Как реализовано set()?

Ответ 1

Согласно этот поток:

Действительно, наборы CPython реализованы как нечто вроде словарей с фиктивными значениями (ключи, являющиеся членами набора), с некоторыми оптимизация (ы), которые используют это отсутствие значений

Таким образом, в основном set использует хэш-таблицу в качестве своей базовой структуры данных. Это объясняет проверку членства O (1), так как поиск элемента в хэш-таблице в среднем является операцией O (1).

Если вы так склонны, вы можете даже просмотреть исходный код CPython для набора, который, согласно Achim Domma, является главным образом вырезанием и вставкой из реализации dict.

Ответ 2

Когда люди говорят, что наборы имеют 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).

Ответ 3

Я думаю, что его распространенная ошибка, set lookup (или хэш-таблица) не O (1).
из Википедии

В простейшей модели хеш-функция полностью не определена, а таблица не изменяется. Для наилучшего выбора хэш-функции таблица размера n с открытой адресацией не имеет коллизий и содержит до n элементов, с единственным сравнением для успешного поиска, а таблица размера n с цепочкой и k-ключами имеет минимальный максимум (0, kn) и O (1 + k/n) сравнений для поиска. Для худшего выбора хеш-функции каждая вставка вызывает столкновение, а хэш-таблицы вырождаются в линейный поиск, с Ω (k) амортизируются сравнения для каждой вставки и до k сравнений для успешного поиска.

Связано: Является ли хэш-карта Java действительно O (1)?

Ответ 4

У всех нас есть легкий доступ к источнику, где комментарий, предшествующий set_lookkey() говорит:

/* set object implementation
 Written and maintained by Raymond D. Hettinger <[email protected]>
 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)  
{
...

Ответ 5

Чтобы подчеркнуть немного больше разницы между set's и dict's, вот отрывок из разделов комментариев setobject.c, которые уточняют основное отличие множества от dicts.

Случаи для наборов значительно отличаются от словарей, где искали    ключи, скорее всего, будут присутствовать. Напротив, наборы в первую очередь    о тестировании членства, где присутствие элемента неизвестно в    авансовый. Соответственно, реализация набора должна оптимизироваться для обоих    найденный и не найденный случай.

источник github