efficient partial sort in Python ?
Dan Stromberg
drsalists at gmail.com
Tue Aug 19 19:22:48 EDT 2014
On Tue, Aug 19, 2014 at 4:10 PM, Dan Stromberg <drsalists at gmail.com> wrote:
> On Tue, Aug 19, 2014 at 4:05 PM, Dan Stromberg <drsalists at gmail.com> wrote:
>> When you use heapq, are you putting all the values in the heap, or
>> just up to n at a time (evicting the worst value, one at a time as you
>> go)? If you're doing the former, it's basically a heapsort which
>> probably won't beat timsort. If you're doing the latter, that should
>> be pretty good.
>
> It just occurred to me that evicting the highest value each step of
> the way might be expensive with a traditional heap (since the value at
> the largest array index isn't necessarily the largest). I've
> experimented with doing this using a treap a bit:
> http://stromberg.dnsalias.org/~strombrg/treap/ You might try that.
Or more directly relevant:
http://stromberg.dnsalias.org/~strombrg/highest/
More information about the Python-list
mailing list