StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWhy does one version leak memory but not the other ? (Python)
text
Body
copied!<p>Both these functions compute the same thing (the numbers of integers such that the length of the associated Collatz sequence is no greater than n) in essentially the same way. The only difference is that the first one uses sets exclusively whereas the second uses both sets and lists.</p> <p>The second one leaks memory (in IDLE with Python 3.2, at least), the first one does not, and I have no idea why. I have tried a few "tricks" (such as adding <code>del</code> statements) but nothing seems to help (which is not surprising, those tricks <em>should be</em> useless).</p> <p>I would be grateful to anybody who could help me understand what goes on.</p> <p><em>If you want to test the code, you should probably use a value of <code>n</code> in the 55 to 65 range, anything above 75 will almost certainly result in a (totally expected) memory error.</em></p> <pre class="lang-py prettyprint-override"><code>def disk(n): """Uses sets for explored, current and to_explore. Does not leak.""" explored = set() current = {1} for i in range(n): to_explore = set() for x in current: if not (x-1) % 3 and ((x-1)//3) % 2 and not ((x-1)//3) in explored: to_explore.add((x-1)//3) if not 2*x in explored: to_explore.add(2*x) explored.update(current) current = to_explore return len(explored) def disk_2(n): """Does exactly the same thing, but Uses a set for explored and lists for current and to_explore. Leaks (like a sieve :)) """ explored = set() current = [1] for i in range(n): to_explore = [] for x in current: if not (x-1) % 3 and ((x-1)//3) % 2 and not ((x-1)//3) in explored: to_explore.append((x-1)//3) if not 2*x in explored: to_explore.append(2*x) explored.update(current) current = to_explore return len(explored) </code></pre> <p><strong>EDIT</strong> : This also happens when using the interactive mode of the interpreter (without IDLE), but not when running the script directly from a terminal (in that case, memory usage goes back to normal some time after the function has returned, or as soon as there is an explicit call to <code>gc.collect()</code>).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload