2

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).par、私の状態が悪くなります。cacheトレイトでインスタンス化cacheすると、メソッド呼び出しの周りに巨大なブロックを配置するだけなSynchronizedMapので、すべてのフォークがスレッド ブロックに参加します。では、メモ化と並行して再帰的な分割統治アルゴリズムを実行するための Scala のイディオムは何ですか?SynchronizedMapsynchronizedgetOrElseUpdate

4

2 に答える 2

3

私の経験則: 独自のキャッシュを作成しないでください。本当に変更可能なルートに行きたい場合は、GuavaのCacheBuilder クラスを調べることをお勧めします。私の記憶が正しければ、適切な同期 (およびその他の機能) を提供しますが、それでも非常に軽量です。

編集：

Scalaz 7 は、スレッドセーフな実装 ( 、、 )Memoを持つと主張する型を提供します。一見すると、必要なもののように見えますが、私自身は使用したことがなく、少し懐疑的です。それぞれのマップを保存するために使用されるものは、可視性の問題を避けるためにマークする必要があると思います.immutableHashMapMemoimmutableListMapMemoimmutableTreeMapMemovar@volatile

于 2013-01-24T07:33:32.017 に答える
1

解決策を見つけました: val cache = concurrent.TrieMap[Int, BigInt]- 並行性 != 同期

于 2013-01-24T09:18:41.393 に答える