Присоединение к множеству упорядоченных целочисленных итераторов Python

Question

Вот, на первый взгляд, простая проблема: учитывая список итераторов, которые выдают последовательности целых чисел в порядке возрастания, напишите краткий генератор, который выдает только те числа, которые встречаются в каждой последовательности.

Прочитав несколько статей вчера вечером, я решил взломать на Python абсолютно минимальный полнотекстовый индексатор, , как показано здесь (хотя эта версия довольно старая).

Моя проблема связана с функцией search(), которая должна выполнять итерацию по каждому списку публикаций и выводить только идентификаторы документов, которые появляются в каждом списке. Как видно из приведенной выше ссылки, моя текущая нерекурсивная «рабочая» попытка ужасна.

Пример :

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

Должен дать:

[100, 322]

Существует по крайней мере одно элегантное рекурсивное решение этой проблемы, но я бы хотел избежать этого, если это возможно. Тем не менее, решение, включающее вложенные выражения генератора, злоупотребление itertools или любой другой вид гольф-кода, приветствуется. : -)

Должна быть возможность устроить так, чтобы функция требовала только столько шагов, сколько имеется элементов в наименьшем списке, и не высасывая весь набор целых чисел в память. В будущем эти списки могут быть прочитаны с диска и больше, чем доступно в ОЗУ.

В течение последних 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

Это решение будет вычислять пересечение ваших итераторов. Он работает, продвигая итераторы по одному шагу за раз и ища одинаковое значение во всех них. Когда такие значения найдены, они получаются - это делает функцию 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()

Answer 3

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

... вы можете попробовать воспользоваться тем фактом, что списки упорядочены, но, так как Reduce, выражения генератора и set все реализованы на C, вам, вероятно, будет нелегко добиться большего, чем с логикой вышеописанного реализовано в python.

Answer 4

Если это действительно длинные (или даже бесконечные) последовательности, и вы не хотите загружать все в набор заранее, вы можете реализовать это с предварительным просмотром 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]

Answer 5

Что по этому поводу:

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)]

Я не очень тщательно его проверил (просто провёл ваш пример), но я считаю, что основная идея - это звук.

Answer 6

Я хочу показать, что есть элегантное решение, которое повторяется только один раз . Извините, я недостаточно хорошо знаю 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()) 

Answer 7

Эта строка выполняется в O(n*m), где n - сумма всех длин итераторов, а 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])