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

Question

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

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

Answer 1

Согласно этой теме :

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

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

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

Answer 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, <em>независимо от n ,

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

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

Answer 3

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

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

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

Answer 5

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

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

source on github