17

ここに一見単純な問題があります: 整数のシーケンスを昇順で生成するイテレータのリストが与えられた場合、すべてのシーケンスに現れる整数のみを生成する簡潔なジェネレータを記述します。

昨夜いくつかの論文を読んだ後、私は Python で完全に最小限のフルテキスト インデクサーをハックすることにしました(このバージョンは今ではかなり古いですが)。

私の問題は、search()各投稿リストを反復処理し、すべてのリストに表示されるドキュメント ID のみを生成する必要がある関数にあります。上記のリンクからわかるように、現在の非再帰的な「作業」の試みはひどいものです。

例：

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

生成する必要があります:

[100, 322]

これに対する洗練された再帰関数の解決策が少なくとも 1 つありますが、可能であればそれは避けたいと思います。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 に答える
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 に答える
0

これは、すべての反復子の長さの合計であり O(n*m)、リストの数です。6行目のヒープを使って作ることができます。nmO(n*logm)

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 に答える