Python giving a memory error

Question

hi everyone im very new to python.i was trying to solve this problem from a coding site online

A=3, B= 5
Table of A = 3 , 6 , 9 , 12 ,15 ,18 and so on
Table of B =5 , 10 , 15 , 20 and so on
After Merging : 3, 5, 6, 9 ,10 , 12 ,15 ,15, 18, 20 and so on
Remove Duplicates : 3 , 5 , 6, 9 , 10 , 12 , 15 , 18 , 20 and so on
For N= 2 , 2nd element of the supertable is 5

the problem is i can get the answers for a finite range of A and B but when i do it for 10^9th element i get a memory error.

from array import *
import itertools
array1=[]
array2=[]
A=int(input())
B=int(input())
N=int(input())
for i in range(0,10**9):
    try:
        array1.append(i+1 * A)
    except MemoryError :
        break 

for j in range(0,10**9):
    try:
        array2.append(j+1 * B)
    except MemoryError :
        break
filter(None ,array1)
filter(None ,array2)
array3 = array1 + array2
array3 = sorted(set(array3))
print (array3[N])

Traceback (most recent call last):
File "C:/Users/Clinton D/Desktop/supertables.py", line 21, in
array3 = array1 + array2 MemoryError

Answer 1

If you really need to use this large data set, you should use pandas or numpy to process it.

But if you're trying to solve a coding golf, try to use a smaller data set to test your approach. Anyway, you may consider use iterators instead list, and use iterator.chain to join iterators.

from itertools import chain

A=int(input())
B=int(input())
N=int(input())

array_a = (i*A for i in range(10**4))
array_b = (i*B for i in range(10**4))
array_c = chain(array_a, array_b)
c = sorted(set(array_c))

print(c[N])

Answer 2

As has been pointed out, you are making some very big lists in memory. I also found it surprising that you're actually expecting MemoryError! A part of your problems will be solved by using list comprehensions, those are ways to tell Python how to build a list without having to use a for-loop and append. For example, a list comprehension for the squares of the first 100 numbers can be written as:

squares = [x*x for x in xrange(100)]

A list comprehension consists of two parts: the element definition and the iterable set to which it is applied. In the previous example, x*x is the element definition and for x in xrange(100) is the iterable part.

Now back to your problem. The second thing that strikes me from your code is the use of the array module, without specifically needing anything from it.

Finally, using filter(None, [...]) is usefull to eliminate every element which evaluates to False, which for numbers is 0. In your example, there's no such element in any of the list, unless either A or B are 0.

So your script should end up along this lines:

A = int(input())
B = int(input())
N = int(input())

array1 = []
array2 = []
if A:
    array1 = [i * A for i in xrange(1, 10**7 + 1)]
if B:
    array2 = [i * B for i in xrange(1, 10**7 + 1)]

array1.extend(array2)
del(array2)  # not entirely necessary, if you have 128GB RAM or more...
array1 = sorted(set(array1))
print array1[N-1]

Something that had been in the back of my mind, until I completley hung up my computer testing your code, is that you could use generators to solve this. I am now entirely sure of it. Also, why would you want between one and two billion elements?

I tihnk your problem here is not something related to Python or lack of memory, but an awful algorithm for calculating this values -- which I simply made slightly less awful.

Edit:

• @acushner noticed the squares list was simply named list and that could interfere with Python list builtin.
• Some typos here and there.
• I had posted a slightly incorrect version of the script, fixed now.

Answer 3

you don't want to create the whole list ahead of time (i.e., why create all these values if you only want to find the Nth one?)

what you want to do is something like this:

def f(n):
    vals = (x for x in xrange(1, 10**9) if (x % 3 == 0) or (x % 5 == 0))
    for _ in xrange(n - 1):
        vals.next()
    return vals.next()

you're only iterating through things here, so there's no big list creation.