Uniéndose a un conjunto de enteros ordenados que producen iteradores de Python

Question

Aquí hay un problema aparentemente simple: dada una lista de iteradores que arrojan secuencias de enteros en orden ascendente, escriba un generador conciso que arroje solo los enteros que aparecen en cada secuencia.

Después de leer algunos documentos anoche, decidí hackear un indexador de texto completo completamente mínimo en Python, as seen here (aunque esa versión ya es bastante antigua).

Mi problema es con la función search(), que debe iterar sobre cada lista de publicación y ceder solo las identificaciones de documentos que aparecen en cada lista. Como puede ver en el enlace de arriba, mi intento actual de "trabajo" no recursivo es terrible.

Ejemplo:

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

debe ceder:

[100, 322] 

Hay al menos una solución función recursiva elegante a este, pero me gustaría evitar que si es posible. Sin embargo, una solución que involucre expresiones generadas anidadas, abuso de itertools, o cualquier otro tipo de código de golf es más que bienvenido. :-)

Debería ser posible disponer que la función solo requiera tantos pasos como elementos en la lista más pequeña, y sin aspirar todo el conjunto de enteros en la memoria. En el futuro, estas listas se pueden leer desde el disco y son más grandes que la memoria RAM disponible.

Durante los últimos 30 minutos he tenido una idea en la punta de la lengua, pero no puedo escribirla. Recuerde, esto es solo por diversión!

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

... usted podría tratar de aprovechar el hecho de que las listas están ordenadas, pero ya reducir, las expresiones generadoras y conjunto está todo implementado en C, es probable que tenga dificultades para hacerlo mejor que lo anterior con lógica implementada en python.

Answer 3

Si estas secuencias son realmente largas (o incluso infinitas), y no desea cargar todo en un conjunto de antemano, puede implementar esto con un elemento de anticipación de 1 elemento en cada iterador.

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 

Uso:

>>> print list(contained_in_all(postings)) 
[100, 322] 

Answer 4

Qué tal esto:

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

no he probado muy a fondo (acaba de ejecutar el ejemplo), pero creo que la idea básica es sólida .

Answer 5

Esta solución calculará la intersección de sus iteradores. Funciona avanzando los iteradores un paso a la vez y buscando el mismo valor en todos ellos. Cuando se encuentran, dichos valores se obtienen, esto hace que la función intersect funcione como un generador.

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 6

Quiero mostrar que hay una solución elegante, que sólo una iteración hacia adelante una vez. Lo siento, no conozco lo suficiente a Python, así que uso clases de ficción.Este lee input, una matriz de iteradores, y escribe en output sobre la marcha sin tener que volver atrás ni utilizar ninguna función de matriz.

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

Éste se ejecuta en O(n*m) donde n es la suma de todas las longitudes de iterador, y m es el número de listas. Se puede hacer O(n*logm) usando un montón en la línea 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])