python - 用于合并排序的类字典迭代的生成器

Question

这是 Generator to yield gap tuples from zipped iterables 的变体.

我希望设计一个生成器函数:

• 接受任意数量的迭代器
• 每个输入 iterable 产生零个或多个 (k, v)，k 不一定是唯一的
• 假定输入键按升序排序
• 输出应该产生 (k, (v1, v2, ...))
• 输出键是唯一的，并且与输入的顺序相同
• 输出元组的数量等于输入中唯一键的数量
• 输出值对应于匹配输出键的所有输入元组
• 由于输入和输出可能很大，因此应将它们视为可迭代对象，而不是作为内存中的字典或列表加载。

举个例子，

i1 = ((2, 'a'), (3, 'b'), (5, 'c'))
i2 = ((1, 'd'), (2, 'e'), (3, 'f'))
i3 = ((1, 'g'), (3, 'h'), (5, 'i'), (5, 'j'))
result = sorted_merge(i1, i2, i3)
print [result]

这将输出:

[(1, ('d', 'g')), (2, ('a', 'e')), (3, ('b', 'f', 'h')), (5, ('c', 'i', 'j'))]

如果我没记错的话，Python 标准库中没有内置任何东西可以开箱即用。

Answer 1

虽然没有一个标准库函数可以做你想做的事，但有 enough building blocks帮助您完成大部分工作:

from heapq import merge
from itertools import groupby
from operator import itemgetter

def sorted_merge(*iterables):
    for key, group in groupby(merge(*iterables), itemgetter(0)):
        yield key, [pair[1] for pair in group]    

例子:

>>> i1 = ((2, 'a'), (3, 'b'), (5, 'c'))
>>> i2 = ((1, 'd'), (2, 'e'), (3, 'f'))
>>> i3 = ((1, 'g'), (3, 'h'), (5, 'i'), (5, 'j'))
>>> result = sorted_merge(i1, i2, i3)
>>> list(result)
[(1, ['d', 'g']), (2, ['a', 'e']), (3, ['b', 'f', 'h']), (5, ['c', 'i', 'j'])]

请注意，在 sorted_merge 的版本中上面，我们产生 int , list为了产生可读的输出而对。没有什么可以阻止您将相关行更改为

        yield key, (pair[1] for pair in group)          

如果你想产生int , <generator>相反。