为什么在大多数情况下,group-by函数的结果键按顺序排列,但在使用范围时却没有？

Question

我的解决方案是:

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

前三次测试通过,最后一次测试失败.

因为

(group-by identity (range 50)

给出无序的结果.但我的解决方案强烈依赖于分组功能的有序功能.也就是说,必须保持结果映射中每个键的顺序.即使Doc不能保证这一点,这几乎也是如此.

真奇怪的是:

在此输入图像描述

你看,当参数超过32分组函数给出错误的顺序.结果不是随机的,而是溢出的元素在第一个之后.

为什么？

如何保留分组功能的有序功能还是有更好的解决方案？

Answer 1

通用映射的任何排序都是实现细节.

使用哈希表实现较大的映射,这通常不会保留顺序.对于小地图,散列的开销高于线性查找的开销.因此,优化是针对小地图以数组地图开始生命,这确实保留了顺序.随着添加更多元素,地图将转换为哈希映射.

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

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

这种转换发生在32个元素之前,但是没有深入到内部,我怀疑初始哈希表有32个槽,因此在哈希冲突策略启动之前不会开始发生混乱.

就4Clojure实施distinct问题而言,您可以使用原始集合中的sort-byon 来挽救您的解决方案.indexOf.

扰流板:

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