并行递归记忆化斯卡拉

Question

我在Scala中有一个memoized分而治之算法：

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).par它返回一个平行的列表，而不是递归。但是现在，我在cache中处于不良状态，因为该地图不是并发的。当我将cache与SynchronizedMap实例化时，所有我的fork都加入了线程块，因为所有SynchronizedMap都会在getOrElseUpdate方法调用周围放置一个巨大的​​块。那么什么是斯卡拉成语做一个递归的鸿沟和征服算法并行与memoization？

Answer 1

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

Answer 2

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

编辑：

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