 |
| An ambulance rushing by. |
Here's an update of the benchmark. Compared to its predecessor, the change was quite a success. The removal capability accounts for an 4x slowdown now compared to its prior 50x. Furthermore, I could improve the testsuite considerably and as expected I needed to fix some bugs then.
The faster and better version of xheap can be obtained from PyPI and the source can be found at github.
operation 1,000 items 10,000 items 100,000 items 1,000,000 items
init heapq 0.03 ( 1.00x) 0.41 ( 1.00x) 4.45 ( 1.00x) 64.37 ( 1.00x)
Heap 0.03 ( 1.02x) 0.42 ( 1.03x) 4.46 ( 1.00x) 64.36 ( 1.00x)
RemovalHeap 0.05 ( 1.57x) 0.62 ( 1.53x) 7.94 ( 1.79x) 101.16 ( 1.57x)
pop heapq 0.01 ( 1.00x) 0.07 ( 1.00x) 0.85 ( 1.00x) 10.32 ( 1.00x)
Heap 0.01 ( 1.46x) 0.10 ( 1.38x) 1.13 ( 1.33x) 13.20 ( 1.28x)
RemovalHeap 0.02 ( 4.18x) 0.24 ( 3.51x) 2.61 ( 3.07x) 28.37 ( 2.75x)
push heapq 0.00 ( 1.00x) 0.03 ( 1.00x) 0.34 ( 1.00x) 3.58 ( 1.00x)
Heap 0.01 ( 1.82x) 0.06 ( 1.85x) 0.61 ( 1.81x) 6.38 ( 1.78x)
RemovalHeap 0.01 ( 2.83x) 0.09 ( 2.91x) 0.97 ( 2.86x) 9.81 ( 2.74x)
init heapq 0.14 ( 1.00x) 1.60 ( 1.00x) 24.00 ( 1.00x) 271.42 ( 1.00x)
OrderHeap 0.17 ( 1.26x) 1.88 ( 1.18x) 26.80 ( 1.12x) 299.55 ( 1.10x)
XHeap 0.19 ( 1.42x) 2.10 ( 1.31x) 30.14 ( 1.26x) 332.56 ( 1.23x)
pop heapq 0.01 ( 1.00x) 0.15 ( 1.00x) 1.83 ( 1.00x) 22.37 ( 1.00x)
OrderHeap 0.02 ( 1.80x) 0.24 ( 1.60x) 2.73 ( 1.50x) 31.36 ( 1.40x)
XHeap 0.03 ( 2.66x) 0.33 ( 2.25x) 3.69 ( 2.02x) 41.03 ( 1.83x)
push heapq 0.00 ( 1.00x) 0.04 ( 1.00x) 0.54 ( 1.00x) 5.67 ( 1.00x)
OrderHeap 0.01 ( 3.97x) 0.15 ( 3.70x) 1.62 ( 3.03x) 16.46 ( 2.90x)
XHeap 0.01 ( 3.28x) 0.12 ( 3.06x) 1.38 ( 2.58x) 13.94 ( 2.46x)
remove RemovalHeap 0.02 ( 1.00x) 0.19 ( 1.00x) 2.18 ( 1.00x) 22.62 ( 1.00x)
XHeap 0.02 ( 0.90x) 0.17 ( 0.89x) 1.72 ( 0.79x) 17.60 ( 0.78x)
Kudos to Srinivas who proposed the mark&sweep approach in the first place, especially the sweeping condition which allows an amortized runtime of O(log n) for pop, push and remove.
Best,
Sven
No comments:
Post a Comment