순서가 지정된 항복 형 파이썬 반복자 세트에 합치기

Question

다음은 겉보기에 간단한 문제입니다. 정수 시퀀스를 오름차순으로 생성하는 반복기 목록이 주어지면 모든 시퀀스에 나타나는 정수 만 생성하는 간결 생성기를 작성하십시오.

어젯밤에 몇 편의 논문을 읽은 후 파이썬에서 완전 최소 전체 텍스트 인덱서 인 as seen here을 해킹하기로 결정했습니다 (현재 버전은 상당히 오래된 버전 임에도 불구하고).

내 문제는 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)) 

... 당신이 시도하고 목록이 정렬 있다는 장점이 있지만, 감소시키기 때문에, 발전기 표현과 세트 모두 C로 구현 수, 당신은 아마보다 더 나은 일을 힘든 시간을해야합니다 위의 로직은 파이썬으로 구현되었습니다.

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

Answer 4

무엇 이것에 대해 : 나는 그것이 매우 철저하게 (당신의 예를 실행) 테스트를하지 않은,하지만 내가 믿는

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 5

이 솔루션은 반복기의 교차점을 계산합니다. 한 번에 한 단계 씩 반복자를 전진시키고 모든 요소에서 동일한 값을 찾음으로써 작동합니다. 이러한 값이 발견되면 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 6

나는 우아한 솔루션, 어떤 만 반복 앞으로 한 번가 있다는 것을 보여주고 싶다. 죄송합니다. 파이썬에 대해서는 잘 모릅니다. 그래서 가상 클래스를 사용합니다.이 코드는 반복자의 배열 인 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

이 하나가 n 모든 반복자 길이의 합이다 O(n*m)에서 실행하고, m는 목록의 수입니다. 12 행의 힙을 사용하여 O(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])