[issue13742] Add a key parameter (like sorted) to heapq.merge

[Simon Sapin]

Simon Sapin <simon.sapin at kozea.fr> added the comment:

The attached script benchmarks the basline (current implementation) against 3 new implementations, as suggested on http://mail.python.org/pipermail/python-ideas/2012-January/013296.html

On my machine, the output is:

    merge_baseline
    per run, min of 3 = 7.527 ms
    
    merge_1
    per run, min of 3 = 9.894 ms
    131.449 % of baseline
    
    merge_2
    per run, min of 3 = 7.948 ms
    105.594 % of baseline
    
    merge_3
    per run, min of 3 = 7.581 ms
    100.716 % of baseline

On this particular input, merge_2 adds 6% of overhead when the key parameter is not used. While merge_3 only adds 1% of overhead, it almost doubles the amount of code. (Which was admittedly not that long to begin with.)

The patch in the previous message is with the merge_2 implementation, which seemed like the best compromise to me.

----------
Added file: http://bugs.python.org/file24185/benchmark_heapq_merge.py

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue13742>
_______________________________________