Я видел, как люди говорят, что set
объекты в Python имеют O (1) проверку членства. Как они реализованы внутри, чтобы позволить это? Какую структуру данных он использует? Какие еще последствия имеет эта реализация?
Каждый ответ здесь был действительно поучительным, но я могу принять только один, поэтому я пойду с самым близким ответом на мой оригинальный вопрос. Спасибо всем за информацию!
источник
set
реализация на самом деле былаdict
с фиктивными значениями, и позже она была оптимизирована.Когда люди говорят, что наборы имеют 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)
.источник
Я думаю, что это распространенная ошибка,
set
поиск (или хэш-таблица в этом отношении) не O (1).из википедии
Связанный: действительно ли Java hashmap O (1)?
источник
У всех нас есть легкий доступ к источнику , где предыдущий комментарий
set_lookkey()
говорит:источник
Чтобы еще больше подчеркнуть разницу между
set's
иdict's
, вот выдержка изsetobject.c
разделов с комментариями, в которых разъясняется главное отличие набора от диктов.источник на github
источник