Как создать список быстрее, чем .append?

#python #list #performance #append

#питон #Список #Производительность #добавить

Вопрос:

Я пробовал этот код

 p = 1000003
q = 400003
M = p*q  
n = 84480
X = [6225**2%M]
new = X[0]**2%M
i = 1
while new not in X and len(X) < n:
         X.append(new)
         new = X[i]**2%M
         i  = 1

.append синтаксису потребовалось некоторое время, чтобы составить список. Мне нужен другой синтаксис, чтобы сделать список быстрее, потому n что он довольно большой.

Ответ №1:

Вы можете попробовать extend() метод Python, который быстрее, чем append . Для больших списков время выполнения extend() метода на 60% быстрее, чем время выполнения append() метода. Подробная информация

1. Как расширение может улучшить производительность? он добавляет только один элемент на шаг, поэтому extend будет работать как append

2. @Glauco метод extend() должен быть быстрее для больших размеров списка, потому что Python может добавлять элементы в список в пакетном режиме, а не вызывать один и тот же метод снова и снова.

3. Я согласен с вашей точкой зрения, но в этом алгоритме он вставляет только один элемент за раз

4. @Glauco Он сказал в своем вопросе: «Мне нужен другой синтаксис, чтобы сделать список быстрее, потому что n довольно большой». так вот почему я посоветовал ему попытаться extend() это сделать .

Ответ №2:

Python хорошо работает, если вы не создаете экземпляр или не изменяете объект во время выполнения, поэтому, если вы создаете все элементы в качестве первого шага, вы можете просто переназначить значения. Но этого алгоритма не хватает в части [new in X], потому что это O (NxM).

Таким образом, лучшее решение — создать все элементы до, чтобы избежать добавления, и использовать лучшую структуру данных, чтобы проверить, готовы ли значения, это словарь:

 p = 1000003
q = 400003
M = p*q  
n = 84480
X = [6225**2%M]*n
Xd = {X[0]:None}
new = X[0]**2%M
i = 1
while new not in Xd and i<n:
         X[i] = new
         Xd[new]=None
         new = X[i]**2%M
         i  = 1



Original:
CPU times: user 47.5 s, sys: 13.2 ms, total: 47.5 s
Wall time: 49.5 s

Optimized:
CPU times: user 66.9 ms, sys: 9 µs, total: 66.9 ms
Wall time: 103 ms

1. я вижу, дело в том, что список построен в самом начале. Большое спасибо, брат

2. но теперь у меня есть 1 список и 1 кортеж, разве это не займет некоторое время?

3. Это не кортеж, а словарь, и он очень быстр для работы. (x в [] принимает O (n)) ( x в {} принимает O (1)) так что это второе улучшение.

Ответ №3:

Ваша проблема не в append, а в том, как вы проверяете наличие дублирующейся записи. Вы можете использовать set, чтобы сделать это очень эффективно.

Вы также можете структурировать код как генератор, чтобы упростить его использование и повторное использование:

def modSquare(N,M,maxCount): seen = set() for _ in range(maxCount): N = N**2%M if N in seen: break yield N seen.add(N)

вывод:

p = 1000003 q = 400003 M = p*q n = 84480 X = list(modSquare(6225,M,n)) print(len(X)) # 84480 print(X[:3],"...",X[-3:]) # [38750625, 395175256848, 7948406859] ... [166985992167, 267628307961, 385065196277]