2

frequenciesinの実装は次のclojureとおりです。

(defn frequencies
  "Returns a map from distinct items in coll to the number of times
  they appear."
  [coll]
  (persistent!
   (reduce (fn [counts x]
         (assoc! counts x (inc (get counts x 0))))
           (transient {}) coll)))

assoc!突然変異と見なされますか？

assoc!内部の複雑さはfrequencies?

またcounts、各反復で 2 回アクセスされているようです: パフォーマンスが低下しますか?

4

3 に答える 3

4

assoc!は一時的な突然変異であり、O(log n) 償却されていると思います。したがって、全体の実行frequenciesは O(n log n) です。

countsはローカルにバインドされた変数であるため、2 回アクセスしても問題ありません。

複数の状態を使用しない周波数の機能バージョンを次に示します。

(defn frequencies-2 [coll]
  (reduce (fn [m v] (assoc m v (inc (get m v 0)))) {} coll))

この機能バージョンも O(n log n) ですが、より多くの一時オブジェクトを作成して破棄するため、オーバーヘッドが多少大きくなります (より高い定数係数)。

于 2012-10-18T07:13:42.190 に答える
2

ツリーを使用して、要素から周波数へのマップを log(n) の複雑さで格納できます (二分探索ツリー、AVL、赤黒ツリーなどにすることができます)。このツリーの機能的な実装を選択してください。つまり、変更することはできませんが、代わりassoc counts x freqに新しいデータ構造を返し、共通部分を とメモリで共有しcountsます。これは一種の「コピーオンライト」です。その場合、すべての周波数を計算するパフォーマンスは O(n log(n)) になります。

于 2012-10-18T06:45:29.420 に答える
1

assoc!一時データを変更し、よりもはるかに優れたパフォーマンスを発揮しassocます。これは、実際には不変のClojureのモデルに違反しているわけではありません（http://clojure.org/transientsを参照）。

  1. persistent!とtransientはO（1）です
  2. assoc!はO（log32 n）であり、これは事実上O（1）でhash-mapあり、〜2 ^ 32アイテムのサイズに上限があり、これにより最大ツリー深度は6になります。

したがって、の複雑さはfrequenciesのサイズに比例しcollます。

備考：@mikeraが気付いたように、の複雑さは、定数係数も高くなりますが、frequencies線形になります。assoc

于 2012-10-23T03:52:45.047 に答える