Heap Implementation

[Sven R. Kunze]

On 31.01.2016 02:48, Steven D'Aprano wrote:
> On Sunday 31 January 2016 09:47, Sven R. Kunze wrote:
>
>> @all
>> What's the best/standardized tool in Python to perform benchmarking?
> timeit
Thanks, Steven.

Maybe, I am doing it wrong but I get some weird results:

 >>> min(timeit.Timer('for _ in range(10000): heappop(h)', 'from heapq 
import heappop; h=list(range(10000000))').repeat(10, 1)), 
min(timeit.Timer('for _ in range(10000): h.pop()', 'from xheap import 
Heap; h=Heap(range(10000000))').repeat(10, 1))
(0.017267618000005314, 0.01615345600021101)

 >>> min(timeit.Timer('for _ in range(100000): heappop(h)', 'from heapq 
import heappop; h=list(range(10000000))').repeat(10, 1)), 
min(timeit.Timer('for _ in range(100000): h.pop()', 'from xheap import 
Heap; h=Heap(range(10000000))').repeat(10, 1))
(0.12321608699949138, 0.13042051299999002)

 >>> min(timeit.Timer('for _ in range(10000): heappop(h)', 'from heapq 
import heappop; h=list(range(1000000))').repeat(10, 1)), 
min(timeit.Timer('for _ in range(10000): h.pop()', 'from xheap import 
Heap; h=Heap(range(1000000))').repeat(10, 1))
(0.010081621999233903, 0.008791901999757101)

 >>> min(timeit.Timer('for _ in range(1000000): heappop(h)', 'from heapq 
import heappop; h=list(range(10000000))').repeat(10, 1)), 
min(timeit.Timer('for _ in range(1000000): h.pop()', 'from xheap import 
Heap; h=Heap(range(10000000))').repeat(10, 1))
(0.6218949679996513, 0.7172151949998806)


How can it be that my wrapper is sometimes faster and sometimes slower 
than heapq? I wouldn't mind slower, but faster*?


Best,
Sven


* that behavior is reproducible also for other combos and other machines.