Ich habe Scala-Code geschrieben, um eine elementweise Operation für eine Sammlung auszuführen. Hier habe ich zwei Methoden definiert, die dieselbe Aufgabe ausführen. Eine Methode verwendet zip
und die andere verwendet zipped
.
def ES (arr :Array[Double], arr1 :Array[Double]) :Array[Double] = arr.zip(arr1).map(x => x._1 + x._2)
def ES1(arr :Array[Double], arr1 :Array[Double]) :Array[Double] = (arr,arr1).zipped.map((x,y) => x + y)
Um diese beiden Methoden hinsichtlich der Geschwindigkeit zu vergleichen, habe ich den folgenden Code geschrieben:
def fun (arr : Array[Double] , arr1 : Array[Double] , f :(Array[Double],Array[Double]) => Array[Double] , itr : Int) ={
val t0 = System.nanoTime()
for (i <- 1 to itr) {
f(arr,arr1)
}
val t1 = System.nanoTime()
println("Total Time Consumed:" + ((t1 - t0).toDouble / 1000000000).toDouble + "Seconds")
}
Ich rufe die fun
Methode auf und übergebe ES
und ES1
wie folgt:
fun(Array.fill(10000)(math.random), Array.fill(10000)(math.random), ES , 100000)
fun(Array.fill(10000)(math.random), Array.fill(10000)(math.random), ES1, 100000)
Die Ergebnisse zeigen , dass die Methode mit dem Namen , ES1
dass Anwendungen zipped
schneller als Verfahren , ES
dass Verwendungen zip
. Aufgrund dieser Beobachtungen habe ich zwei Fragen.
Warum ist zipped
schneller als zip
?
Gibt es eine noch schnellere Möglichkeit, elementweise Operationen an einer Sammlung in Scala durchzuführen?
scala
performance
scala-collections
jmh
elementwise-operations
user12140540
quelle
quelle
Antworten:
So beantworten Sie Ihre zweite Frage:
Die traurige Wahrheit ist, dass funktionale Sprachen trotz ihrer Prägnanz, verbesserten Produktivität und Widerstandsfähigkeit gegenüber Fehlern nicht unbedingt die leistungsstärksten sind. Verwenden Sie Funktionen höherer Ordnung, um eine Projektion zu definieren, die für nicht freie Sammlungen ausgeführt werden soll, und Ihre enge Schleife hebt dies hervor. Wie andere bereits betont haben, wird die zusätzliche Speicherzuweisung für Zwischen- und Endergebnisse ebenfalls einen Overhead verursachen.
Wenn die Leistung kritisch ist, obwohl dies keineswegs universell ist, können Sie in Fällen wie Ihrem die Vorgänge von Scala wieder in zwingende Äquivalente zurückführen, um die Kontrolle über die Speichernutzung wieder direkter zu erlangen und Funktionsaufrufe zu vermeiden.
In Ihrem speziellen Beispiel können die
zipped
Summen unbedingt ausgeführt werden, indem ein festes, veränderbares Array mit der richtigen Größe vorab zugewiesen wird (da die Zip-Funktion stoppt, wenn in einer der Sammlungen keine Elemente mehr vorhanden sind) und anschließend Elemente am entsprechenden Index hinzugefügt werden (seit dem Zugriff) Array-Elemente nach Ordnungsindex sind eine sehr schnelle Operation.Hinzufügen einer dritten Funktion
ES3
zu Ihrer Testsuite:Auf meinem i7 erhalte ich folgende Antwortzeiten:
Noch hektischer wäre es, eine direkte Mutation des kürzeren der beiden Arrays an Ort und Stelle durchzuführen, was offensichtlich den Inhalt eines der Arrays verfälschen würde und nur dann erfolgen würde, wenn das ursprüngliche Array erneut nicht benötigt würde:
Aber offensichtlich ist die direkte Mutation von Array-Elementen nicht im Sinne von Scala.
quelle
Array.tabulate(minSize)(i => arr(i) + arr1(i))
Array.tabulate
sollte viel schneller sein als entwederzip
oderzipped
hier (und ist in meinen Benchmarks).for
wird zu einem Funktionsaufruf höherer Ordnung (foreach
) entschärft . Das Lambda wird in beiden Fällen nur einmal instanziiert.Keine der anderen Antworten erwähnt den Hauptgrund für den Geschwindigkeitsunterschied, nämlich dass die
zipped
Version 10.000 Tupelzuweisungen vermeidet. Als ein paar der anderen Antworten tun Note, diezip
beinhaltet Version eine Zwischen Array, während diezipped
Version nicht der Fall ist, sondern auch für 10.000 Elemente eines Arrays Zuteilung ist nicht das, was die machtzip
Version so viel schlechter es die 10.000 kurzlebig Tupel ist das werden in dieses Array eingefügt. Diese werden durch Objekte in der JVM dargestellt, sodass Sie eine Reihe von Objektzuordnungen für Dinge vornehmen, die Sie sofort wegwerfen werden.Der Rest dieser Antwort geht nur etwas detaillierter darauf ein, wie Sie dies bestätigen können.
Besseres Benchmarking
Sie möchten wirklich ein Framework wie jmh verwenden , um verantwortungsbewusstes Benchmarking für die JVM durchzuführen , und selbst dann ist der verantwortungsvolle Teil schwierig, obwohl das Einrichten von jmh selbst nicht schlecht ist. Wenn Sie eine
project/plugins.sbt
solche haben:Und
build.sbt
so etwas (ich verwende 2.11.8, da Sie erwähnen, dass Sie das verwenden):Dann können Sie Ihren Benchmark folgendermaßen schreiben:
Und führen Sie es aus mit
sbt "jmh:run -i 10 -wi 10 -f 2 -t 1 zipped_bench.ZippedBench"
:Dies zeigt, dass die
zipped
Version etwa 80% mehr Durchsatz erzielt, was wahrscheinlich mehr oder weniger Ihren Messungen entspricht.Zuordnungen messen
Sie können jmh auch bitten, Zuordnungen zu messen mit
-prof gc
:… Wo
gc.alloc.rate.norm
ist wahrscheinlich der interessanteste Teil, der zeigt, dass diezip
Version mehr als dreimal so viel zuweist wiezipped
.Imperative Implementierungen
Wenn ich wüsste, dass diese Methode in extrem leistungsabhängigen Kontexten aufgerufen werden würde, würde ich sie wahrscheinlich folgendermaßen implementieren:
Beachten Sie, dass im Gegensatz zur optimierten Version in einer der anderen Antworten
while
anstelle von a verwendet wird,for
da derfor
Wille weiterhin in Scala-Sammlungsvorgängen enthalten ist. Wir können diese Implementierung (withWhile
), die optimierte (aber nicht vorhandene) Implementierung (withFor
) der anderen Antwort ( ) und die beiden ursprünglichen Implementierungen vergleichen:Das ist ein wirklich großer Unterschied zwischen der imperativen und der funktionalen Version, und alle diese Methodensignaturen sind genau identisch und die Implementierungen haben dieselbe Semantik. Es ist nicht so, dass die imperativen Implementierungen den globalen Status usw. verwenden. Obwohl die
zip
undzipped
-Versionen besser lesbar sind, glaube ich persönlich nicht, dass die imperativen Versionen in irgendeiner Weise gegen den "Geist von Scala" sind, und ich würde nicht zögern sie selbst zu benutzen.Mit tabellarisch
Update: Ich
tabulate
habe dem Benchmark eine Implementierung hinzugefügt , die auf einem Kommentar in einer anderen Antwort basiert:Es ist viel schneller als die
zip
Versionen, obwohl immer noch viel langsamer als die zwingenden:Dies ist, was ich erwarten würde, da das Aufrufen einer Funktion nicht von Natur aus teuer ist und der Zugriff auf Array-Elemente über den Index sehr billig ist.
quelle
Erwägen
lazyZip
anstatt
zip
Scala 2.13 zugunsten von hinzugefügt
lazyZip
.zipped
zipped
(und daherlazyZip
) ist schneller alszip
weil, wie von Tim und Mike Allen erklärt ,zip
gefolgt vonmap
zwei getrennten Transformationen aufgrund von Strenge führt, währendzipped
gefolgt vonmap
einer einzelnen Transformation aufgrund von Faulheit auf einmal ausgeführt wird.zipped
gibtTuple2Zipped
und analysiertTuple2Zipped.map
,wir sehen die beiden Sammlungen
coll1
undcoll2
sind iteriert und bei jeder Iteration der Funktionf
übergebenmap
wird , auf dem Weg angewandtohne zwischengeschaltete Strukturen zuordnen und transformieren zu müssen.
Anwenden von Travis' Benchmark - Methode, hier ist ein Vergleich zwischen neuen
lazyZip
und veraltete ,zipped
wogibt
lazyZip
scheint etwas besser zu funktionieren alszipped
aufArraySeq
. Interessanterweise sollten Sie bei VerwendunglazyZip
von "Die Leistung erheblich beeinträchtigen"Array
.quelle
Aufgrund der JIT-Kompilierung sollten Sie bei der Leistungsmessung immer vorsichtig sein. Ein wahrscheinlicher Grund ist jedoch, dass Sie
zipped
faul sind undArray
während desmap
Aufrufs Elemente aus den ursprünglichen Vaules extrahieren , während Siezip
ein neuesArray
Objekt erstellen und dannmap
das neue Objekt aufrufen .quelle