Embedded Files
17. April. 2020 - Oliver Eglseder
Arrays in PHP zu sortieren ist sehr einfach. Es gibt zahlreiche Funktionen, die nach unterschiedlichsten Kriterien ein Array neu sortieren können. Es gibt jedoch keine Funktion um Elemente eines Arrays in einer bestimmten Reihenfolge anzuordnen.
Ich möchte zwei Methoden vorstellen, wie man eine Anordnung möglichst schnell mit geringsten Mittel erreichen kann.
Der Testsieger für assoziative Arrays
"array_flip, array_column, array_replace"
Diese Methode nutzt den gleichen Effekt aus dem ersten Beispiel, ist aber noch etwas schneller. Allerdings eignet sie sich nur, wenn die Elemente des Arrays assoziative Arrays sind. array_column mit null als zweites argument und id als drittes erzeugt ein array, dessen Keys durch den Wert von id in jedem Eintrag ausgetauscht wurde.
Der Testsieger für Objekte
"array_flip, foreach"
Diese Methode nutzt die Tatsache aus, dass überschriebene Keys im Array ihre Position behalten. Dies ermöglicht es ein passend geordnetes Array durch array_flip herzustellen. Es müssen nur noch die Werte im resultierendem Array anhand des Keys durch die Datensätze überschrieben werden.
Wie schnell sind diese Methoden tatsächlich? Und wie schnell ist die akzeptierte Antwort auf Stackoverflow?
"usort (from stackoverflow)"
Akzeptierte Antwort auf Stackoverflow: https://stackoverflow.com/a/11145568
"prepared array with 2 foreach"
Hier wird das Array über ein foreach mit den Keys in der richtigen Reihenfolge vorbelegt, dann werden die Werte anhand der Keys eingesetzt.
"array_column + foreach"
Die Elemente werden dem geordnetem Array in der Reihenfolge hinzugefügt in der sie erwartet werden.
Hinweis: Ein unset auf das verwendete Element damit bei jeder Iteration ein Element weniger in dem zu durchsuchendem Array ist hat erst ab 1.000.000 Einträge im Array einen positiven Effekt.
"ksort position indexed array"
Hier wird ein Array erzeugt dessen Keys die Position der id in $order ist. Dann wird das Array nach Keys sortiert und die Einträge sind in der richtigen Reihenfolge.
"array_column, array_map"
Die Keys im vorsortierten Array werden mittels array_map überschrieben.
"array_column, array_search, array_walk"
Nicht nur die zweit-komplizierteste, sondern auch die zweit-langsamste Methode. Eine Erklärung muss nicht stattfinden, da dieser Code aus Gründen der Performance und Lesbarkeit nicht verwendet werden sollte.
Performancevergleich der verschiedenen Methoden bei Anwendung auf Arrays verschiedener Größen.
Dieses Diagramm ist Logarithmisch. Obwohl der Abstand zwischen "usort" und "array_column, array_search, array_walk" nicht sehr groß erscheint bedeutet er trotzdem einen Unterschied von knapp 37 Stunden bei einer Array-Länge von 10.000 Elementen.
Für die Messung dieser Zeiten wurden die Durchläufe bei großeren Arrays reduziert, daher nimmt die Messgenauigkeit mit größeren Arrays ab, diese Abweichung fällt bei diesen großen Zeiten jedoch nicht mehr ins Gewicht.
Das Diagramm betrachtend kann man sagen, dass der Gewinner des Perfomance-Tests eindeutig die ist, die array_replace verwendet (Schwarze Linie). Der zweite Sieger ist "array_flip, foreach" (Lila Linie), da nur diese Variante auch mit Objekten umgehen kann.
Das Schlusslicht des Vergleichs ist die akzeptierte Antwort von Stackoverflow, die auch die meisten Upvotes hat. Das diese Methode so schlecht abschneidet liegt nicht nur daran, dass usort intern den Quicksort Algorithmus verwendet und dieser mehrere Iterationen benötigt um ein Array zu sortieren als es Elemente besitzt.
usort ist zum aufsteigenden/absteigenden Sortieren gedacht, nicht zum Ordnen eines Arrays. Weiterhin ist die Benutzung von array_search der Performancekiller schlechthin.
Die Komplexität bei usort ist auch im schlimmsten Fall weitaus schlechter als in allen anderen Fällen. Im worst case liegt sie bei O(n * log(n)). So kann es passieren dass bei einem Array mit 15 Einträgen bis zu 416 Ausführungen von array_search stattfinden. array_search hat selbst eine Komplexität von O(n).
Alle anderen Methoden (außer die Zweite Methode mit array_search) haben annähernd eine Komplexität von O(1).
Page updated
Report abuse