Сложность времени для добавления элементов в список по сравнению с набором в Python

Question

Почему добавление элементов в набор занимает больше времени, чем добавление элементов в список в Python? Я создал цикл и перебрал более 1000000 элементов, добавил его в список и набор. Список постоянно занимает около 10 секунд против набора, который занимает около 20 секунд.

Answer 1

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

Однако то, что оба являются O (1), не означает, что они занимают одинаковое количество времени:

• Присоединение к списку должно выполняться быстрее, поскольку список реализован в виде динамического массива , поэтому для добавления элемента требуется просто записать этот элемент по правильному индексу (который уже известен),и увеличение длины на 1.
• Напротив, добавление к набору происходит медленнее, поскольку для вычисления индекса, с которого нужно начать поиск, требуется вычислить хэш элемента, а затем тестирование индексов в некоторой последовательности для проверки наличия элемента (путем проверки наличия элемента в индексе, и если да, тоей он равен вставляемому элементу), пока либо не найдет его, либо не найдет пустое место, где должен быть добавлен элемент.

Answer 2

Обе операции O (1) амортизируются сложность по времени.

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

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