CODEWITHSUNDEEP
arraysperformancepython-3.x
Jesus Sono
Jesus Sono

Reputation: 78

Create a list with millions of elements

I need to create and work with lists with 2**30 elements, but It's to slow. Is there any form to increase the speed?

My code:

sup = []

for i in range(2**30):
    sup.append([i,pow(y,i,N)])

pow(y,i,n) == y**i*mod(N), modular exponentiation

I tried to use list comprehensions but isn't enough.

Upvotes: 1

Views: 1468

Answers (2)

Copperfield
Copperfield

Reputation: 8510

Going by your comment and complementing the answer of GhostCat, go directly for the data you are looking for, for example like this

>>> from collections import defaultdict
>>> y = 2
>>> N = 10
>>> data = defaultdict(list)
>>> for i in range(100):
        data[pow(y,i,N)].append(i)


>>> for x in data.items():
        x


(8, [3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, 83, 87, 91, 95, 99])
(1, [0])
(2, [1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97])
(4, [2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 74, 78, 82, 86, 90, 94, 98])
(6, [4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96])
>>>

or more specifically, as you need a random sample go for it from the start and don't waste time producing a gazillion stuff you would not need, for example

>>> import random
>>> random_data = defaultdict(list)
>>> for i in random.sample(range(2**30), 20):
        random_data[pow(2,i,10)].append(i)


>>> for x in random_data.items():
        x


(8, [633728687, 357300263, 208747091, 456291987, 1028949643, 23961003, 750842555])
(2, [602395153, 215460881, 144481457, 829193705])
(4, [752840814, 26689262])
(6, [423520476, 969809132, 326786996, 736424520, 929123176, 865279408, 338237708])
>>>

and depending of what you do with those i later on, you can instead try a more mathematical approach to uncover the underplaying patter that produce an i for which yi mod N is the same and that way you can produce as many i as you need for that particular modular class.

Which for this example is easy, it is

2i = 8 (mod 10) for all i=3 (mod 4) -> range(3,2**30,4)

2i = 2 (mod 10) for all i=1 (mod 4) -> range(1,2**30,4)

2i = 4 (mod 10) for all i=2 (mod 4) -> range(2,2**30,4)

2i = 6 (mod 10) for all i=0 (mod 4) -> range(4,2**30,4)

2i = 1 (mod 10) for i=0

Upvotes: 0

GhostCat
GhostCat

Reputation: 140457

Different approach: why do you want to store those numbers in a list?

You have your formula right there; whenever some piece of code needs sup[i]; you just compute pow(y,i,N).

In other words: instead of storing values within a list; just compute them when you need them.

Edit: as it seems that you have good reasons to store that data in an array; I would then say: use the appropriate tool then.

Meaning: instead of doing computing intense things directly with python, you rather look into the numpy framework. That framework is designed for exactly such purposes. Beyond that, I would also look in the way you are storing/preparing your data. Example: you mention to later look for identical entries in that array. I am wondering if that would meant you should use a dictionary instead of a list; or did you really intend do check 2**30 entries each time you look for equal pow values?

Upvotes: 3

Related Questions