motatoes's blog

A question about memory usage in Python3
By motatoes, history, 7 years ago, In English

I'm trying to solve the python indentation problem in round 455C. My submission is receiving a memory limit exceeded.

Memory limit is: 256 * 1024 * 1024 = 268435456 bytes

In my code I am using at most a 5000*5000 matrix to hold the dp values and this will occupy ~ 200000064 bytes

I am also using a string to hold the program and it will occupy: 5049 bytes

I am using about 6 int variables in my program and then will occupy: 6 * 28 = 168 bytes

so in total: 200005281 bytes

Or 191 MB. So According to my calculations I am still bellow 200 MB, but in CF I am exceeding 256MB. Is there something that I am missing in the memory computation? Is the python interpreter size counted within the memory computation also?

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Because in Python not all elements have to be of the same type, Python has to keep some additional information about the elements. Usually Python is considered a language which uses lots of memory because of it's flexibility.

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

One point: You are creating the matrix by appending which can lead to higher memory usage, read this: https://stackoverflow.com/questions/7247298/size-of-list-in-memory

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    hmm .. I have tried preallocating the memory without using append but it doesn't seem to make a difference

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Okay, another idea (which also fits that this happens only after 1.5s): The values grow large and python starts switching to arbitrary precision integers whose size is unbounded. Maybe you can fix this by taking modulo earlier (in every step).

      → Reply