Почему конструктор set () работает медленнее, чем list ()

Question

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

Я использую Python 3.7.5 [MS C v.1916 64 бит (AMD64)], Windows 10 , на момент написания этой статьи (8 ^th March).

#No significant changed observed.
timeit set(range(<b>10</b>))
<b>517 ns</b> ± 4.91 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
timeit list(range(<b>10</b>))
<b>404 ns</b> ± 4.71 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Когда размер увеличивается, set() становится очень медленным, чем list()

# When size is 100
timeit set(range(<b>100</b>))
2.13 <b>µs</b> ± 12.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
timeit list(range(<b>100</b>))
934 <b>ns</b> ± 10.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

# when size is ten thousand.
timeit set(range(<b>10000</b>))
<b>325 µs</b> ± 2.37 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
timeit list(range(<b>10000</b>))
<b>240 µs</b> ± 2.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

# When size is one million.
timeit set(range(<b>1000000</b>))
<b>86.9 ms</b> ± 1.78 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
timeit list(range(<b>1000000</b>))
<b>37.7 ms</b> ± 396 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Оба они принимают O(n) асимптотически. Когда дубликатов нет, set(...) приблизительно не должно быть list(...).

К моему удивлению установить понимание и список понимания не показывает те огромные отклонения вроде set() и list() показали.

# When size is 100. 
timeit {i for i in range(<b>100</b>)}
<b>3.96 µs</b> ± 858 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
timeit [i for i in range(<b>100</b>)]
<b>3.01 µs</b> ± 265 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

# When size is ten thousand.
timeit {i for i in range(<b>10000</b>)}
<b>434 µs</b> ± 5.11 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
timeit [i for i in range(<b>10000</b>)]
<b>395 µs</b> ± 13.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

# When size is one million.
timeit {i for i in range(<b>1000000</b>)}
<b>95.1 ms</b> ± 2.03 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
timeit [i for i in range(<b>1000000</b>)]
<b>87.3 ms</b> ± 760 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Answer 1

Почему они должны быть одинаковыми? Да, они оба O (n), но set() необходимо га sh каждого элемента и необходимо учитывать, что элементы не являются уникальными. Это приводит к более высокой фиксированной стоимости на элемент .

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

Если вы хотите лучше понять Big O, я настоятельно рекомендую Введение Неда Батчелдера в тему .

При отсутствии дубликатов не следует устанавливать (...) приблизительно равный списку (...).

Нет, они не равны, потому что list() не имеет sh. То, что дубликатов нет, не имеет значения.

К моему удивлению, набор и понимание списка не показали таких огромных отклонений, как set() и list().

Дополнительные l oop, выполняемые интерпретатором Python l oop, добавляют накладные расходы, которые преобладают над затраченным временем. Более высокая фиксированная стоимость, равная set(), становится менее заметной.

Существуют и другие различия, которые могут иметь значение:

• Учитывая последовательность с известным length, list() может предварительно выделить достаточно памяти для размещения этих элементов. Наборы не могут предварительно выделить, так как они не могут знать, сколько будет дубликатов. Предварительное выделение позволяет избежать (амортизированной) стоимости необходимости динамически увеличивать список.
• Список и заданные значения добавляют по одному элементу за раз, поэтому объекты списка не могут быть предварительно распределены, что немного увеличивает фиксированную стоимость для каждого элемента. .