memory error in python

Question

Traceback (most recent call last):
File "/run-1341144766-1067082874/solution.py", line 27, in 
main()
File "/run-1341144766-1067082874/solution.py", line 11, in main
if len(s[i:j+1]) > 0:
MemoryError
Error in sys.excepthook:
Traceback (most recent call last):
File "/usr/lib/python2.7/dist-packages/apport_python_hook.py", line 64, in apport_excepthook
from apport.fileutils import likely_packaged, get_recent_crashes
File "/usr/lib/python2.7/dist-packages/apport/__init__.py", line 1, in 
from apport.report import Report
MemoryError

Original exception was:
Traceback (most recent call last):
File "/run-1341144766-1067082874/solution.py", line 27, in 
main()
File "/run-1341144766-1067082874/solution.py", line 11, in main
if len(s[i:j+1]) > 0:
MemoryError

The above errors appeared when I tried to run the following program. Can someone explain what is a memory error, and how to overcome this problem? . The program takes strings as input and finds all possible sub strings and creates a set(in a lexicographical order) out of it and it should print the value at the respective index asked by the user otherwise it should print 'Invalid'

def main():
    no_str = int(raw_input())
    sub_strings= []
    for k in xrange(0,no_str):
        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])
    sub_strings = list(set(sub_strings))
    sub_strings.sort()
    queries= int(raw_input())
    resul = []
    for i in xrange(0,queries):
        resul.append(int(raw_input()))
    for p in resul:
        try:
            print sub_strings[p-1]
        except IndexError:
            print 'INVALID'


if __name__ == "__main__":
   main()

Frication

You are out of memory: docs.python.org/library/exceptions.html – Decasyllable

I think you might be running out of memory, could you post your input data? – Elver

@GustavLarsson I don't no the input data, its a problem from interviewstreet. – Frication

@kratos what is your expected output for string abcd? – Pistareen

if the input is 2,aab,aac,3,3,8,23 the the output should be aab, c, INVALID – Frication

@kratos: When I run your example with those inputs, I get that output – Adrianaadriane

@kratos interviewstreet's link of the problem? – Pistareen

@kratos: It is also really annoying and confusing to see the program having like 7 input statements with no text prompt. I don't even know whats going on. – Adrianaadriane

@AshwiniChaudhary interviewstreet.com/challenges/dashboard/#problem/4efa210eb70ac – Frication

@Adrianaadriane code is working for small inputs, i think for larger inputs its showing memory error, and btw sorry for the inputs without any info, I have provided the info of the problem in the above comment – Frication

@kratos you should try itertools , see my solution below. – Pistareen

A note to anyone encountering this for the first time; may be worth closing the terminal and re-opening. That can free up enough RAM to do what you need. – Alamo

Answer 1

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) # don't 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.

Fontanez

Answer 2

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

Indeterminate

quick instructions for switching in windows, - detect if you are running 32-bit stackoverflow.com/questions/1842544 - download a 64 bit version from python.org, and install it - update your PATH variable to the new installation – Reisfield

Answer 3

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 don't 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 don't 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 don't pre-compute all possible sub-strings. Instead, you could simply compute the substring that are asked.

Garett

I already know that, a bit more explanation on why this is happening in this case would be more helpful. – Frication

I was simply trying to provide a clear answer to the title of your question, in case someone else finds it looking for MemoryError and Python. – Garett

@kratos You asked for it: "Can someone explain what is a memory error," – Fontanez

Answer 4

Either there's a error in your code or you are out of memory, you can upgrade it or for quick solution try increasing your virtual memory.

1. Open My Computer
2. Right click and select Properties
3. Go to Advanced System Settings
4. Click on Advance Tab
5. Click on settings under Performance
6. Click on Change under Advance Tab
7. Increase the memory size, that will increase virtual memory size.

If there's issue with your memory space, it will be resolved now!

Teem

Answer 5

you could try to create the same script that popups that error, dividing the script into several script by importing from external script. Example, hello.py expect an error Memory error, so i divide hello.py into several scripts h.py e.py ll.py o.py all of them have to get into a folder "hellohello" into that folder create init.py into init write import h,e,ll,o and then on ide you write import hellohello

Nadenenader

Answer 6

Check program with this input: abc. If you got something like ab ac bc abc, then the program works well and you just need more RAM. Otherwise, the program is incorrect.

Mesics

Please review the accepted answer from seven years ago for an explanation of what addressed the issue—and addresses issues similar to this. Just because a program works with a small amount of data and fails with more complex data doesn’t mean that the program “works well” or that the OP needs more RAM. As mentioned in the existing answers, this can be caused by inefficient code—or even just using the 32-bit version of the interpreter, which restricts the available RAM (independent of how much is actually installed), – Lacunar

Answer 7

You are clearly out of memory. I don’t know for sure, but maybe nested loops aren’t a good idea. You can see https://docs.python.org/3/library/exceptions.html for more info. Also, how large a string were you entering? Try with a string literal instead of raw_input(). Maybe try on another device or a fresh Linux install or something. Also maybe try python 3.

Coverup

Answer 8

Using python 64 bit solves lot of problems.

Sike

Perhaps it'd be useful to other users to say why it solves problems? – Hagride