How to build a list faster than .append?

user_14941958 0
Viewed 1113

I have tried this code

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 syntax took a while to build the list. I need another syntax to make a list faster because n is quite large.

append list python performance
3 Answers

You can try Python's extend() method which is faster than append. For large lists, the runtime of the extend() method is 60% faster than the runtime of the append() method. more info

user_121747110

Python works well if you don't instantiate or change object at runtime, so if you create all elements as first step, you can simply reassign values. But this algorithm lack in the [new in X] part, this because this is O(NxM).

So the best solution is create all element before in order to avoid append, and use a better data structure to check if values is altready done, this is a dictionary:

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
user_31946180

Your issue is not with append but with the way you check for existence of a duplicate entry. You can use a set to do that very efficiently.

You can also structure the code as a generator to make it easier to use and reuse:

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)

output:

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]
user_52375600
Related