データ要素の順序付けられていないペアを作成しています。この質問に関する@Chouser のコメントによると、ハッシュセットはノードごとに 32 の子で実装され、ソートセットはノードごとに 2 つの子で実装されます。これは、ペアをハッシュセットではなくソートセットで実装すると、ペアが占めるスペースが少なくなることを意味しますか (データ要素が比較可能、つまりソート可能であると仮定)? (実際にはそれが問題になるとは思えません。これらのペアは数百しかなく、2 要素のデータ構造でのルックアップ、ベクトルまたはリストでのシーケンシャル ルックアップでさえも高速である必要があります。しかし、興味があります。)
4 に答える
1
順序付けられていないペアで何かをしている場合、通常はマップを使用するのが好きです。これにより、他の要素を簡単に検索できるからです。たとえば、ペアが[2 7]{2 7, 7 2}の場合、を使用します。({2 7, 7 2} 2)これにより、 が得られます7。
スペースに関しては、PersistentArrayMap実装は実際には非常にスペースを意識しています。ソース コード (前のリンクを参照) を見ると、Object[]すべてのキーと値のペアを保持するのに必要な正確なサイズの が割り当てられていることがわかります。これは、キーと値のペアが 8 つ以下のすべてのマップのデフォルトのマップ タイプとして使用されていると思います。
ここでの唯一の問題は、重複キーに注意する必要があることです。{2 2, 2 2}例外が発生します。次のようなことを行うことで、この問題を回避できます。(merge {2 2} {2 2})つまり、同じ値を持つ(merge {a b} {b a})可能性がある場合。ab
ここに私のreplからの小さなスニペットがあります:
user=> (def a (array-map 1 2 3 4))
#'user/a
user=> (type a)
clojure.lang.PersistentArrayMap
user=> (.count a) ; count simply returns array.length/2 of the internal Object[]
2
array-map上記で明示的に呼び出したことに注意してください。defこれは、マップ リテラルとrepl に関連して、少し前に私が尋ねた質問に関連しています。
于 2013-11-05T22:34:23.283 に答える
0
今は異なるペア表現のベンチマークを行うつもりはありませんでしたが、@ArthurUlfeldt の回答と @DaoWen のおかげでそうするようになりました。benchこれが基準のマクロを使用した私の結果です。ソースコードは以下。要約すると、予想どおり、テストした 7 つの表現の間に大きな違いはありません。ただし、最速の array-map および hash-map とその他の時間にはギャップがあります。これは、DaoWen と Arthur Ulfeldt の発言と一致しています。
平均実行時間 (秒単位)。最速から順に (MacBook Pro、2.3GHz Intel Core i7):
配列マップ: 5.602099
ハッシュマップ: 5.787275
ベクトル: 6.605547
ソートセット: 6.657676
ハッシュセット: 6.746504
リスト: 6.948222
編集:test-control以下の実行を追加しました。これは、他のすべての異なるテストに共通することのみを行います。 test-control平均で 5.571284 秒かかりました。表現と他の表現との間には、私が思っていたよりも大きな違いがあるようです-map: 2 つのエントリのハッシュマップまたは配列マップへのアクセスは、(私のコンピューター、OS、Java などでは) 基本的に瞬時に行われますが、他の表現では、1,000 万回の反復に約 1 秒かかります。これは、1,000 万回の反復であることを考えると、これらの操作がまだほぼ瞬時であることを意味します。(私の推測では、コンピューターのバックグラウンドで発生している他のことからのノイズが原因であるtest-arraymapよりも高速だったということです。または、コンパイルの特異性に関係している可能性があります。)test-control
(警告: 基準から警告が表示されることを忘れていました:「JVM 引数 TieredStopAtLevel=1 がアクティブであり、JIT C2 コンパイラがアクティブでない可能性があるため、予期しない結果につながる可能性があります。」これは、Leiningen が-server JITコンパイラ向けのコマンドラインオプションでJavaを起動しますが、代わりにデフォルトの-client JITコンパイラで実行されています.したがって、警告は「あなたは-serverを実行していると思いますが、そうではありません.であるため、-server の動作は期待しないでください。" -server を指定して実行すると、上記の時間が変わる可能性があります。)
(use 'criterium.core)
;; based on Arthur Ulfedt's answer:
(defn pairlist-contains? [key pair]
(condp = key
(first pair) true
(second pair) true
false))
(defn pairvec-contains? [key pair]
(condp = key
(pair 0) true
(pair 1) true
false))
(def ntimes 10000000)
;; Test how long it takes to do what's common to all of the other tests
(defn test-control []
(print "=============================\ntest-control:\n")
(bench
(dotimes [_ ntimes]
(def _ (rand-nth [:a :b])))))
(defn test-list []
(let [data '(:a :b)]
(print "=============================\ntest-list:\n")
(bench
(dotimes [_ ntimes]
(def _ (pairlist-contains? (rand-nth [:a :b]) data))))))
(defn test-vec []
(let [data [:a :b]]
(print "=============================\ntest-vec:\n")
(bench
(dotimes [_ ntimes]
(def _ (pairvec-contains? (rand-nth [:a :b]) data))))))
(defn test-hashset []
(let [data (hash-set :a :b)]
(print "=============================\ntest-hashset:\n")
(bench
(dotimes [_ ntimes]
(def _ (contains? data (rand-nth [:a :b])))))))
(defn test-sortedset []
(let [data (sorted-set :a :b)]
(print "=============================\ntest-sortedset:\n")
(bench
(dotimes [_ ntimes]
(def _ (contains? data (rand-nth [:a :b])))))))
(defn test-hashmap []
(let [data (hash-map :a :a :b :b)]
(print "=============================\ntest-hashmap:\n")
(bench
(dotimes [_ ntimes]
(def _ (contains? data (rand-nth [:a :b])))))))
(defn test-arraymap []
(let [data (array-map :a :a :b :b)]
(print "=============================\ntest-arraymap:\n")
(bench
(dotimes [_ ntimes]
(def _ (contains? data (rand-nth [:a :b])))))))
(defn test-all []
(test-control)
(test-list)
(test-vec)
(test-hashset)
(test-sortedset)
(test-hashmap)
(test-arraymap))
于 2013-11-06T06:30:23.323 に答える