如何实现set()？

Question

如何实现set()？

Dae*_*yth 140 python cpython set data-structures

我见过有人说setpython 中的对象有O(1)成员资格检查.它们如何在内部实施以实现这一目标？它使用什么样的数据结构？该实施还有哪些其他含义？

这里的每个答案都很有启发性,但我只能接受一个,所以我会用最接近我原来问题的答案.谢谢你的信息!

Answer 1

Jus*_*ier 128

根据这个帖子:

实际上,CPython的集合实现为具有虚拟值的字典(键是集合的成员),并且利用这些缺乏值的一些优化

所以基本上a set使用哈希表作为其底层数据结构.这解释了O(1)成员资格检查,因为在哈希表中查找项目平均是O(1)操作.

如果您如此倾向,您甚至可以浏览CPython源代码,根据Achim Domma的说法,该代码主要是实现的剪切和粘贴dict.

IIRC,原来的`set`实现*实际上是*`dict`,带有虚拟值,后来得到了优化. (17认同)
@ThunderPhoenix：它们并不总是按递增顺序，但对于某些类型（例如“int”），哈希码是可预测的，您会在许多简单的测试用例中看到递增顺序。此外，一些常见的工具（例如 IPython）对“集合”进行排序以进行显示，而不是显示原始迭代顺序。Python 的 set 类似于 C++ 的 unordered_set ，而不是 C++ 的 set 。如果您想要对此进行可靠的演示，请运行“print(set(range(-5, 5)))”。然后为了好玩，运行 `print({-1, *range(-5, 5)})` 并记下 `-1` 和 `-2` 更改的顺序（在 CPython 上，由于 API，它们具有相同的哈希值）限制）。 (5认同)
不,平均情况是O(1),但最坏情况是哈希表查找的O(N). (4认同)
@ClaudiuCreanga这是一个老评论,但只是为了澄清:big-O符号告诉你事物增长率的上限,但你可以上限平均案例绩效的增长,你可以单独上限最坏情况的增长性能. (4认同)
大O不是最坏的情况吗？如果你能找到一个时间为 O(n) 的实例，那么它就是 O(n) .. 我现在对所有这些教程一无所知。 (2认同)
我进行编辑以澄清“set”和“dict”不再以通用代码的方式使用太多。只是为了详细说明，“dict”现在是插入顺序的，并进行了优化以最大限度地减少过度分配（假设小型“dict”在构建后不会增长太多/根本不会增长），支持从一组固定的键中重复查找，并假设很少有“dict”删除键，所有这些都在用于实现属性时提高了性能（对于所有用户定义的类和大多数用户定义的类实例）；`set` 会分配更多资源并更有效地处理项目删除，从而优化重复数据删除和实时更新。 (2认同)

Answer 2

unu*_*tbu 73

当人们说集合有O(1)成员资格检查时,他们正在讨论平均情况.在最坏的情况下(当所有散列值冲突时),成员资格检查是O(n).请参阅Python wiki的时间复杂度.

在维基百科的文章说,最好的情况下为一个哈希表,不调整是时间复杂度O(1 + k/n).此结果不直接适用于Python集,因为Python集使用调整大小的哈希表.

维基百科的文章稍微进一步说,对于普通情况,并假设一个简单的统一散列函数,时间复杂度O(1/(1-k/n)),k/n可以由常量限制c<1.

Big-O仅指n→∞的渐近行为.由于k/n可以以常数为界,c <1,与n无关,

O(1/(1-k/n))不大于O(1/(1-c))等于O(constant)= O(1).

因此,假设统一的简单散列,平均而言,Python集的成员资格检查是O(1).

Answer 3

Sha*_*men 13

我认为这是一个常见的错误,set查找(或哈希表)不是O(1).
来自维基百科

在最简单的模型中,哈希函数是完全未指定的,并且表不会调整大小.为了最好地选择散列函数,具有开放寻址的大小为n的表没有冲突并且最多可容纳n个元素,单个比较用于成功查找,而具有链接和k键的大小为n的表具有最小最大值(0,kn)碰撞和O(1 + k/n)比较用于查找.对于哈希函数的最差选择,每次插入都会导致冲突,哈希表退化为线性搜索,每次插入时进行Ω(k)分摊比较,最多进行k次比较,以便成功查找.

相关:Java hashmap真的是O(1)吗？

但他们确实需要花费一些时间来查找项目:python -m timeit -s"s = set(range(10))""s in s"10000000循环,最好的3:0.0642 usec每循环< - > python - m timeit -s"s = set(range(10000000))""s in s"10000000循环,最好3:0.0634 usec每循环......这是不抛出MemoryErrors的最大集合 (4认同)
@intuited:确实如此,但上面的测试并不能证明你可以在查找"485398"的同时查找"5",或者可能在可怕的碰撞空间中查找其他数字.它不是同时在不同大小的哈希中查找相同的元素(事实上,根本不需要),而是关于您是否可以在当前表中的相同时间内访问每个条目 - 因为通常总是存在冲突,所以哈希表基本上不可能完成. (3认同)
换句话说,进行查找的时间取决于存储值的数量,因为这会增加冲突的可能性. (3认同)
@intuited:不,那是不对的.当存储值的数量增加时,Python将自动增加哈希表的大小,并且冲突率大致保持不变.假设均匀分布的O(1)哈希算法,则哈希表查找是*摊销*O(1).您可能想观看视频演示"The Mighty Dictionary"http://python.mirocommunity.org/video/1591/pycon-2010-the-mighty-dictiona (3认同)
@ THC4k所有你证明的是,查找X是在恒定的时间内完成的,但这并不意味着查找X + Y的时间将花费相同的时间,这是O(1)的全部内容. (2认同)

Answer 4

gim*_*mel 13

我们都可以轻松访问源代码,前面的评论set_lookkey()说:

/* set object implementation
 Written and maintained by Raymond D. Hettinger <python@rcn.com>
 Derived from Lib/sets.py and Objects/dictobject.c.
 The basic lookup function used by all operations.
 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
 The initial probe index is computed as hash mod the table size.
 Subsequent probe indices are computed as explained in Objects/dictobject.c.
 To improve cache locality, each probe inspects a series of consecutive
 nearby entries before moving on to probes elsewhere in memory.  This leaves
 us with a hybrid of linear probing and open addressing.  The linear probing
 reduces the cost of hash collisions because consecutive memory accesses
 tend to be much cheaper than scattered probes.  After LINEAR_PROBES steps,
 we then use open addressing with the upper bits from the hash value.  This
 helps break-up long chains of collisions.
 All arithmetic on hash should ignore overflow.
 Unlike the dictionary implementation, the lookkey function can return
 NULL if the rich comparison returns an error.
*/


...
#ifndef LINEAR_PROBES
#define LINEAR_PROBES 9
#endif

/* This must be >= 1 */
#define PERTURB_SHIFT 5

static setentry *
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)  
{
...

Run Code Online (Sandbox Code Playgroud)

此答案将受益于C [语法突出显示]（https://meta.stackexchange.com/questions/184108/what-is-syntax-highlighting-and-how-does-it-work）。注释的Python语法高亮显示看起来确实很糟糕。 (2认同)

Answer 5

use*_*754 5

为了更多地强调和之间的区别set's，dict's这里是评论部分的摘录setobject.c，它澄清了 set 与 dict 的主要区别。

集合的用例与字典有很大不同，字典中查找的键更有可能出现。相比之下，集合主要是关于成员资格测试，其中元素的存在是事先未知的。因此，集合实现需要针对已找到和未找到的情况进行优化。

源码在github上

Answer 6

小智 5

python 中的集合在内部使用哈希表。我们先来说说哈希表。假设您想要在哈希表中存储一些元素，并且哈希表中有 31 个位置可以执行此操作。设元素为：2.83、8.23、9.38、10.23、25.58、0.42、5.37、28.10、32.14、7.31。当您想要使用哈希表时，首先确定哈希表中存储这些元素的索引。模函数是确定这些索引的一种流行方法，因此假设我们一次取一个元素，将其乘以 100，然后对 31 进行模运算。重要的是，对元素的每个此类操作都会产生一个唯一的数字，作为除非允许链接，否则哈希表中的条目只能存储一个元素。这样，每个元素将存储在由通过模运算获得的索引控制的位置。现在，如果您想在本质上使用此哈希表存储元素的集合中搜索某个元素，您将在 O(1) 时间内获得该元素，因为该元素的索引是在恒定时间内使用模运算计算出来的。为了阐述模运算，我也写一些代码：

piles = [2.83, 8.23, 9.38, 10.23, 25.58, 0.42, 5.37, 28.10, 32.14, 7.31]

def hash_function(x):
    return int(x*100 % 31)

[hash_function(pile) for pile in piles]

Run Code Online (Sandbox Code Playgroud)

输出：[4, 17, 8, 0, 16, 11, 10, 20, 21, 18]

真的很难理解一堵文字墙:( (2认同)

归档时间：	15 年，1 月前
查看次数：	53255 次
最近记录：	6 年，12 月前