[issue38938] Possible performance improvement for heaqq.merge()

[Dennis Sweeney]

Dennis Sweeney <sweeney.dennis650 at gmail.com> added the comment:

The attached recursive_merge.py should be much less ugly and still somewhat performant.

It should be the same algorithm as that PR, just written recursively rather than iteratively.

I got some text files from http://www.gwicks.net/dictionaries.htm and tried merging them line-by-line:

py -3.9 -m pyperf timeit -s "from heapq import merge; from collections import deque" "deque(merge(open('english.txt'), open('dutch.txt'), open('french.txt'), open('german.txt'), open('italian.txt')), maxlen=0)"

    Mean +- std dev: 391 ms +- 9 ms

py -3.9 -m pyperf timeit -s "from recursive_merge import merge; from collections import deque" "deque(merge(open('english.txt'), open('dutch.txt'), open('french.txt'), open('german.txt'), open('italian.txt')), maxlen=0)"

    Mean +- std dev: 262 ms +- 9 ms

Perhaps that's a more real-world benchmark.

----------
Added file: https://bugs.python.org/file49156/recursive_merge.py

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue38938>
_______________________________________