加入一组有序整数的Python迭代器

Question

这是一个看似简单的问题:给定一个按升序生成整数序列的迭代器列表,编写一个简洁的生成器,只生成每个序列中出现的整数.

在昨晚阅读了几篇论文之后,我决定在Python中破解一个完全最小的全文索引器,如此处所示(尽管该版本现在已经很老了).

我的问题在于search()函数,它必须迭代每个发布列表并仅产生每个列表上显示的文档ID.正如您从上面的链接中看到的那样,我当前的非递归"工作"尝试非常糟糕.

示例:

postings = [[1,   100, 142, 322, 12312],
            [2,   100, 101, 322, 1221],
            [100, 142, 322, 956, 1222]]

应该产量:

[100, 322]

至少有一个优雅的递归函数解决方案,但我想尽可能避免这种情况.但是,一个涉及嵌套生成器表达式,itertools滥用或任何其他类型的代码高尔夫的解决方案非常受欢迎.:-)

应该可以安排函数只需要与最小列表中的项目一样多的步骤,并且不将整个整数集吸入内存.将来,这些列表可能从磁盘读取,并且大于可用RAM.

在过去的30分钟里,我对我的舌尖有了一个想法,但我无法将其纳入代码中.请记住,这只是为了好玩!

Answer 1

import heapq, itertools
def intersect(*its):
    for key, values in itertools.groupby(heapq.merge(*its)):
        if len(list(values)) == len(its):
            yield key

>>> list(intersect(*postings))
[100, 322]

Answer 2

def postings(posts):
    sets = (set(l) for l in posts)
    return sorted(reduce(set.intersection, sets))

...你可以尝试利用列表是有序的这一事实,但由于reduce,生成器表达式和集合都是用C实现的,你可能会比用python实现的逻辑更好地做上面的事情.

Answer 3

此解决方案将计算迭代器的交集.它的工作原理是逐步推进迭代器,并在所有迭代器中查找相同的值.找到后,会产生这样的值 - 这使得intersect函数本身就是一个生成器.

import operator

def intersect(sequences):
    """Compute intersection of sequences of increasing integers.

    >>> list(intersect([[1,   100, 142, 322, 12312],
    ...                 [2,   100, 101, 322, 1221],
    ...                 [100, 142, 322, 956, 1222]]))
    [100, 322]
    """
    iterators = [iter(seq) for seq in sequences]
    last = [iterator.next() for iterator in iterators]
    indices = range(len(iterators) - 1)
    while True:
        # The while loop stops when StopIteration is raised. The
        # exception will also stop the iteration by our caller.
        if reduce(operator.and_, [l == last[0] for l in last]):
            # All iterators contain last[0]
            yield last[0]
            last = [iterator.next() for iterator in iterators]

        # Now go over the iterators once and advance them as
        # necessary. To stop as soon as the smallest iterator is
        # exhausted we advance each iterator only once per iteration
        # in the while loop.
        for i in indices:
            if last[i] < last[i+1]:
                last[i] = iterators[i].next()
            if last[i] > last[i+1]:
                last[i+1] = iterators[i+1].next()