Как реализуется set ()?

Question

Как реализуется set ()?

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

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

705 5

python set data-structures cpython

5 ответов:

Comments

Ничего не найдено.

Justin Ethier · Accepted Answer · 2017-07-11 15:29:28

по данным этой теме:

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

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

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

unutbu · Accepted Answer · 2010-10-17 11:24:06

когда люди говорят, что наборы имеют O (1) проверку членства, они говорят о в среднем случае. В хуже case(когда все хэшированные значения сталкиваются) проверка членства-O (n). Смотрите Python wiki по сложности времени.

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

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

Big-O относится только к асимптотическому поведению как n → ∞. Так как k / n может быть ограничено константой, c независимо от n,

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

Итак, предполагая равномерное простое хэширование, на в среднем, проверка членства для наборов Python - это O(1).

Shay Erlichmen · Accepted Answer · 2017-05-23 15:26:21

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

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

по теме: является ли Java hashmap действительно O (1)?

gimel · Accepted Answer · 2017-07-13 07:41:20

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

user1767754 · Accepted Answer · 2017-11-15 10:58:10

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

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

источник github