Python-множества и словари могут работать за квадратичное время
Python sets and dictionaries can have quadratic-time performance
В Python структуры dict и set принято считать O(1), но на практике это не так. Подобрав ключи с одинаковым хешем, можно получить квадратичное время вставки и проверки: при n=16000 построение множества занимает больше секунды, а при 100000 — 45 секунд. Даже без коллизий словарь на миллионе строк замедляется в девять раз из-за промахов кэша, тогда как fastconstmap остаётся быстрым. Модель O(1) полезна, но не отражает реальность.
Время примерно учетверяется каждый раз, когда n удваивается. Это квадратичное время, а не линейное.
- amiga386
Я заявляю, что это подстава.
import timeit
def test(M,n):
values = [i * M for i in range(1, n + 1)]
s = set(values)
sum(v in s for v in values)
M = (1 << 61) - 1
for n in [1000, 2000, 4000, 8000, 16000]:
print(f"M=2^61-1, {n=:5d} ->", timeit.timeit(lambda: test(M,n), number=3))
for n in [1000, 2000, 4000, 8000, 16000]:
print(f"M=1, {n=:5d} ->", timeit.timeit(lambda: test(1,n), number=3))
По волшебству, когда вы перестаёте использовать BIGINT в качестве элементов множества и просто используете обычные int, никакого квадратичного взрыва не происходит.
M=2^61-1, n= 1000 -> 0.13144792200182565
M=2^61-1, n= 2000 -> 0.48016051898594014
M=2^61-1, n= 4000 -> 2.058760045998497
M=2^61-1, n= 8000 -> 7.843778470996767
M=2^61-1, n=16000 -> 40.01485426299041
M=1, n= 1000 -> 0.000748768012272194
M=1, n= 2000 -> 0.0015750699967611581
M=1, n= 4000 -> 0.003037029004190117
M=1, n= 8000 -> 0.006664915999863297
M=1, n=16000 -> 0.012693285010755062
Время выполнения тратится на хеширование bigint, сравнение кандидатов bigint с эталонными bigint и суммирование bigint. А ещё есть немного поиска по множеству.
- juancn
Обычно это верно для всех распространённых реализаций хеш-таблиц (когда у объектов нет определённого порядка; если он есть, можно получить O(1) в среднем и O(log N) в худшем случае), независимо от языка.
O(1) — это ожидаемый средний случай, который обычно и наблюдается.
Да, O(N^2) теоретически возможно, но если только вы не защищаетесь от какой-то атаки типа отказа в обслуживании, на практике это редко имеет значение.
Тем не менее, если вы можете угадать разумный начальный размер хеш-таблицы, вы можете избежать многих накладных расходов на перехеширование.
- northisup
У Рэймонда Хеттингера есть отличный доклад о том, насколько улучшился dict в Python за эти годы. Так что это супер интересно и, вероятно, в конечном итоге просто сделает встроенный dict ещё лучше.
Урок из доклада: если вы пишете идиоматично, вы выиграете по мере развития языка.
- brudgers
Но можно ли создать хеш-таблицу, которая была бы по-настоящему константной по времени? Нет. По мере роста размера вашей структуры данных требуется всё более медленная память.
При достаточно большом размере, чтобы это было интересно, всё определяется вводом-выводом, а поскольку ввод-вывод медленный, при любом интересном размере производительность — это вопрос подгонки реализации под детали данных {0}.
Инженерия — это тяжёлая работа, а не наивная математика.
[0] Данные могут быть произвольными, но они никогда не случайны. Именно то, что они не случайны, и делает их данными.
- ok123456
Большинство анализов алгоритмов не учитывают иерархии памяти. Не уверен, в чём был смысл этого поста.
Если вас это действительно беспокоит, вычислите эмпирическую roofline для вашей машины.
Кроме того, если цель — указать на иерархии памяти, то это не «квадратичная производительность». Алгоритм не ведёт себя иначе, как только выходит за пределы кэша. Просто затраты становятся больше.