heapq.merge() 如何与无限生成器一起工作？

Question

我想了解 heapq.merge() 如何使用无限生成器。考虑这个例子：

>>> from heapq import merge
>>> from itertools import count
>>> m = merge(count(0, 2), count(1, 2))
>>> for _ in range(10):
...     print(next(m))
...
0
1
2
3
4
5
6
7
8
9

文档说明它不会一次性将数据拉入内存。但是它是如何消耗每个无限生成器的呢？

Answer 1

一个非常这样一个函数的简单实现可能如下所示。但是请注意，为了简单起见，这不会处理任何特殊（和不那么特殊）的情况，例如空的或耗尽的可迭代对象。

def merge(*iterables):
    heap = [(next(it), i) for i, it in enumerate(iterables)]
    heapq.heapify(heap)
    while heap:
        val, i = heapq.heappop(heap)
        yield val
        heapq.heappush(heap, (next(iterables[i]), i))

它是这样工作的：

从每个 已排序 可迭代对象中获取第一个元素，以及该可迭代对象在列表中的索引
从堆中产生下一个最小的元素
从 iterable 中添加下一个元素，该元素与刚刚生成的元素具有相同的索引

实际的实现有点复杂，但似乎大致按照相同的思路工作。您可以使用 heapq.__file__ 获取本地源的位置，在我的系统上是 /usr/lib/python3.6/heapq.py，并自行检查。

heapq.merge() 如何与无限生成器一起工作？

How does heapq.merge() work with infinite generators?

python

merge

heap

priority-queue

heapq