Когда CPython устанавливает оператор `in`, это O (n)?

Коэффициент загрузки — отвлекающий маневр. В CPython наборы (и словари) автоматически изменяют размер, чтобы коэффициент загрузки не превышал 2/3. Вы ничего не можете сделать в коде Python, чтобы остановить это.

O(N) поведение может иметь место, когда очень много элементов имеют одинаковый хеш-код. Затем они сопоставляются с одним и тем же хэшем и устанавливают вырожденные поисковые запросы в медленную форму линейного поиска.

Самый простой способ придумать такие плохие элементы — это создать класс с ужасной хэш-функцией. Как, например, и непроверенный:

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.

Вы можете просмотреть исходный код 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

Это иногда называют «амортизацией» набора или словаря. Это появляется время от времени как вопрос интервью. Как говорит @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 от его базовой емкости. Вы действительно хотите вялую производительность навсегда? Вы можете принудительно увеличить его размер.

«если ключи всегда известны заранее, вы можете хранить их в наборе и создавать свои словари из набора, используя dict.fromkeys ()». плюс некоторые другие полезные, хотя и датированные наблюдения. Повышение производительности очень большого словаря в Python

Для хорошего чтения о dictresize(): (dict был в Python до установки) https://github.com/python/cpython/blob/master/Objects/dictobject.c#L415