2008-09-21 8 views
11

Hat jemand in Perl eine gute Lösung für lazy-evaluated Listen gefunden? Ich habe eine Reihe von Möglichkeiten versucht, etwas zu machen wieGibt es eine Perl-Lösung für faule Listen dieser Seite von Perl 6?

for my $item (map { ... } @list) { 
} 

in eine lazy evaluation - durch tie-ing @liste, zum Beispiel. Ich versuche es zu vermeiden, einen Quellfilter zu schreiben und zu schreiben, weil er sich mit der Fähigkeit beschäftigt, den Code zu debuggen. Hat jemand Erfolg gehabt? Oder müssen Sie nur eine While-Schleife verwenden?

Hinweis: Ich denke, dass ich erwähnen sollte, dass ich manchmal lange grep-map-Ketten für funktional transformierende Listen angehakt habe. Es ist also nicht so sehr die foreach-Schleife oder die while-Schleife. Map-Ausdrücke neigen dazu, mehr Funktionalität in den gleichen vertikalen Bereich zu packen.

Antwort

13

Wie bereits erwähnt, ist für (jedes) eine eifrige Schleife, so dass es vor dem Start die gesamte Liste auswerten möchte.

Der Einfachheit halber würde ich empfehlen, ein Iterator-Objekt oder Closure zu verwenden, anstatt zu versuchen, ein lazy evaluated Array zu haben. Während Sie können verwenden Sie eine Krawatte, um eine träge ausgewertet unendliche Liste haben, können Sie in Schwierigkeiten laufen, wenn Sie jemals fragen (direkt oder indirekt, wie in der foreach oben) für die gesamte Liste (oder sogar die Größe der gesamten Liste) .

Ohne eine vollständige Klasse oder mit beliebigen Modulen zu schreiben, können Sie eine einfache iterator Fabrik machen nur durch die Verwendung Verschlüsse:

sub make_iterator { 
    my ($value, $max, $step) = @_; 

    return sub { 
     return if $value > $max; # Return undef when we overflow max. 

     my $current = $value; 
     $value += $step;   # Increment value for next call. 
     return $current;   # Return current iterator value. 
    }; 
} 

Und dann, es zu benutzen:

# All the even numbers between 0 - 100. 
my $evens = make_iterator(0, 100, 2); 

while (defined(my $x = $evens->())) { 
    print "$x\n"; 
} 

Es gibt auch die Tie::Array::Lazy Modul auf dem CPAN, die eine viel reichere und vollere Schnittstelle zu Lazy-Arrays bietet. Ich habe das Modul nicht selbst benutzt, daher kann Ihre Laufleistung variieren.

Alles Gute,

Paul

+1

Wenn Sie mehr über diese Art von Programmierung erfahren möchten, lesen Sie Mark Jason Dominus Buch "Higher Order Perl". Sehr gut, IMHO. – moritz

+2

for/foreach do * not * bekomme die ganze Liste im Spezialfall des Bereichsoperators. – user11318

2

Wenn ich mich richtig erinnere, for/foreach bekomme sowieso zuerst die ganze Liste, also würde eine faul ausgewertete Liste komplett gelesen und dann würde es anfangen, durch die Elemente zu iterieren. Daher denke ich, dass es keinen anderen Weg gibt, als eine While-Schleife zu verwenden. Aber ich kann mich irren.

Der Vorteil einer while-Schleife ist, dass Sie mit einem Referenz-Code die Empfindung einer lazily ausgewertet Liste fälschen können:

my $list = sub { return calculate_next_element }; 
while(defined(my $element = &$list)) { 
    ... 
} 

Schließlich, ich denke, eine Krawatte so nah ist, wie Sie in Perl bekommen 5.

+0

Warum nicht nur meine $ list = \ & calculate_next_element; ? Oder überspringe die Codereferenz und rufe calculate_next_element direkt auf? – cjm

+0

for/foreach do * not * Erhalte die gesamte Liste im Fall des Bereichsoperators. Sonst tun sie es. – user11318

+0

cjm: Das war nur als Platzhalter für * calculate-your-next-element-hier * gedacht, nicht wirklich ein Funktionsaufruf. Sonst hast du natürlich Recht. – jkramer

5

Es gibt mindestens einen Spezialfall, bei dem for und foreach optimiert wurden, um nicht die gesamte Liste auf einmal zu generieren. Und das ist der Bereichsoperator. So haben Sie die Möglichkeit, zu sagen:

for my $i (0..$#list) { 
    my $item = some_function($list[$i]); 
    ... 
} 

und dies wird das Array durchlaufen, transformiert, wie Sie wollen, ohne eine lange Liste von Werten vorne zu schaffen.

Wenn Sie Ihre Karte Anweisung wünschen variable Anzahl von Elementen zurück, Sie diese stattdessen tun könnte:

for my $i (0..$#array) { 
    for my $item (some_function($array[$i])) { 
    ... 
    } 
} 

Wenn Sie mehr Pervasive Faulheit als dies wünschen, dann Ihre beste Möglichkeit ist, zu lernen, wie Verschlüsse verwenden um faule Listen zu erzeugen. MJDs ausgezeichnetes Buch Higher Order Perl kann Sie durch diese Techniken führen. Seien Sie jedoch gewarnt, dass sie wesentlich umfangreichere Änderungen an Ihrem Code erfordern.

9

[Sidenote: Seien Sie sich bewusst, dass jeder einzelne Schritt auf einer Karte/grep Kette gespannt ist. Wenn Sie eine große Liste auf einmal eingeben, beginnen Ihre Probleme viel früher als beim letzten foreach.]

Was Sie tun können, um ein vollständiges Neuschreiben zu vermeiden, ist, Ihre Schleife mit einer äußeren Schleife zu wickeln. Anstatt diese zu schreiben:

for my $item (map { ... } grep { ... } map { ... } @list) { ... } 

... schreiben Sie es wie folgt aus:

while (my $input = calculcate_next_element()) { 
    for my $item (map { ... } grep { ... } map { ... } $input) { ... } 
} 

Dies erspart Ihnen, deutlich Ihre vorhandenen Code neu zu schreiben, und solange die Liste nicht durch mehrere Aufträge wächst von Magnitude während der Transformation, erhalten Sie fast alle Vorteile, die ein Neuschreiben auf Iterator-Stil bieten würde.

7

Wenn Sie faule Listen erstellen möchten, müssen Sie einen eigenen Iterator schreiben. Sobald Sie das haben, können Sie etwas wie Object::Iterate verwenden, das Iterator-bewusste Versionen von map und grep hat. Sehen Sie sich die Quelle für dieses Modul an: Es ist ziemlich einfach und Sie werden sehen, wie Sie Ihre eigenen Iterator-fähigen Subroutinen schreiben.

Viel Glück :)

3

fragte ich eine ähnliche Frage an perlmonks.org und BrowserUk gab einen wirklich guten Rahmen in his answer. Im Prinzip ist es eine bequeme Möglichkeit, eine faule Bewertung zu erhalten, indem man Threads für die Berechnung spawnt, zumindest so lange, wie Sie sicher sind, dass Sie die Ergebnisse, Just Not Now, wollen. Wenn Sie eine faule Auswertung wünschen, um die Latenz nicht zu reduzieren, sondern um Berechnungen zu vermeiden, hilft mein Ansatz nicht, da er auf einem Push-Modell und nicht auf einem Pull-Modell beruht. Eventuell können Sie mit Coro Outines diesen Ansatz auch in ein (single-threaded) Pull-Modell umwandeln.

Während dieses Problem nachzudenken, ich untersuchte auch tie-ing ein Array an den Faden Ergebnisse des Perl-Programm eher wie map machen fließen, aber so weit, wie ich meine API zur Einführung des parallel „Schlüsselwort“ (ein Objektkonstruktor in Verkleidung) und dann Methoden auf das Ergebnis aufrufen. Die besser dokumentierte Version des Codes wird als Antwort auf that thread und möglicherweise auch auf CPAN veröffentlicht.

4

diese von den Toten zurück bringen zu erwähnen, dass ich nur das Modul List::Gen auf CPAN geschrieben, die genau das tut, was das Plakat suchte:

use List::Gen; 

for my $item (@{gen { ... } \@list}) {...} 

alle Berechnung der Listen sind faul, und es gibt Karte/grep Äquivalente zusammen mit einigen anderen Funktionen.

Jede der Funktionen gibt einen 'generator' zurück, der eine Referenz auf ein gebundenes Array darstellt. Sie können das gebundene Array direkt verwenden, oder es gibt eine Reihe von Accessor-Methoden wie Iteratoren zu verwenden.

+0

Ich werde es mir ansehen. Vielen Dank. – Axeman

+0

Kein Problem, wenn es irgendwelche Funktionen gibt, von denen Sie denken, dass sie darin enthalten sein sollten, lassen Sie es mich wissen. –