Python 如何确定集合中元素的顺序?
- 2024-12-25 08:51:00
- admin 原创
- 134
问题描述:
我知道sets
在 Python 中它们是无序的,但我对它们显示的“顺序”感到好奇,因为它似乎是一致的。它们似乎每次都以同样的方式乱序:
>>> set_1 = set([5, 2, 7, 2, 1, 88])
>>> set_2 = set([5, 2, 7, 2, 1, 88])
>>> set_1
set([88, 1, 2, 5, 7])
>>> set_2
set([88, 1, 2, 5, 7])
...另一个例子:
>>> set_3 = set('abracadabra')
>>> set_4 = set('abracadabra')
>>> set_3
set(['a', 'r', 'b', 'c', 'd'])
>>>> set_4
set(['a', 'r', 'b', 'c', 'd'])
我只是好奇为什么会这样。有什么帮助吗?
解决方案 1:
你应该看看这个视频(虽然它是特定于 CPython 1并且关于字典的 - 但我认为它也适用于集合)。
基本上,python 对元素进行哈希处理并取最后 N 位(其中 N 由集合的大小决定),并使用这些位作为数组索引将对象放置在内存中。然后按照对象在内存中的存在顺序生成对象。当然,当您需要解决哈希之间的冲突时,情况会变得稍微复杂一些,但这就是它的要点。
还请注意,它们的打印顺序由您输入的顺序决定(由于冲突)。因此,如果您重新排序传递给 的列表set_2
,如果存在密钥冲突,您可能会得到不同的顺序。
例如:
list1 = [8,16,24]
set(list1) #set([8, 16, 24])
list2 = [24,16,8]
set(list2) #set([24, 16, 8])
请注意,这些集合中保留顺序的事实是“巧合”,并且与冲突解决有关(我对此一无所知)。关键是hash(8)
,hash(16)
和的最后 3 位hash(24)
是相同的。由于它们相同,因此冲突解决接管并将元素放在“备用”内存位置而不是第一个(最佳)选择中,因此是否8
占据一个位置或16
取决于哪一个先到达聚会并占据“最佳座位”。
如果我们用 和 重复该示例1
,2
则3
无论它们在输入列表中的顺序如何,您都会得到一致的顺序:
list1 = [1,2,3]
set(list1) # set([1, 2, 3])
list2 = [3,2,1]
set(list2) # set([1, 2, 3])
因为的最后3位hash(1)
、hash(2)
和hash(3)
是唯一的。
1注意此处描述的实现适用于 CPythondict
和set
。我认为一般描述适用于所有现代版本的 CPython 3.6 及以下版本。但是,从 CPython3.6 开始,有一个额外的实现细节,实际上保留了 迭代的插入顺序dict
。似乎set
仍然没有这个属性。pypy 人员(他们在 CPython 人员之前就开始使用它)在这篇博客文章中描述了数据结构。原始想法(至少对于 python 生态系统而言)存档在 python-dev 邮件列表中。
解决方案 2:
这种行为的原因是 Python 使用哈希表来实现字典:https://en.wikipedia.org/wiki/Hash_table#Open_addressing
键的位置由其内存地址定义。如果您知道 Python 会重用某些对象的内存:
>>> a = 'Hello world'
>>> id(a)
140058096568768
>>> a = 'Hello world'
>>> id(a)
140058096568480
可以看到对象a每次初始化的时候都有不同的地址。
但对于小的整数来说,它不会改变:
>>> a = 1
>>> id(a)
40060856
>>> a = 1
>>> id(a)
40060856
即使我们创建具有不同名称的第二个对象,它也将是相同的:
>>> b = 1
>>> id(b)
40060856
这种方法可以节省 Python 解释器消耗的内存。
解决方案 3:
mgilson 的精彩答案中暗示了一个关键点,但在任何现有答案中都没有明确提及:
小整数哈希值为自身:
>>> [hash(x) for x in (1, 2, 3, 88)]
[1, 2, 3, 88]
字符串哈希值是不可预测的。事实上,从 3.3 开始,默认情况下,它们由启动时随机化的种子构建。因此,每个新的 Python 解释器会话都会得到不同的结果,但是:
>>> [hash(x) for x in 'abcz']
[6014072853767888837,
8680706751544317651,
-7529624133683586553,
-1982255696180680242]
因此,考虑最简单的哈希表实现:只是一个包含 N 个元素的数组,其中插入一个值意味着将其放入hash(value) % N
(假设没有冲突)。您可以粗略地猜测N
它的大小——它将比其中的元素数量稍大。当从 6 个元素的序列创建一个集合时,N 很容易就是 8。
当您将这 5 个数字存储为 N=8 时会发生什么?好吧hash(1) % 8
,hash(2) % 8
、 等只是数字本身,但hash(88) % 8
是 0。因此,哈希表的数组最终会保留88, 1, 2, NULL, NULL, 5, NULL, 7
。因此,应该很容易弄清楚为什么迭代集合可能会给您88, 1, 2, 5, 7
。
当然,Python 并不保证每次都能得到这个顺序。对猜测正确值的方式进行一点小改动N
可能会导致88
结果不同(或与其他值发生冲突)。事实上,在我的 Mac 上运行 CPython 3.7 时,我得到了1, 2, 5, 7, 88
.0
同时,当您从大小为 11 的序列构建哈希,然后将随机哈希插入其中时,会发生什么?即使假设最简单的实现,并且假设没有冲突,您仍然不知道您将获得什么顺序。它在 Python 解释器的一次运行中是一致的,但下次启动时会有所不同。(除非您设置PYTHONHASHSEED
为0
,或其他 int 值。)这正是您所看到的。
当然,值得一看的是集合的实际实现方式,而不是猜测。但是,基于最简单的哈希表实现的假设(排除冲突和哈希表扩展),您猜测的正是发生的事情。
解决方案 4:
据我所知,Python 集合是使用哈希表实现的。项目出现的顺序取决于所使用的哈希函数。在程序的同一运行中,哈希函数可能不会改变,因此您会得到相同的顺序。
但不能保证它总是使用相同的函数,并且顺序会在运行过程中发生变化 - 或者在同一运行中,如果你插入大量元素并且哈希表必须调整大小。
解决方案 5:
集合基于哈希表。值的哈希值应该是一致的,因此顺序也应一致 - 除非两个元素的哈希值相同,在这种情况下插入顺序将改变输出顺序。