pytoolz/toolz — pull request #163 by larsmans (2014-05-03 12:04:04+00:00)
Title: faster merge_sorted without key

Here's an easy optimization for `merge_sorted`. Instead of consuming the `heapq.merge` generator and passing the items on to the caller, just pass on the generator.

The diff looks big because of my re-indenting. Unfortunately `return other_iterable` is not allowed (so much for "consenting adults") and Python 2 doesn't have `yield from`, so I had to introduce a separate function for the `key is not None` case.

Micro-benchmark, before:

```python
>>> from heapq import merge
>>> from toolz import merge_sorted
>>> a = range(10000)
>>> b = range(1, 5000, 2)
>>> %timeit list(merge(a, b))
100 loops, best of 3: 2.02 ms per loop
>>> %timeit list(merge_sorted(a, b))
100 loops, best of 3: 2.43 ms per loop
```

17% of the time spent looping and yielding.

After:

```python
>>> %timeit list(merge_sorted(a, b))
1000 loops, best of 3: 1.94 ms per loop
>>> %timeit list(merge(a, b))
100 loops, best of 3: 1.91 ms per loop
```

(It looks like `heapq.merge` magically got faster as well ;)