Что делает наборы быстрее, чем списки?
Вики Python говорит: "Тестирование членства с наборами и словарями гораздо быстрее, O(1), чем поиск последовательности, O(n). При тестировании"a в b", b должен быть набор или словарь вместо списка или кортеж ".
Я использовал наборы вместо списков всякий раз, когда в моем коде важна скорость, но в последнее время я удивляюсь, почему наборы намного быстрее, чем списки. Может ли кто-нибудь объяснить или указать мне источник, который объяснит, что именно происходит за кулисами в python, чтобы сделать наборы быстрее?
9 ответов
Наборы реализованы с использованием хеш-таблиц. Всякий раз, когда вы добавляете объект к набору, положение в памяти set объект определяется с использованием хеша объекта, который будет добавлен. При тестировании на членство все, что нужно сделать, это в основном посмотреть, находится ли объект в позиции, определенной его хешем, поэтому скорость этой операции не зависит от размера набора. Для списков, напротив, нужно искать весь список, который будет становиться медленнее по мере роста списка.
Это также причина того, что наборы не сохраняют порядок объектов, которые вы добавляете.
Обратите внимание, что наборы не быстрее, чем списки в целом - проверка членства выполняется быстрее для наборов, и поэтому удаляется элемент. Пока вам не нужны эти операции, списки часто бывают быстрее.
list Представьте, что вы ищете свои носки в своем шкафу, но не знаете, в каком ящике находятся ваши носки, поэтому вам придется искать их по ящикам, пока вы их не найдете (или, возможно, никогда не найдете). Это то, что мы называем O(n), потому что в худшем случае, вы будете смотреть во всех своих ящиках (где n это количество ящиков).
set Теперь представьте, что вы все еще ищете носки в своем шкафу, но теперь вы знаете, в каком ящике находятся ваши носки, скажем, в третьем. Таким образом, вы просто будете искать в третьем ящике, а не искать во всех ящиках. Это то, что мы называем O(1) потому что в худшем случае вы будете смотреть только в одном ящике.
Я думаю, что вам нужно хорошенько взглянуть на книгу о структурах данных. По сути, списки Python реализованы в виде динамических массивов, а наборы реализованы в виде хеш-таблиц.
Реализация этих структур данных дает им принципиально разные характеристики. Например, хеш-таблица имеет очень быстрое время поиска, но не может сохранить порядок вставки.
list: Представьте, что вы ищете ручку, но не знаете, в каком ящике находится ручка, поэтому вам нужно искать ящик за ящиком, пока вы не найдете ее (или, может быть, вы никогда не найдете). Это то, что мы называем O(n), потому что в худшем случае вы заглянете во все свои ящики (где n - количество ящиков).
set: Теперь представьте, что вы все еще ищете свою ручку, но теперь вы знаете, в каком ящике находится ваша ручка, скажем, в 8-м ящике. Таким образом, вы будете искать только в 8-м ящике, а не по всем ящикам. Это то, что мы называем O(1), потому что в худшем случае вы будете искать только в одном ящике.
По сути, списки Python реализованы какdynamic arraysи наборы реализованы какhash tables.
Хотя я пока не измерял ничего, касающегося производительности в python, я все же хотел бы отметить, что списки часто бывают быстрее.
Да, у вас есть O(1) против O(n). Но всегда помните, что это дает информацию только об асимптотическом поведении чего-либо. Это означает, что если ваш n очень высокий O(1) всегда будет быстрее - теоретически. Однако на практике n часто должно быть намного больше, чем будет ваш обычный набор данных.
Таким образом, наборы не быстрее, чем списки как таковые, но только в том случае, если вам приходится обрабатывать много элементов.
В основном, зависит от выполняемой вами операции...
* Для добавления элемента - тогда набору не нужно перемещать какие-либо данные, и все, что ему нужно сделать, это вычислить значение хеш-функции и добавить его в таблицу. Для вставки списка потенциально есть данные, которые нужно переместить.
* Для удаления элемента - все, что нужно сделать набору, - это удалить хеш-запись из хеш-таблицы, для списка потенциально необходимо перемещать данные (в среднем 1/2 данных.
* Для поиска (т.е. оператора in) - набору просто нужно вычислить хеш-значение элемента данных, найти это хеш-значение в хеш-таблице, и если оно есть - тогда бинго. Для списка поиск должен искать каждый элемент по очереди - в среднем 1/2 всех терминов в списке. Даже для многих тысяч предметов поиск набора будет намного быстрее.
На самом деле наборы - это не скорость, чем списки в каждом сценарии. Обычно списки быстрее, чем наборы. Но в случае поиска элемента в наборе это скорость, потому что наборы реализованы с использованием хеш-таблиц. Таким образом, в основном ему не нужно искать полный набор, поэтому временная сложность в среднем составляет O(1). Списки используют динамические массивы, и для поиска необходимо искать в полном массиве. Так что требуется O(n). n - размер списка.
Итак, наконец, мы видим, что в некоторых случаях наборы лучше, а в некоторых - списки. Мы должны выбрать подходящую структуру данных в соответствии с нашей задачей.
Список должен быть найден один за другим, где набор или словарь имеет индекс для более быстрого поиска.