Is there any way to avoid this memory error?

Question

I am currently working on Project Euler issues, and so far I have come up with this code for the issue.

from itertools import combinations import time def findanums(n): l = [] for i in range(1, n + 1): s = [] for j in range(1, i): if i % j == 0: s.append(j) if sum(s) > i: l.append(i) return l start = time.time() #start time limit = 28123 anums = findanums(limit + 1) #abundant numbers (1..limit) print "done finding abundants", time.time() - start pairs = combinations(anums, 2) print "done finding combinations", time.time() - start sums = map(lambda x: x[0]+x[1], pairs) print "done finding all possible sums", time.time() - start print "start main loop" answer = 0 for i in range(1,limit+1): if i not in sums: answer += i print "ANSWER:",answer 

When I run this, I fire a MemoryError .

Track:

 File "test.py", line 20, in <module> sums = map(lambda x: x[0]+x[1], pairs) 

I tried to prevent this by disabling garbage collection from what I was able to get from Google, but to no avail. Am I approaching this wrong? In my head, it looks like the most natural way to do it, and I'm at a loss at this point.

SIDE NOTE. I use PyPy 2.0 Beta2 (Python 2.7.4) because it is much faster than any other python implementation I used and Scipy / Numpy is above my head, as I am still just starting to program and I don’t have an engineering or strong mathematical background.

Answer 1

As Kevin mentions in the comments, your algorithm may not be correct, but in any case, your code is not optimized.

When using very large lists, generators are usually used, there is a well-known, excellent Stackoverflow answer explaining the concepts of yield and generator - What does the do keyword do in output in Python?

The problem is that your pairs = combinations(anums, 2) does not generate a generator , but generates a large object that consumes a lot more memory.

I changed my code to this function, since you repeat the assembly only once, you can be lazy to evaluate the values:

 def generator_sol(anums1, s): for comb in itertools.combinations(anums1, s): yield comb 

Now instead of pairs = combinations(anums, 2) , which generates a large object. Using:

 pairs = generator_sol(anums, 2) 

Then instead of using lambda I would use another generator :

 sums_sol = (x[0]+x[1] for x in pairs) 

Another tip, you better look at xrange , which is more suitable, it does not generate a list, and xrange object which is more efficient in many cases (for example, here).

Answer 2

Let me suggest you use generators . Try changing this:

 sums = map(lambda x: x[0]+x[1], pairs) 

to

 sums = (a+b for (a,b) in pairs) 

Ofiris solution is also fine, but implies that itertools.combinations returns a list when it is erroneous. If you are going to continue to solve the problems of project eulers , see the itertools documentation .

Answer 3

The problem is that anums are big - about 28,000 elements. therefore pairs should be 28000 * 28000 * 8 bytes = 6 GB. If you used numpy, you can use anums as a numpy.int16 array, in which case the result pairs will be 1.5 GB - more manageable:

 import numpy as np #cast anums = np.array([anums],dtype=np.int16) #compute the sum of all the pairs via outer product pairs = (anums + anums.T).ravel()