Python memory - The memory limit exceeded for Python code

Question

I got this problem while I was solving a problem of self crossing. It's like the snake game.

Given x = [2, 1, 1, 2], we start from 0, and then we go up for 2, go left for 1, go right for 1 and go down for 2. The goal is to calculate if it will self cross or not. As the given steps are always integers, I thought about using a matrix and every time when it get through a point, I set the point to 1. Like this I could check if the point has been visited or not.

I think in this way, all the memory that Python will make is just the assignment of the matrix. That's why I don't understand when the input x is huge, and why it says "memory out of limit". For me, I think the memory is the same as the matrix has been initiated before.

How can I fix this?

class Solution(object):

    def isSelfCrossing(self, x):
        """
        :type x: List[int]
        :rtype: bool
        """
        m = [[0 for j in xrange(1000)] for j in xrange(1000)]
        m[0][0] = 1
        a, b = 0, 0
        flag = 0
        for i in x:
            flag = (flag + 1) % 4
            if flag == 1:
                for temp in xrange(1, i+1):
                    b += 1
                    if m[a][b] != 0:
                        return True
                    else: m[a][b] = 1
            elif flag == 2:
                for temp in xrange(1, i+1):
                    a -= 1
                    if m[a][b] != 0:
                        return True
                    else: m[a][b] = 1
            elif flag == 3:
                for temp in xrange(1, i+1):
                    b -= 1
                    if m[a][b] != 0:
                        return True
                    else: m[a][b] = 1
            else:
                for temp in xrange(1, i+1):
                    a += 1
                    if m[a][b] != 0:
                        return True
                    else: m[a][b] = 1
        return False

That code should only use around 4MB on 32 bit Python. How are you calling that function? And why is it in a class? — PM 2Ring, Mar 05 '16 at 10:27
It's in a class because I'm solving the problem here: https://leetcode.com/problems/self-crossing/ When I submit my answer, there is a memory limit exceed problem and I really don't know why for small test sets there isn't a memory limit exceed problem but for large sets there is a memory limit exceed problem. — Elona Mishmika, Mar 11 '16 at 09:50
You still didn't tell us _how_ you're calling `isSelfCrossing`. The reason that I asked for that info is that I _suspected_ that you were inadvertently creating multiple instances of the Solution class. BTW, you can safely initialize `m` using `[[0] * 1000 for j in xrange(1000)]`, but I seriously recommend you try doing it with a set instead. — PM 2Ring, Mar 11 '16 at 18:41
Thanks for the set explanation . I called the isSelfCrossing like this: `s = Solution()` `print s.isSelfCrossing(x)` ... I don' t think it's the problem of calling Solution class ;) — Elona Mishmika, Mar 14 '16 at 22:20

score 0 · Answer 1 · edited Dec 16 '20 at 15:36

0

How huge could "x" be? If "x" is not so big, does your code run successfully?

Assuming "x" is really really huge, it might be related to your "m" initialization which is the straw that broke the camel's back. In other words, your "x" (and some other memory allocations) might consume almost all of the allowed memory allocation of the process, and "m" initialization passes over the limit.

edited Dec 16 '20 at 15:36

Peter Mortensen

30,738
21
105
131

answered Mar 05 '16 at 11:47

Aviad

343
1
7

Hello Aviad, the x is not really huge, it's just like 100 numbers. But the memory is not in my computer, it's in the memory of here: leetcode.com/problems/self-crossing. When I'm solving this problem, for large set there is a memory exceed limit, but in my option, for large test set and for small test set the memory should be almost the same. I don't understand why this answer doesn't work. – Elona Mishmika Mar 11 '16 at 09:53

score 0 · Accepted Answer · edited May 23 '17 at 12:07

0

Using lists for a boolean matrix in Python rarely makes sense. Try storing pairs of integers in a set and replace

m = ...       # with m = set()
m[a][b] != 0  # with (a, b) in m
m[a][b] = 1   # with m.add((a, b))

Alternatively, you can create a flat bytearray with the same number of elements as m and index it as a * 1000 + b. This, however, might lead to subtle indexing bugs, so I strongly suggest to give set a try first.

edited May 23 '17 at 12:07

Community

1
1

answered Mar 11 '16 at 10:14

Sergei Lebedev

2,659
20
23

May I ask why using lists for a boolean matrix doesn't make sense in Python please? Cause I was using it like this in C++ a lot...I don't see a difference in memory allocation of this action between C++ and Python. – Elona Mishmika Mar 11 '16 at 10:26
Let me first clarify that I suggested `set` assuming the matrix `m` might be sparse, but even for the dense case I would prefer a nested list of 0/1 integers to a set, because conceptually that is the structure I want to represent, and in Python you often optimize for readability rather than anything else. If you do need to optimize for memory consumption in the dense case and you can't use NumPy, an [`array`](http://docs.python.org/2/library/array.html) or a [`bytearray`](https://docs.python.org/2/library/functions.html#bytearray) is the way to go. – Sergei Lebedev Mar 11 '16 at 10:36
As for the memory differences, in Python a nested list is represented as (roughly) a dynamic array of pointers to the element lists, whereas if you allocate a matrix on the stack in C++ it would be a fixed-size contiguous block of memory. – Sergei Lebedev Mar 11 '16 at 10:36
Also, you can check memory consumption of your Python object using [asizeof](https://pythonhosted.org/Pympler/asizeof.html) from the Pympler package. E.g. `asizeof.asizeof(m) == 9033048`, which is ~8.6Mb on a 64-bit Python. – Sergei Lebedev Mar 11 '16 at 10:43
@YilingLiu: My guess: maybe the leetcode.com site only gives your process a small amount of memory. So you should try Sergei's recommendation and use a set for `m` instead of a list of lists, since only a small number of entries in `m` get set to 1. – PM 2Ring Mar 11 '16 at 18:33

Python memory - The memory limit exceeded for Python code

2 Answers2