memory error in python

memory error in python

If you get an unexpected MemoryError and you think you should have plenty of RAM available, it might be because you are using a 32-bit python installation.

The easy solution, if you have a 64-bit operating system, is to switch to a 64-bit installation of python.

The issue is that 32-bit python only has access to ~4GB of RAM. This can shrink even further if your operating system is 32-bit, because of the operating system overhead.

You can learn more about why 32-bit operating systems are limited to ~4GB of RAM here: https://superuser.com/questions/372881/is-there-a-technical-reason-why-32-bit-windows-is-limited-to-4gb-of-ram

This one here:

s = raw_input()
a=len(s)
for i in xrange(0, a):
    for j in xrange(0, a):
        if j >= i:
            if len(s[i:j+1]) > 0:
                sub_strings.append(s[i:j+1])

seems to be very inefficient and expensive for large strings.

Better do

for i in xrange(0, a):
    for j in xrange(i, a): # ensures that j >= i, no test required
        part = buffer(s, i, j+1-i) # dont duplicate data
        if len(part) > 0:
            sub_Strings.append(part)

A buffer object keeps a reference to the original string and start and length attributes. This way, no unnecessary duplication of data occurs.

A string of length l has l*l/2 sub strings of average length l/2, so the memory consumption would roughly be l*l*l/4. With a buffer, it is much smaller.

Note that buffer() only exists in 2.x. 3.x has memoryview(), which is utilized slightly different.

Even better would be to compute the indexes and cut out the substring on demand.

memory error in python

A memory error means that your program has ran out of memory. This means that your program somehow creates too many objects.

In your example, you have to look for parts of your algorithm that could be consuming a lot of memory. I suspect that your program is given very long strings as inputs. Therefore, s[i:j+1] could be the culprit, since it creates a new list. The first time you use it though, it is not necessary because you dont use the created list. You could try to see if the following helps:

if  j + 1 < a:
    sub_strings.append(s[i:j+1])

To replace the second list creation, you should definitely use a buffer object, as suggested by glglgl.

Also note that since you use if j >= i:, you dont need to start your xrange at 0. You can have:

for i in xrange(0, a):
    for j in xrange(i, a):
        # No need for if j >= i

A more radical alternative would be to try to rework your algorithm so that you dont pre-compute all possible sub-strings. Instead, you could simply compute the substring that are asked.