scala - Scala中的并行递归记忆

Question

我在 Scala 中有一个记忆的分而治之算法：

val cache = mutable.Map[Int, BigInt]()
cache(1) = BigInt(0)

def dp(n: Int): BigInt = cache.getOrElseUpdate(n, {
  partitions(n).map(i => dp(i)).min
  // partitions is non-recursive function that given an Int returns a list[Int]
})

但是，我想将此代码转换为在递归时使用并行化，方法是更改partitions(n)​​为partitions(n).parwhich 返回并行列表。但是现在，我的状态很糟糕，cache因为该地图不是并发的。cache当我使用trait进行实例化时，我的SynchronizedMap所有 fork 都会加入线程块，因为所做的只是在方法调用周围SynchronizedMap放置一个巨大的块。那么，在记忆化的同时进行递归分治算法的 Scala 习语是什么？synchronizedgetOrElseUpdate

Answer 1

我的经验法则：永远不要创建自己的缓存。如果你真的想走可变路线，你可能想看看Guava的CacheBuilder 类。如果我没记错的话，它提供了适当的同步（和其他好东西），但仍然非常轻量级。

编辑：

Scalaz 7 提供了Memo一种声称具有线程安全实现的类型 ( immutableHashMapMemo, immutableListMapMemo, immutableTreeMapMemo)。乍一看，它看起来像你需要的，但我自己没有使用过，我有点怀疑：我认为var应该标记用于存储相应地图的@volatile用于避免可见性问题。

Answer 2

找到了解决方案：val cache = concurrent.TrieMap[Int, BigInt]-并发！=同步