17

这是一个看似简单的问题：给定一个迭代器列表，这些迭代器按升序产生整数序列，编写一个简洁的生成器，它只产生出现在每个序列中的整数。

昨晚阅读了几篇论文后，我决定用 Python 破解一个完全最小的全文索引器，如图所示（尽管那个版本现在已经很老了）。

我的问题在于该search()函数，它必须遍历每个发布列表并仅生成出现在每个列表上的文档 ID。正如您从上面的链接中看到的那样，我当前的非递归“工作”尝试非常糟糕。

示例：

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

应该产生：

[100, 322]

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

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

在过去的 30 分钟里，我在舌尖有了一个想法，但我无法将其完全融入代码中。请记住，这只是为了好玩！

4

7 回答 7

16 
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]
于 2009-06-11T00:49:14.260 回答
6 
def postings(posts):
    sets = (set(l) for l in posts)
    return sorted(reduce(set.intersection, sets))

...您可以尝试利用列表是有序的这一事实，但由于 reduce、生成器表达式和 set 都是用 C 实现的，因此使用 python 实现的逻辑您可能很难做得比上面的更好.

于 2009-06-09T12:22:43.800 回答
6

该解决方案将计算迭代器的交集。它通过一次推进迭代器并在所有迭代器中寻找相同的值来工作。找到后，就会产生这样的值——这使得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()
于 2009-06-09T13:11:37.273 回答
3

如果这些序列真的很长（甚至无限），并且您不想提前将所有内容加载到集合中，则可以在每个迭代器上使用 1 项前瞻来实现这一点。

EndOfIter = object() # Sentinel value

class PeekableIterator(object):
    def __init__(self, it):
        self.it = it
        self._peek = None
        self.next() # pump iterator to get first value

    def __iter__(self): return self

    def next(self):
        cur = self._peek
        if cur is EndOfIter:
            raise StopIteration()

        try:
            self._peek = self.it.next()
        except StopIteration:
            self._peek = EndOfIter
        return cur

    def peek(self): 
        return self._peek


def contained_in_all(seqs):
   if not seqs: return   # No items
   iterators = [PeekableIterator(iter(seq)) for seq in seqs]
   first, rest = iterators[0], iterators[1:]

   for item in first:
       candidates = list(rest)
       while candidates:
           if any(c.peek() is EndOfIter for c in candidates): return  # Exhausted an iterator
           candidates = [c for c in candidates if c.peek() < item]
           for c in candidates: c.next()

       # Out of loop if first item in remaining iterator are all >= item.
       if all(it.peek() == item for it in rest):
           yield item

用法：

>>> print list(contained_in_all(postings))
[100, 322]
于 2009-06-09T12:35:22.947 回答
2

那这个呢：

import heapq

def inalliters(iterators):
  heap=[(iterator.next(),iterator) for iterator in iterators]
  heapq.heapify(heap)
  maximal = max(heap)[0]
  while True:
    value,iterator = heapq.heappop(heap)
    if maximal==value: yield value
    nextvalue=iterator.next()
    heapq.heappush(heap,(nextvalue,iterator))
    maximal=max(maximal,nextvalue)

postings = [iter([1,   100, 142, 322, 12312]),
            iter([2,   100, 101, 322, 1221]),
            iter([100, 142, 322, 956, 1222])]
print [x for x in inalliters(postings)]

我没有对它进行过彻底的测试（只是运行了你的例子），但我相信基本的想法是合理的。

于 2009-06-09T13:09:15.110 回答
1

我想展示一个优雅的解决方案，它只向前迭代一次。抱歉，我不太了解 Python，所以我使用虚构的类。这个读取input，一个迭代器数组，并即时写入，output而无需返回或使用任何数组函数！。

    def intersect (input, output) 
        do:
            min = input[0]
            bingo = True
            for i in input:
                if (i.cur < min.cur):
                     bingo = False
                     min =  i
            if bingo: 
                output.push(min.cur)
        while (min.step())
于 2009-06-09T13:23:02.290 回答
0

这个运行在O(n*m)wheren是所有迭代器长度的总和，并且 m是列表的数量。它可以O(n*logm)通过在第 6 行中使用堆来实现。

def intersection(its):
  if not its: return
  vs = [next(it) for it in its]
  m = max(vs)
  while True:
    v, i = min((v,i) for i,v in enumerate(vs))
    if v == m:
      yield m
    vs[i] = next(its[i])
    m = max(m, vs[i])
于 2013-08-12T13:26:36.060 回答