<div class="gmail_quote">On Sat, Mar 12, 2011 at 3:44 PM, Guido van Rossum <span dir="ltr"><<a href="mailto:guido@python.org">guido@python.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
I recently advised a Googler who was sorting a large dataset and<br>
running out of memory. My analysis of the situation was that he was<br>
sorting a huge list of short lines of the form "shortstring,integer"<br>
with a key function that returned a tuple of the form ("shortstring",<br>
integer).</blockquote><div><br></div><div>As Raymond pointed out, a change I made for 3.2 significantly shrinks the memory footprint of sorting with a key (although it's still more memory-intensive than sorting with cmp).</div>
<div><br></div><div>He could reduce the memory footprint further by sorting in two passes instead of using a tuple, leveraging the fact that Python guarantees a stable sort. In 3.2 or later, this technique will require roughly twice as much memory as just storing the list:</div>
<meta http-equiv="content-type" content="text/html; charset=utf-8"><div><br></div><meta http-equiv="content-type" content="text/html; charset=utf-8"><div><div>biglist.sort(key=lambda s: int(s.split(',')[1])) # Sort by the integer</div>
</div><div>biglist.sort(key=lambda s: s.split(',')[0]) # Sort by the shortstring</div><div><br></div><div>I think the use cases are pretty narrow where there's plenty of memory for storing the list but not enough to store two copies.</div>
<div><br></div></div>-- <br>Daniel Stutzbach<br>