even faster heaps

Sven R. Kunze srkunze at mail.de
Sun Mar 6 08:59:48 EST 2016


Hi python-list, hi Srinivas,

I managed to implement the mark&sweep approach for fast removal from 
heaps. This way, I got three pleasant results:

1) a substantial speed up!
2) an improved testsuite
3) discovery and fixing of several bugs

@Srinivas I would be honored if you could have a look at the 
implementation: https://github.com/srkunze/xheap . After all, it was 
your idea. I only perform the sweeping step during pop and remove with 
the condition of yours. :)

Using the original xheap benchmark 
<http://srkunze.blogspot.de/2016/02/the-xheap-benchmark.html>, I could 
see huge speedups: from 50x/25x down to 3x/2x compared to heapq. That's 
a massive improvement. I will publish an update soon.

Best,
Sven



More information about the Python-list mailing list