prefix_dict = {}
for j in xrange(1,len(a)+1):
    prefix = a[:j]
    prefix_dict[prefix] = len(prefix)
print prefix_dict

Is there any possibility of memory error in the above code?

  • \$\begingroup\$ A memory error? Please explain. \$\endgroup\$ – Joel Cornett Jul 23 '12 at 4:57
  • \$\begingroup\$ @JoelCornett The above code is a part of another code from a contest. when tried on the website it gave a memoryerroer at prefix = a[:j] . \$\endgroup\$ – sachin irukula Jul 23 '12 at 16:02
  • \$\begingroup\$ Oh, I see. What implementation of python are you using? \$\endgroup\$ – Joel Cornett Jul 23 '12 at 17:15
  • \$\begingroup\$ @JoelCornett Sorry, but I lost you "What implementation of python are you using?" do u mean version or anything else?? \$\endgroup\$ – sachin irukula Jul 23 '12 at 17:31
  • \$\begingroup\$ I mean, what are you running this code on? cPython? Jython? Stackless Python? The code as given shouldn't give you an error, so any errors would be platform specific. Are you sending this code to a server? \$\endgroup\$ – Joel Cornett Jul 23 '12 at 18:31

It's hard to tell what is making the error occur without giving us the input, but it's certainly possible the input is too large for the system to store.

prefix_dict will contain len(a) entries so if your input is larger than 32-bit python allows for dictionary size on your machine, then that could be the issue.

I will note that instead of having prefix_dict[prefix] = len(prefix) you could just have prefix_dict[prefix] = j which would stop you from needing to do an extra length calculation each time (not that this would be the cause of the memory issue).

Take a look at the sample output (I modified the print statement and used an example string):

>>> prefix_dict = {}
>>> a = 'hello'
>>> for j in xrange(1,len(a)+1):
        prefix = a[:j]
        prefix_dict[prefix] = len(prefix)
        print j, len(prefix), prefix_dict

1 1 {'h': 1}
2 2 {'h': 1, 'he': 2}
3 3 {'hel': 3, 'h': 1, 'he': 2}
4 4 {'hel': 3, 'h': 1, 'hell': 4, 'he': 2}
5 5 {'hel': 3, 'h': 1, 'hell': 4, 'hello': 5, 'he': 2}

The slice operator in a[:j] creates a copy of the sublist so is perfectly possible that you get a MemoryError.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.