अजगर iterators उपज

Question

यहाँ एक कदाचित सरल समस्या यह है आदेश दिया-पूर्णांक का एक सेट में शामिल होना: iterators कि आरोही क्रम में पूर्णांक के दृश्यों उपज की एक सूची दी गई है, एक संक्षिप्त जनरेटर कि पैदावार केवल पूर्णांकों है कि हर दृश्य में दिखाई देते हैं लिखें।

कल रात कुछ कागजात पढ़ने के बाद, मैंने पाइथन, as seen here में एक पूरी तरह से न्यूनतम पूर्ण पाठ सूचकांक को हैक करने का फैसला किया (हालांकि वह संस्करण अब पुराना है)।

मेरी समस्या 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

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

... आप कोशिश करते हैं और तथ्य यह है कि सूचियों का आदेश दिया जाता का लाभ ले सकता है, लेकिन जब से कम करने, जनरेटर भाव और सेट सभी सी में लागू किया जाता है, तो आप शायद की तुलना में बेहतर कर रही एक कठिन समय होगा पाइथन में लागू तर्क के साथ उपरोक्त।

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

यह समाधान अपने iterators के चौराहे की गणना करेगा। यह एक समय में एक कदम को आगे बढ़ाने और उन सभी में समान मूल्य की तलाश करके काम करता है। जब पाया, इस तरह के मूल्यों झुकेंगे रहे हैं - यह 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

यह एक O(n*m) जहां n सभी इटरेटर लंबाई का योग है में चलाता है, और m सूचियों की संख्या है। इसे लाइन 6 में ढेर का उपयोग करके 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])