Heap Implementation

Sven R. Kunze srkunze at mail.de
Mon Feb 1 12:24:07 EST 2016


On 31.01.2016 05:59, srinivas devaki wrote:
> @Sven
> actually you are not sweeping at all, as i remember from my last post
> what i meant by sweeping is periodically deleting the elements which
> were marked as popped items.

Exactly.

Maybe I didn't express myself well. Would you prefer the sweeping 
approach in terms of efficiency over how I implemented xheap currently?

Without running some benchmarks, I have absolutely no feeling which 
approach is faster/more memory efficient etc.

> kudos on that __setitem__ technique,
> instead of using references to the items like in HeapDict, it is
> brilliant of you to simply use __setitem__

Thanks. :)

> On Sun, Jan 31, 2016 at 4:17 AM, Sven R. Kunze <srkunze at mail.de> wrote:
>> Hi again,
>>
>> as the topic of the old thread actually was fully discussed, I dare to open
>> a new one.
>>
>> I finally managed to finish my heap implementation. You can find it at
>> https://pypi.python.org/pypi/xheap + https://github.com/srkunze/xheap.
>>
>> I described my motivations and design decisions at
>> http://srkunze.blogspot.com/2016/01/fast-object-oriented-heap-implementation.html
>>
>> @Cem
>> You've been worried about a C implementation. I can assure you that I did
>> not intend to rewrite the incredibly fast and well-tested heapq
>> implementation. I just re-used it.
>>
>> I would really be grateful for your feedback as you have first-hand
>> experience with heaps.
>>
>> @srinivas
>> You might want to have a look at the removal implementation. Do you think it
>> would be wiser/faster to switch for the sweeping approach?
>>
>> I plan to publish some benchmarks to compare heapq and xheap.
>>
>> @all
>> What's the best/standardized tool in Python to perform benchmarking? Right
>> now, I use a self-made combo of unittest.TestCase and time.time + proper
>> formatting.
>>
>> Best,
>> Sven
>>
>>
>> PS: fixing some weird typos and added missing part.



More information about the Python-list mailing list