PHP array_shift – Alternative für mehr Performance

Ich habe vor einiger Zeit die Aufgabe „Equal Stacks“ auf HackerRank gelöst und mir dabei sehr schwer getan, obwohl die Aufgabe als „Easy“ eingestuft wurde. Das grundlegende Problem wurde schnell erkannt und gelöst und viele der Tests konnten auch erfolgreich abgeschlossen werden, andere jedoch wurden nur mit einem Timeout beendet. Die Logik an sich war richtig und auch performant genug daher habe ich mir die Array-Funktionen etwas näher angeschaut um evtl. dort Probleme zu erkennen. Das Problem konnte auch recht schnell durch die Verwendung der Funktion array_shift  erkannt werden. Diese Funktion entfernt das erste Element von einem Array und gibt dessen Wert zurück. Anschließend werden alle verbleibenden Elemente neu indexiert. Bei wenigen Elementen ist das auch kein Problem. Jedoch bei einem Array mit vielen tausenden von Elementen kann diese Neu-Indexierung sehr viel Zeit in Anspruch nehmen. Dies kann auch in den Kommentaren auf php.net gelesen werden:

Using array_shift over larger array was fairly slow.  It sped up as the array shrank, most likely as it has to reindex a smaller data set.

For my purpose, I used array_reverse, then array_pop, which doesn’t need to reindex the array and will preserve keys if you want it to (didn’t matter in my case).

Using direct index references, i.e., array_test[$i], was fast, but direct index referencing + unset for destructive operations was about the same speed as array_reverse and array_pop.  It also requires sequential numeric keys.

http://php.net/manual/en/function.array-shift.php#86783

Ich habe also meinen Code wie in diesem Kommentar beschrieben angepasst. So habe ich den Array einmalig mit der Funktion array_reverse  umgedreht. So befindet sich nun das letzte Element an erster Stelle und das erste Element an letzter Stelle. Anschließend kann die Funktion array_pop  verwendet werden, um das letzte Element zu entfernen und dessen Wert zurückzugeben. Hierfür ist keine Neu-Indexierung notwendig da lediglich das letzte Element entfernt wird. Nachdem ich meine Lösung entsprechend angepasst habe, wurden auch die mit einem Timeout beendeten Tests erfolgreich abgeschlossen.

Dieses Kommentar hat mir auf jeden Fall geholfen, die Aufgabe zu lösen und die Tests erfolgreich zu bestehen. Ein Nutzer auf HackerRank hat dies auf einem älteren PC noch einmal getestet und eine erhebliche Verbesserung der Performance feststellen können und selbst die Aufgabe lösen können:

I was testing my code (in an old computer) with 10k items in each stack and my running time was alittle over 14 seconds, after switching array_shift for array_pop my runing time is now something arround 110 ms :O!!!

https://www.hackerrank.com/challenges/equal-stacks/forum/comments/155521

sebastianbrosch

Ich bin gelernter Fachinformatiker und konnte Erfahrungen in HTML, CSS, JavaScript, jQuery, PHP sowie VB.NET sammeln. In diesem Blog schreibe ich über meine Probleme und Erfahrungen sowie Aritkel aus dem Gebiet der Anwendungsentwicklung.

Das könnte Dich auch interessieren...

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.