Какова временная сложность доступа к списку в Python?
Я пытаюсь сделать функцию python как можно быстрее. Предположим, у меня есть простой список, и я звоню primes[i] n раз по одному и тому же i.
У меня есть интуиция, что при определенном значении n становится проще сохранить значение primes[i] в переменной.
Я сделал несколько попыток, сравнив две следующие реализации, и не могу понять, какая из них самая быстрая. Похоже, временной доступ к primes[i] зависит от многих факторов.
1-я реализация
while n != 1:
p = primes[i]
if n % p == 0:
n = n // p
factorization.append(p)
else:
i += 1
2-я реализация
while n != 1:
if n % primes[i] == 0:
n = n // primes[i]
factorization.append(primes[i])
else:
i += 1
Есть ли какое-то правило, чтобы узнать, из какого количества вызовов становится интересно сохранить значение элемента списка в переменной?
Я не могу понять, какой из них самый быстрый. Вы проводили какой-либо бенчмаркинг?
Ответы 2
Доступ к primes[i] осуществляется в постоянное время, O(1). Это означает, что время, необходимое для чтения primes[i], не увеличивается по мере того, как primes становится больше, и что оно не увеличивается, когда i становится больше.
С точки зрения непрофессионала: это чертовски быстро!
Опять же, доступ к локальной переменной p по-прежнему быстрее, чем доступ к primes[i], потому что последний должен искать и вызывать __getitem__ реализацию объекта primes. Поэтому кеширование значения в локальной переменной вместо двойного поиска в списке немного быстрее.
С другой стороны, забота о незначительном повышении скорости бессмысленна по сравнению с уменьшением сложности алгоритма. Что касается проблемы поиска простых чисел, вам следует сосредоточиться на поиске умного алгоритма, а не на улучшении времени доступа к встроенным спискам.
Попробуйте использовать эталон
import time
start = time.time()
while n != 1:
p = primes[i]
if n % p == 0:
n = n // p
factorization.append(p)
else:
i += 1
end = time.time()
print(end - start)
сделайте то же самое для реализации 2 и сравните.
А также попробуйте сделать это в google colab или любой другой внешней машине для лучших результатов.
Вся идея списка заключается в том, что он имеет постоянный доступ во времени.