clojure - 为什么group-by函数的结果键在大多数情况下是有序的，而在使用with range时却不是？

Question

我正在研究 this problem

我的解决方案是:

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

前三个测试通过，最后一个失败。

因为

(group-by identity (range 50)

给出无序的结果。但我的解决方案强烈依赖于 group-by 函数的有序特性。也就是说必须保持结果映射中每个键的顺序。即使 the Doc 这几乎是正确的不保证。

真正奇怪的是:

你看，当参数超过 32 个时，group-by 函数给出了错误的顺序。结果不是随机的，而是溢出的元素放在第一个元素之后。

为什么？

如何保持group-by函数的有序性，或者有更好的方案吗？

Answer 1

通用 map 的任何排序都是一个实现细节。

较大的 map 是使用哈希表实现的，通常不会保持顺序。对于小映射，散列的开销高于线性查找的开销。因此，优化是让小 map 以数组 map 的形式开始使用，这样可以保持顺序。随着更多元素的添加，映射将转换为 HashMap 。

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

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

此转换发生在 32 个元素之前，但如果不深入研究内部结构，我怀疑初始哈希表有 32 个槽，因此在哈希冲突策略启动之前不会开始出现无序。

至于4Clojure implement distinct就问题而言，您可以使用原始集合中 .indexOf 上的 sort-by 来挽救您的解决方案。

剧透:

(fn [s] (排序方式 #(.indexOf s %) (map #(first %) (group-by identity s))))