当 CPython 设置 `in` 操作符是 O(n)？

Question

我正在阅读 time complexity of set operations in CPython and learned that the in operator for sets has the average time complexity of O(1) and worst case time complexity of O(n). I also learned that the worst case wouldn't occur in CPython unless the set's hash table's load factor is too high。

这让我想知道，在CPython实现中什么时候会出现这种情况？是否有一个简单的演示代码，它显示了一组具有清晰可见的 O(n) 时间复杂度的 in 运算符？

Answer 1

您可以在此处查看 set 来源，这可以提供帮助：https://github.com/python/cpython/blob/723f71abf7ab0a7be394f9f7b2daa9ecdf6fb1eb/Objects/setobject.c#L429-L441

很难设计一个具体的例子，但幸运的是理论相当简单:) 该集合使用值的 hash 存储键，只要 hash 足够独特，您最终会获得预期的 O(1) 性能。

如果出于某种奇怪的原因，您的所有项目都有不同的数据但具有相同的哈希值，它就会发生冲突，并且必须单独检查所有项目。

为了说明，您可以将集合视为像这样的字典：

import collection


your_set = collection.defaultdict(list)


def add(value):
    your_set[hash(value)].append(value)


def contains(value):
    # This is where your O(n) can occur, all values the same hash()
    values = your_set.get(hash(value), [])
    for v in values:
        if v == value:
            return True
    return False

Answer 2

负载系数是一个转移注意力的问题。在 CPython 中，集合（和口述）会自动调整大小以将负载因子保持在 2/3 以下。在 Python 代码中您无法阻止它。

O(N) 当大量元素具有完全相同的哈希码时，可能会出现这种行为。然后它们映射到相同的哈希桶，并将查找退化为线性搜索的缓慢形式。

设计此类不良元素的最简单方法是创建具有可怕散列函数的 class。喜欢，例如，未经测试：

class C:
    def __init__(self, val):
        self.val = val
    def __eq__(a, b):
        return a.val == b.val
    def __hash__(self):
        return 3

然后hash(C(i)) == 3不管i的值。

要对内置类型执行相同的操作，需要深入了解其 CPython 实现细节。例如，这里有一种方法可以使用相同的哈希码创建任意数量的不同整数：

>>> import sys
>>> M = sys.hash_info.modulus
>>> set(hash(1 + i*M) for i in range(10000))
{1}

这表明创建的一万个不同的整数都具有哈希码 1。

Answer 3

这有时称为集合或字典的 'amortization'。它不时作为面试问题出现。正如@TimPeters 所说，调整大小会以 2/3 的容量自动发生，所以如果你自己强制哈希，你只会点击 O(n)。

In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case run time per operation, rather than per algorithm, can be too pessimistic.

`/* GROWTH_RATE. Growth rate upon hitting maximum load.
 * Currently set to used*3.
 * This means that dicts double in size when growing without deletions,
 * but have more head room when the number of deletions is on a par with the
 * number of insertions.  See also bpo-17563 and bpo-33205.
 *
 * GROWTH_RATE was set to used*4 up to version 3.2.
 * GROWTH_RATE was set to used*2 in version 3.3.0
 * GROWTH_RATE was set to used*2 + capacity/2 in 3.4.0-3.6.0.
 */
#define GROWTH_RATE(d) ((d)->ma_used*3)`

更多的是效率点。为什么是 2/3？维基百科文章有一个漂亮的图表 https://upload.wikimedia.org/wikipedia/commons/1/1c/Hash_table_average_insertion_time.png 伴随文章。（对于我们的目的，线性探测曲线对应于 O(1) 到 O(n)，链接是一种更复杂的哈希方法）参见 https://en.wikipedia.org/wiki/Hash_table 完整

假设您有一个稳定的集合或字典，并且是其基础容量的 2/3 - 1。你真的想要永远低迷的表现吗？您可能希望强制向上调整它的大小。

"if the keys are always known in advance, you can store them in a set and build your dictionaries from the set using dict.fromkeys()." 加上一些其他有用的过时观察。 Improving performance of very large dictionary in Python

为了更好地阅读 dictresize()：（dict 在 Python 之前设置） https://github.com/python/cpython/blob/master/Objects/dictobject.c#L415

当 CPython 设置 `in` 操作符是 O(n)？

When CPython set `in` operator is O(n)?

python

cpython

set

time-complexity

in-operator