Iterator clone

[Gerenuk]

Hallo!

was wäre denn der günstigste Weg folgendes in etwa zu implementieren:

Code: Alles auswählen

for x in seq:
    seq_follow=clone(seq)
    for y in seq_follow:
         if func(x,y): break
         print(x,y)

Also ich möchte für alle Elemente in seq die jeweils nachfolgenden betrachten und da ein gewisses Stück weit gehen. Das mit dem Clone finde ich irgendwie nicht raus. Ich hatte bis jetzt range(len(...)) Konstrukte, aber das ist ja auch hässlich?

[EyDu]

Hallo.

Ich würde es so lösen:

Code: Alles auswählen

>>> import itertools
>>> sequence = range(4)
>>> for index, x in enumerate(sequence):
...    for y in itertools.islice(sequence, index, index+3):
...        print x, y
... 
0 0
0 1
0 2
1 1
1 2
1 3
2 2
2 3
3 3

Sollte die zu untersuchende Teilsequenz klein sein, so würde auch einfaches Slicing genügen. Um es noch allgemeiner zu halten, falls sequence ein beliebiger Iterator sein kann, solltest du dir noch ``itertools.tee`` anschauen.

[BlackJack]

@EyDu: Bei `islice()` wäre ich vorsichtig -- wenn das nicht speziell auf Sequenzen optimiert ist, dann kann das sehr ineffizient sein, weil dann immer von Anfang an über die Sequenz iteriert wird, bis der Startindex erreicht ist. So kann man sich quadratische Laufzeit einhandeln.

Bei `tee()` müsste man das ganze deutlich umformulieren.

@Gerenuk: Man könnte sich einen "zurückspulbaren" Iterator schreiben, der würde dann nicht nur mit Sequenzen funktionieren, sondern mit jedem "iterable". Ungetestet:

Code: Alles auswählen

class RewindableIterator(Iterator):
    def __init__(self, iterable):
        self.iterator = iter(iterable)
        self.marked = False
        self.recorded = deque()
    
    def next(self):
        if self.marked:
            result = self.iterator.next()
            self.recorded.append(result)
        else:
            if self.recorded:
                result = self.recorded.popleft()
            else:
                result = self.iterator.next()
        return result
    
    def mark(self):
        if self.marked:
            raise Exception('can only mark once')
        self.marked = True
    
    def rewind(self):
        if not self.marked:
            raise Exception('no mark to rewind to')
        self.marked = False

Verwendung in Deinem Fall ungefähr so:

Code: Alles auswählen

rewindable = RewindableIterator(seq)
for x in rewindable:
    rewindable.mark()
    for y in rewindable:
        if func(x, y):
            break
        print x, y
    rewindable.rewind()

[Gerenuk]

@Gerenuk: Man könnte sich einen "zurückspulbaren" Iterator schreiben, der würde dann nicht nur mit Sequenzen funktionieren, sondern mit jedem "iterable".

Coole Idee Und sowas gab es mit den Python standard libs noch nicht?

[EyDu]

Hallo.

Stimmt, das islice Problem habe ich vollkommen übersehen. Mit tee ist die Anpassung allerdings nicht besonders umständlich:

Code: Alles auswählen

>>> import itertools
>>> sequence = range(4)
>>> it = iter(sequence)
>>> try:
...     while True:
...         it, sub = itertools.tee(it, 2)
...         x = next(it)
...         for y in itertools.islice(sub, 3):
...             print x, y
... except StopIteration:
...     pass
... 
0 0
0 1
0 2
1 1
1 2
1 3
2 2                                                                                                                  
2 3                                                                                                                  
3 3