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

152

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

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

Daenyth
источник

Ответы:

139

По этой теме :

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

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

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

Джастин этир
источник
18
IIRC, оригинальная setреализация на самом деле была dict с фиктивными значениями, и позже она была оптимизирована.
dan04
1
Разве большой не худший вариант развития событий? Если вы можете найти экземпляр, где время O (n), то это O (n) ... Я сейчас ничего не понимаю из всех этих уроков.
Клаудиу Крянгэ
4
Нет, средний случай - O (1), но худший случай - O (N) для поиска в хэш-таблице.
Джастин Этьер
4
@ClaudiuCreanga это старый комментарий, но только для пояснения: нотация big-O говорит вам о верхних границах скорости роста вещей, но вы можете ограничить верхнюю границу роста средней производительности, а также отдельно верхнюю границу роста наихудшего случая. производительность.
Кирк Бойер
79

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

В статье Википедии говорится, что лучшая сложность времени для хеш-таблицы без изменения размера 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).

unutbu
источник
14

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

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

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

Шей Эрличмен
источник
4
Но для поиска элементов требуется постоянное время: python -m timeit -s "s = set (range (10))" "5 in s" 10000000 циклов, лучшее из 3: 0,0642 usec на цикл <-> python - m timeit -s "s = set (range (10000000))" "5 in s" 10000000 циклов, лучшее из 3: 0.0634 usec на цикл ... и это самый большой набор, который не выбрасывает MemoryErrors
Йохен Ритцель
2
@ THC4k Все, что вы доказали, это то, что поиск X выполняется за постоянное время, но это не значит, что поиск X + Y займет столько же времени, как и O (1).
Шей Эрличмен
3
@intuited: Да, но приведенный выше тестовый прогон не доказывает, что вы можете искать «5» одновременно с поиском «485398» или другого числа, которое может находиться в ужасном пространстве столкновения. Речь идет не о поиске одного и того же элемента в хэше разного размера в одно и то же время (на самом деле это вообще не требуется), а скорее о том, можете ли вы получить доступ к каждой записи за одинаковое количество времени в текущей таблице - что-то, что в принципе невозможно для хеш-таблиц, так как обычно всегда будут конфликты.
Ник Бастин
3
Другими словами, время выполнения поиска зависит от количества сохраненных значений, поскольку это увеличивает вероятность коллизий.
интуитивно
3
@intuited: нет, это неправильно. Когда количество хранимых значений увеличивается, Python автоматически увеличивает размер хеш-таблицы, и частота столкновений остается примерно постоянной. Принимая во внимание равномерно распределенный алгоритм хеширования O (1), тогда поиск по хэш-таблице амортизируется O (1). Возможно, вы захотите посмотреть видеопрезентацию «Мощный словарь» python.mirocommunity.org/video/1591/…
Ли Райан
13

У всех нас есть легкий доступ к источнику , где предыдущий комментарий 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)  
{
...
гимель
источник
2
Этот ответ выиграл бы от подсветки синтаксиса Си . Подсветка синтаксиса комментария в Python выглядит очень плохо.
user202729
Что касается комментария «Это оставляет нам гибрид линейного зондирования и открытой адресации», не является ли линейное зондирование своего рода разрешением коллизий в открытой адресации, как описано в en.wikipedia.org/wiki/Open_addressing ? Поэтому линейное зондирование является подтипом открытой адресации, и комментарий не имеет смысла.
Алан Евангелиста
2

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

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

источник на github

user1767754
источник