2

我正在解决这个问题

我的解决方案是：

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

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

因为

(group-by identity (range 50)

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

真正奇怪的是：

在此处输入图像描述

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

为什么？

如何保持分组功能的有序功能或有更好的解决方案？

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问题而言，您可以使用原始集合中的asort-by来挽救您的解决方案。.indexOf

剧透：

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

于 2013-03-19T12:52:26.853 回答
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 回答
0

将值添加到映射时，会返回适当类型的集合。在 PersistentArrayMaps 的情况下，当大小变得大于 16 项时（参见源代码行 177），它会返回一个 PersistentHashMap，而不是保持顺序。

虽然我无法找到切换到第 33 个元素的行为的直接原因，但我知道处理向量的方式是大小为 32 块，因此更新一个元素不需要全新的向量 - 仅此而已块需要更换。它可能与此或其他一些优化行为有关。

于 2013-03-19T14:09:54.850 回答