Ich suche nach einigen Einzelheiten darüber, wie Perls grep -Funktion funktioniert. Ich mache das:
Angenommen, @bar ist groß (Hunderttausende von Elementen). Wenn ich nach meinen Daten sortiere @bar , erscheinen Werte von $foo eher am Anfang des Arrays als am Ende. Ich frage mich, ob dies der Performance hilft.
Anders ausgedrückt, bewegt sich grep mit dem obigen Code sequentiell durch @bar , prüft ob $foo == $_ und wird dann sofort beendet, sobald ein Wert als wahr erkannt wurde? Oder würde es tatsächlich jedes Element von @bar prüfen, bevor es einen Wert zurückgibt?
grep schließt nicht kurz, so dass die Reihenfolge der Elemente keine Rolle spielt.
Während List :: MoreUtils first einen Kurzschluss hat, muss die ganze Liste vor dem Aufruf auf dem Stack platziert werden.
Dies wird am besten sein:
%Vor% Aktualisiert : Ich habe ursprünglich über die Indizes iteriert, seit das O (1) Speicher verwendet, aber auch for (@bar) (im Gegensatz zu for (LIST) im Allgemeinen), wie Ysth mich daran erinnert hat.
Da Ihre Verwendung von grep im skalaren Kontext ist, wird die Anzahl der übereinstimmenden Elemente zurückgegeben. Um dies zu berechnen, muss Perl jedes Element trotzdem besuchen, daher ist es unwahrscheinlich, dass die Sortierung die Leistung aus diesem Blickwinkel unterstützt.
In Ihrem Beispiel wird grep das gesamte Array durchlaufen, unabhängig davon, wie viele Elemente übereinstimmen.
Wenn Sie dieses Array sortiert halten können, ist es schneller, nach Ihren Werten mit der binären Suche zu suchen. Sie können auch Ihr Array in Hash konvertieren (mit Keys = Array-Element) und Ihre Prüfungen mit konstanter Zeit durchführen, aber das wird zusätzlichen Speicher verbrauchen.
Es kommt darauf an. A grep { $x == $_ } @a profitiert nicht von der Verzweigungsvorhersage, aber grep { $x < $_ } @a macht!
Die Ergebnisse:
%Vor%Siehe auch Warum ist es schneller? ein sortiertes Array als ein unsortiertes Array verarbeiten?