2

私はこの問題に取り組んでいます

私の解決策は次のとおりです。

(fn [s]
  (map #(first %) (group-by identity s)))

最初の 3 つのテストは成功し、最後のテストは失敗しました。

なぜなら

(group-by identity (range 50)

順不同で結果を返します。しかし、私のソリューションは、group-by 関数の順序付き機能に強く依存しています。つまり、結果マップ内のすべてのキーの順序を維持する必要があります。Docはそれを保証していませんが、これはほとんど真実です。

本当に奇妙なことは次のとおりです。

ここに画像の説明を入力

ご覧のとおり、パラメーターが 32 を超える場合、group-by 関数は間違った順序になります。結果はランダムではありませんが、オーバーフローした要素が最初の要素の後に追加されます。

なんで？

group-by 関数の順序付き機能を維持するにはどうすればよいですか、それともより良い解決策がありますか?

4

3 に答える 3

6

汎用マップの順序付けは、実装の詳細です。

より大きなマップはハッシュ テーブルを使用して実装されますが、これは一般に順序を保持しません。小さなマップの場合、ハッシュのオーバーヘッドは線形ルックアップのコストよりも高くなります。したがって、最適化は、小さなマップを配列マップとして開始することであり、順序を保持します。さらに要素が追加されると、マップはハッシュ マップに変換されます。

(class (group-by identity (range 8)))
;=> clojure.lang.PersistentArrayMap

(class (group-by identity (range 32)))
;=> clojure.lang.PersistentHashMap

この変換は 32 個の要素の前に発生しますが、内部構造を掘り下げることなく、最初のハッシュ テーブルには 32 個のスロットがあると思われるため、ハッシュ衝突戦略が開始されるまで無秩序化は発生しません。

4Clojure 実装distinctの問題に関する限り、元のコレクションの を使用してソリューションを回収できますsort-by。.indexOf

ネタバレ：

(fn [s] (sort-by #(.indexOf s %) (map #(first %) (group-by identity s))))

于 2013-03-19T12:52:26.853 に答える
0

マップに値を追加すると、適切なタイプのコレクションが返されます。PersistentArrayMapsの場合、サイズが16アイテムより大きくなると（ソース行177を参照）、代わりにPersistentHashMapを返しますが、これは順序を維持しません。

33番目の要素に切り替える動作の直接的な理由を見つけることはできませんでしたが、ベクターの処理方法はサイズ32チャンクであるため、1つの要素を更新するために完全に新しいベクターは必要ありません。チャンクを交換する必要があります。それはそれ、または他の最適化動作と関係があるかもしれません。

于 2013-03-19T14:09:54.850 に答える
0

あなたが欲しいように聞こえますsorted-map：

=> (apply sorted-map (flatten (seq (group-by identity (range 50)))))
{0 0, 1 1, 2 2, 3 3, 4 4, 5 5, 6 6, 7 7, 8 8, 9 9, 10 10, 11 11, 12 12, 13 13, 14 14, 15 15, 16 16, 17 17, 18 18, 19 19, 20 20, 21 21, 22 22, 23 23, 24 24, 25 25, 26 26, 27 27, 28 28, 29 29, 30 30, 31 31, 32 32, 33 33, 34 34, 35 35, 36 36, 37 37, 38 38, 39 39, 40 40, 41 41, 42 42, 43 43, 44 44, 45 45, 46 46, 47 47, 48 48, 49 49}

これまで見てきたように、小さなマップを扱っている場合、clojure はソートされた実装を選択することがあります。ただし、これは実装の詳細であり、保証されるものではありません。sorted-mapキーの反復順序がソートされることが保証されているマップを返します。

于 2013-03-19T12:43:57.780 に答える