python - python中集合的“奇怪”排序

Question

当我将 Python 3.8.0 列表转换为集合时，生成的集合排序* 以非平凡的方式高度结构化。这个结构是如何从伪随机列表中提取出来的？

---

作为我正在运行的实验的一部分，我正在生成一个随机集。我惊讶地发现，绘制集合突然在集合中显示出意想不到的线性结构。所以有两件事让我感到困惑——为什么转换为一个集合结果有一个排序*，它最终突出了这个结构；而且，在较小程度上，为什么伪随机集完全有这种“隐藏”结构？

编码：

X = [randrange(250) for i in range(30)]
print(X)
print(set(X))

例如，它的输出

[238, 202, 245, 94, 111, 106, 148, 164, 154, 113, 128, 10, 196, 141, 69, 38, 106, 8, 40, 53, 160, 87, 85, 13, 38, 147, 204, 50, 162, 91]

{128, 8, 10, 141, 13, 147, 148, 154, 160, 162, 164, 38, 40, 50, 53, 196, 69, 202, 204, 85, 87, 91, 94, 106, 238, 111, 113, 245}

正如预期的那样，上面列表的图**看起来相当随机：

而绘制集合（因为它在输出中排序）展示了集合中存在的结构：

这种行为在我的机器上（下面有更多示例）与上面代码中使用的值 250 和 30 100% 一致（我使用的示例不是樱桃挑选的——它只是我运行的最后一个）。调整这些值有时会导致结构略有不同（例如，三个算术级数的子集*** 而不是两个）。

这可以在其他人的机器上重现吗？当然，这种结构的存在似乎表明伪随机数生成不太好，但这并不能解释转换为集合在某种意义上如何“提取”这种结构。据我所知，没有正式保证集合的排序（从列表转换时）是确定性的（即使是，也没有在后台进行复杂的排序）。那么这是怎么回事？！

---

(*)：我知道，集合是无序的集合，但我的意思是“有序”，因为在调用print语句时，集合以某种顺序输出，始终突出显示底层集合结构。

(**)：这些图来自 Wolfram Alpha。下面还有两个例子：

(***)：将随机数的范围从 250 更改为 500 时的两个图：

标签： python

Answer 1

基本上，这是因为两件事：

• Python 中的集合是使用哈希表实现的，
• 整数的散列就是整数本身。

因此，整数出现在基础数组中的索引将由整数的值确定，以基础数组的长度为模。因此，当您将整数的连续范围放入集合时，整数将倾向于保持升序：

>>> list(set(range(10000))) == list(range(10000))
True # this can't be an accident!

如果您没有连续范围内的所有数字，那么“以底层数组的长度为模”部分就会起作用：

>>> r = range(0, 50, 4)
>>> set(r)
{0, 32, 4, 36, 8, 40, 12, 44, 16, 48, 20, 24, 28}
>>> sorted(r, key=lambda x: x % 32)
[0, 32, 4, 36, 8, 40, 12, 44, 16, 48, 20, 24, 28]

如果您知道底层数组的长度以及添加元素的（确定性）算法，则该序列是可预测的。在这种情况下，数组的长度是 32，因为它最初是 8 ，并且在添加元素时是四倍。

除了接近尾端的一个光点（因为数字 52 和 56 不在集合中），范围分为两个序列0, 4, 8, ...，并且32, 36, 40, ...它们交替，因为哈希值本身是数字的值，取模 32 来选择数组中的索引。有碰撞；例如，4 和 36 模 32 相等，但 4 首先添加到集合中，因此 36 以不同的索引结束。

这是这个序列的图表。图表中的结构只是一个嘈杂的版本，因为您是随机生成数字而不是从一个带步长的范围生成的。

交错序列的数量将取决于集合的大小与从中采样数字的范围的长度成比例，因为这决定了范围的长度“环绕”多少倍，以哈希表的基础数组的长度为模。这是一个具有三个交错序列的示例0, 6, 12, ...，66, 72, 78, ...并且36, 42, 48, ...：

>>> set(range(0, 90, 6))
{0, 66, 36, 6, 72, 42, 12, 78, 48, 18, 84, 54, 24, 60, 30}