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

Question

Я видел, что люди говорят, что set Объекты в Python имеют O (1) проверять членства. Как они реализуются внутри, чтобы позволить этому? Какую структуру данных это использует? Какие другие последствия имеют эту реализацию?

Каждый ответ здесь был действительно просвещен, но я могу принять только один, поэтому я пойду с ближайшим ответом на мой оригинальный вопрос. Спасибо всем за информацию!

Answer 1

Согласно с эта нить:

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

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

Если вы настолько склонны, вы даже можете просматривать Cpython исходный код для набора который, по словам Ахим Домма, в основном вырезанная и паста из dict реализация.

Answer 2

Когда люди говорят, что наборы имеют o (1) проверять членства, они говорят о средний кейс. в худший Корпус (когда все хешитые значения сталкиваются), проверка членства - это O (n). Увидеть Python Wiki вовремя сложность.

То Статья Википедии говорит лучший случай Сложность времени для хеш-стола, который не изменяет изменение изменений O(1 + k/n). Отказ Этот результат не применяется непосредственно на наборы Python, поскольку наборы Python используют таблицу HASH, который изменяет изменение.

Немного дальше на статье Википедии говорит, что для средний случай, и предполагая простую равномерную функцию хеширования, момент сложности O(1/(1-k/n)), куда k/n можно ограничить постоянной c<1.

Big-O относится только к асимптотическому поведению как n → ∞. Поскольку K / N можно ограничить постоянной, C <1, Независимо от Н.,

O(1/(1-k/n)) не больше, чем O(1/(1-c)) который эквивалентно O(constant) = O(1).

Так предполагая равномерную простую хеширование, на средний, Проверка членства на наборы Python O(1).

Answer 3

Я думаю, что это распространенная ошибка, set поиск (или hashtable в этом отношении) не о (1).
из Википедии

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

Связанный: Является ли Java Hashmap действительно O (1)?

Answer 4

У всех нас легкий доступ к источник, где комментарий предшествующий 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)  
{
...

Answer 5

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

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

источник дальше гадость