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,...

问题描述:

我知道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取决于哪一个先到达聚会并占据“最佳座位”。

如果我们用 和 重复该示例123无论它们在输入列表中的顺序如何,您都会得到一致的顺序:

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注意此处描述的实现适用于 CPythondictset。我认为一般描述适用于所有现代版本的 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) % 8hash(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 解释器的一次运行中是一致的,但下次启动时会有所不同。(除非您设置PYTHONHASHSEED0,或其他 int 值。)这正是您所看到的。


当然,值得一看的是集合的实际实现方式,而不是猜测。但是,基于最简单的哈希表实现的假设(排除冲突和哈希表扩展),您猜测的正是发生的事情。

解决方案 4:

据我所知,Python 集合是使用哈希表实现的。项目出现的顺序取决于所使用的哈希函数。在程序的同一运行中,哈希函数可能不会改变,因此您会得到相同的顺序。

但不能保证它总是使用相同的函数,并且顺序会在运行过程中发生变化 - 或者在同一运行中,如果你插入大量元素并且哈希表必须调整大小。

解决方案 5:

集合基于哈希表。值的哈希值应该是一致的,因此顺序也应一致 - 除非两个元素的哈希值相同,在这种情况下插入顺序将改变输出顺序。

相关推荐
  政府信创国产化的10大政策解读一、信创国产化的背景与意义信创国产化,即信息技术应用创新国产化,是当前中国信息技术领域的一个重要发展方向。其核心在于通过自主研发和创新,实现信息技术应用的自主可控,减少对外部技术的依赖,并规避潜在的技术制裁和风险。随着全球信息技术竞争的加剧,以及某些国家对中国在科技领域的打压,信创国产化显...
工程项目管理   1579  
  为什么项目管理通常仍然耗时且低效?您是否还在反复更新电子表格、淹没在便利贴中并参加每周更新会议?这确实是耗费时间和精力。借助软件工具的帮助,您可以一目了然地全面了解您的项目。如今,国内外有足够多优秀的项目管理软件可以帮助您掌控每个项目。什么是项目管理软件?项目管理软件是广泛行业用于项目规划、资源分配和调度的软件。它使项...
项目管理软件   1355  
  信创产品在政府采购中的占比分析随着信息技术的飞速发展以及国家对信息安全重视程度的不断提高,信创产业应运而生并迅速崛起。信创,即信息技术应用创新,旨在实现信息技术领域的自主可控,减少对国外技术的依赖,保障国家信息安全。政府采购作为推动信创产业发展的重要力量,其对信创产品的采购占比情况备受关注。这不仅关系到信创产业的发展前...
信创和国产化的区别   8  
  信创,即信息技术应用创新产业,旨在实现信息技术领域的自主可控,摆脱对国外技术的依赖。近年来,国货国用信创发展势头迅猛,在诸多领域取得了显著成果。这一发展趋势对科技创新产生了深远的推动作用,不仅提升了我国在信息技术领域的自主创新能力,还为经济社会的数字化转型提供了坚实支撑。信创推动核心技术突破信创产业的发展促使企业和科研...
信创工作   9  
  信创技术,即信息技术应用创新产业,旨在实现信息技术领域的自主可控与安全可靠。近年来,信创技术发展迅猛,对中小企业产生了深远的影响,带来了诸多不可忽视的价值。在数字化转型的浪潮中,中小企业面临着激烈的市场竞争和复杂多变的环境,信创技术的出现为它们提供了新的发展机遇和支撑。信创技术对中小企业的影响技术架构变革信创技术促使中...
信创国产化   8  
热门文章
项目管理软件有哪些?
云禅道AD
禅道项目管理软件

云端的项目管理软件

尊享禅道项目软件收费版功能

无需维护,随时随地协同办公

内置subversion和git源码管理

每天备份,随时转为私有部署

免费试用