Что делает наборы быстрее, чем списки?

Вики-сценарий python говорит: "Тест на членство с наборами и словарями намного быстрее, O (1), чем поисковые последовательности, O (n). При тестировании" a in b "b должен быть набором или словарем вместо список или кортеж."

Я использую наборы вместо списков всякий раз, когда скорость важна в моем коде, но в последнее время мне интересно, почему наборы намного быстрее, чем списки. Может ли кто-нибудь объяснить или указать мне на источник, который объяснит, что именно происходит за кулисами в python, чтобы сделать наборы быстрее?

Ответ 1

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

Это также причина того, что наборы не сохраняют порядок добавляемых вами объектов.

Обратите внимание, что наборы не быстрее, чем списки в целом - тест принадлежности быстрее для наборов, и поэтому удаляется элемент. Пока вам не нужны эти операции, списки часто бывают быстрее.

Ответ 2

list: представьте, что вы ищете свои носки в вашем шкафу, но вы не знаете, в каком ящике ваши носки, поэтому вам нужно искать ящик с помощью ящика, пока вы их не найдете (или, может быть, вы никогда этого не сделаете). Это то, что мы называем O(n), потому что в худшем случае вы будете смотреть во всех своих ящиках (где n - количество ящиков).

set: Теперь представьте, что вы все еще ищете свои носки в своем шкафу, но теперь вы знаете, в каком ящике ваши носки, скажем, в третьем ящике. Итак, вы будете искать в третьем ящике, а не искать во всех ящиках. Это то, что мы называем O(1), потому что в худшем сценарии вы будете смотреть только в одном ящике.

Ответ 3

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

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

Ответ 4

Python использует hashtables, которые имеют O (1) поиск.

Ответ 5

Пока я пока не оценил какую-либо производительность, связанную с python, я все же хотел бы указать, что списки часто бывают быстрее.

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

Таким образом, наборы не быстрее, чем списки, но только если вам приходится обрабатывать множество элементов.

Ответ 6

Список нужно искать один за другим, где набор или словарь имеет индекс для более быстрого поиска.