<br>Python 2.x, or Python 3.x?<br><br>What are the types of your sort keys?<br><br>If you're on 3.x and the key you need reversed is numeric, you can negate the key.<br><br>If you're on 2.x, you can use an object with a __cmp__ method to compare objects however you require.<br>
<br>You probably should timsort the chunks (which is the standard list_.sort() - it's a very good in-memory sort), and then merge them afterward using the merge step of merge sort.<br><br>heapq's not unreasonable for the merging, but I think it's more common to use a short list.<br>
<br>I have a bunch of Python sorts at <a href="http://stromberg.dnsalias.org/svn/sorts/compare/trunk/">http://stromberg.dnsalias.org/svn/sorts/compare/trunk/</a> - if you find your need is specialized (EG, 3.x sorting by a secondary key that's a string, in reverse), you could adapt one of these to do what you need.<br>
<br>heapq is not bad, but if you find you need a logn datastructure, you might check out <a href="http://stromberg.dnsalias.org/~dstromberg/treap/">http://stromberg.dnsalias.org/~dstromberg/treap/</a> - a treap is also logn, but has a very good amortized cost because it sacrifices keeping things perfectly balanced (and rebalancing, and rebalancing...) to gain speed.  But still, you might be better off with a short list and min.<br>
<br><div class="gmail_quote">On Mon, Aug 1, 2011 at 8:33 AM, aliman <span dir="ltr"><<a href="mailto:alimanfoo@googlemail.com">alimanfoo@googlemail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Hi all,<br>
<br>
Apologies I'm sure this has been asked many times, but I'm trying to<br>
figure out the most efficient way to do a complex sort on very large<br>
files.<br>
<br>
I've read the recipe at [1] and understand that the way to sort a<br>
large file is to break it into chunks, sort each chunk and write<br>
sorted chunks to disk, then use heapq.merge to combine the chunks as<br>
you read them.<br>
<br>
What I'm having trouble figuring out is what to do when I want to sort<br>
by one key ascending then another key descending (a "complex sort").<br>
<br>
I understand that sorts are stable, so I could just repeat the whole<br>
sort process once for each key in turn, but that would involve going<br>
to and from disk once for each step in the sort, and I'm wondering if<br>
there is a better way.<br>
<br>
I also thought you could apply the complex sort to each chunk before<br>
writing it to disk, so each chunk was completely sorted, but then the<br>
heapq.merge wouldn't work properly, because afaik you can only give it<br>
one key.<br>
<br>
Any help much appreciated (I may well be missing something glaringly<br>
obvious).<br>
<br>
Cheers,<br>
<br>
Alistair<br>
<br>
[1] <a href="http://code.activestate.com/recipes/576755-sorting-big-files-the-python-26-way/" target="_blank">http://code.activestate.com/recipes/576755-sorting-big-files-the-python-26-way/</a><br>
<font color="#888888">--<br>
<a href="http://mail.python.org/mailman/listinfo/python-list" target="_blank">http://mail.python.org/mailman/listinfo/python-list</a><br>
</font></blockquote></div><br>