Ergebnisse der Array-Umbau-Aufgabe
Bis heute morgen wurden von 18 Lesern 19 Lösungen zur vorgestrigen Array-Umbau-Aufgabe eingereicht, und ich habe alle Funktionen durchlaufen lassen mit einem Testarray. Nun möchte ich hier einige Werte zur Korrektheit und Laufzeit veröffentlichen.
Dazu habe ich ein Testscript erstellt, welches auf GitHub einsehbar ist, und wo ich alle Funktionen mit einem 29358 Elemente großen Array laufen lasse und dann die Laufzeit und Korrektheit der Umwandlungen überprüfe.
Hier die sortierbare Tabelle:
| Autor | Notices/ Warnings | Korrektheit Compress/Decompress | Laufzeit Compress (in s) | Laufzeit Decompress (in s) |
|---|---|---|---|---|
| smares | Nein | Ja/Ja | 2,450 | |
| max | Nein | Ja/Nein | 0,023 | 0,044 |
| Oliver 2 | Nein | Ja/Ja | 0,023 | 0,047 |
| Stefan Gaudes | Nein | Ja/Ja | 0,027 | 0,091 |
| Lena Fuchs | Nein | Ja/Ja | 0,037 | 24,868 |
| Uwe | Nein | Ja/Ja | 0,064 | 2,334 |
| DukeNightcrawler | Nein | Ja/Ja | 0,073 | 0,051 |
| sprain | Nein | Ja/Ja | 0,106 | 0,052 |
| Wasrun | Nein | Ja/Ja | 0,129 | 0,111 |
| Sebastian | Nein | Ja/Ja | 0,191 | 2,162 |
| Daniel | Nein | Ja/Ja | 0,204 | 4,212 |
| Tobias Rohde | Nein | Ja/Ja | 0,210 | 0,083 |
| Oliver 1 | Nein | Ja/Ja | 0,250 | 0,277 |
| Patrick | Nein | Ja/Ja | 0,262 | 0,125 |
| frank | Nein | Ja/Ja | 0,266 | 2,296 |
| Paloran | Nein | Nein/Ja | 0,274 | 0,057 |
| Artem | Nein | Ja/Ja | 0,292 | 0,225 |
| Martin Schäpker | Nein | Ja/Ja | 0,423 | 4,650 |
| Phil | Nein | Ja/Ja | 0,599 | 23,710 |
| chuckySTAR | Nein | Ja/Ja | 2,956 | 2,966 |
Hinzu kommt eine Lösung von Andre in Haskell geschrieben, die ich aber nicht testen konnte.
Vielen Dank an alle, die mitgemacht haben. Wenn man sich die unterschiedlichen und vor allem auch die schnellsten Lösungen anschaut, ist man doch erstaunt wie man diese doch einfache Aufgabe lösen kann, und dass die einfachste oder naheliegendste Funktion nicht immer die schnellste ist.
Ihr könnt natürlich weiterhin eure Lösungen posten, ich (oder du vielleicht?) kann das GitHub-Repository von Zeit zu Zeit updaten.
Hier noch die Ausgabe des Testscripts:
https://github.com/PHPGangsta/Array-conversion-script/blob/master/README
Doch immerhin 4. respektive 2. schnellste Lösung xD
DukeNightcrawler
9 Feb 11 at 11:41
also dafür das ich nicht auf optimierung geachtet habe bin ich mit meinen platz auch zufrieden^^
wäre cool solche wettbewerbe öffters zu machen, da man auch viel lernt wenn man sich dann die anderen Lösungen anguckt
Wasrun
9 Feb 11 at 12:34
Besser spät als nie!
Habe noch eine Lösung mit einer Lambda Funktion beim „unshorten“ erstellt.
http://pastie.org/1544779
Kannst ja noch in deiner Liste ergänzen wenn du willst. Hat auf jedenfall Spaß gemacht, mehr davon 😉
Sebastian Bruckner
9 Feb 11 at 14:13
Haha ^^
Hätte nicht gedacht, dass array_splice sowas von viel Performance zieht!
Ich schäme mich für meine Laufzeit 🙁
chuckySTAR
9 Feb 11 at 15:08
Schön 🙂
Oliver
9 Feb 11 at 15:38
@WasRun, Sebastian: Ähnliche Probleme gibt es in regelmäßigen Abständen auf Programming Praxis [1]. Wer gerne mathematische Probleme mit dem Computer löst, wird bei Projekt Euler [2] sicherlich auch genügend Programmiermöglichkeiten finden.
[1] http://programmingpraxis.com/
[2] http://projecteuler.net/
Andre
9 Feb 11 at 15:53
@Andre
fand es eher cool das hier in einen zeitlich beregnzen raum eine Lösung für ein problem gefunden werden muss und dabei auf preformance und nicht auf programmierschönheit geachtet wird.
Solche Projekte wo es schon 2000 Lösungen gibt und es nur darum geht irgendwelche Lösungen für komplizierte mathematische sachen zu finden, find ich recht langweilig
Wasrun
9 Feb 11 at 16:13
coole Aktion, und der Tip von @Andre ist auch gut wenn man mal langeweile hat 🙂
das array_splice soviel Performance kostet, schon erschreckend. Programmierer lernen halt nie aus.
Martin Schäpker
9 Feb 11 at 22:01
Soweit ich das sehe, schreibt array_splice den Index des Arrays neu. Damit schwindet dann die Geschwindigkeit. Bei so großen Arrays wie im Test ist es dann richtig tödlich, weil bei 1000 Werten, müssen 1000 Keys geändert werden.
Meine Funktion war am Anfang übrigens wesentlich langsamer als Lenas, weshalb ich hier und da etwas tricksen musste. 😉
Oliver
9 Feb 11 at 22:39
Geschwindigkeit stimmt, Korrektheit nicht. Da musste ich nochmal ran 😉
http://pastie.org/1546647
compress() unterbietet die Zeit meine alter Funktion ein wenig, das sieht aber nicht schön aus… da kann man evtl. noch etwas optimieren.
Bei decompress() sehe ich nichts schnelleres als Olivers Lösung, die ist super!
Halten wir als Erkenntnis fest:
Ein if mit (abs($a-$b) == 1) ist langsam im Vergleich zu ($a+1 == $b && $a-1 == $b)
max
9 Feb 11 at 22:48
@max
Danke, Deine neue Funktion gibt ein falsches Ergebnis, wenn eine Reihe am Ende ist.
array(13,81,80,79,78,77,76,19,40,41,42,43,44,45,48,49)
wird zu
Array
(
[0] => 13
[1] => 81-76
[2] => 19
[3] => 40-45
[4] => 48-48
[5] => 49
)
Ansonsten wirklich sehr schnell. 🙂
Oliver
9 Feb 11 at 22:58
Wie sieht es denn mit dem Speicherverbrauch der Lösungsansätze aus?
Jens
9 Feb 11 at 23:13
@Sebastian: hinzugefügt
@max: Da Oliver noch einen Fehler gefunden hat warte ich noch mit einer Aktualisierung deiner Funktionen bis deine neue Version da ist 😉
@Jens: Dazu müßte man sie alle einzeln laufen lassen und mit memory_get_peak_usage() messen. Alle würden sich freuen wenn das jemand übernehmen könnte! Einfach das GitHub Repository forken und danach einen Pull-Request senden, ich merge es dann rein. Oder wenn das zu kompliziert ist das zip-File mit den Dateien hier posten, dann uploade ich es auf GitHub.
Michael Kliewe
9 Feb 11 at 23:23
Kleine Korrektur meiner Lösung:
http://pastie.org/1546834
Jetzt taucht auch keine Notice mehr aus. Im Grunde war es nur der Positionstausch von Abfragebedingungen. Von der Geschwindigkeit her hat sich nicht viel getan, zumindest nach meiner Messmethode (microtime nach einem Funktionsaufruf minus microtime vor dem Funktionsaufruf).
Tobias Rohde
9 Feb 11 at 23:33
@Tobias: upgedated, die Notice ist weg, Geschwindigkeit ist gleich geblieben.
Michael Kliewe
9 Feb 11 at 23:46
mal so eine Anmwerkung wenn ich auf gist gehe und dann über den backbutton zurück dann steigt der Firefox jedesmal aus, liegt das an meinem System oder ist das ein allgemeins Problem?
Martin Schäpker
10 Feb 11 at 00:09
@Martin: Bei mir klappts wunderbar. Stürzt Firefox komplett ab? Welche Firefox Version hast du?
Michael Kliewe
10 Feb 11 at 00:17
Firefox 3.6.13 allerdings mit einer Menge Plugins aufgerüstet….
Martin Schäpker
10 Feb 11 at 00:21
und ja der stürst komplett ab… sendet nur noch eine Fehlermeldung und sagt dann tschüss…
Martin Schäpker
10 Feb 11 at 00:23
stürzt natürlich.. tztzt
Martin Schäpker
10 Feb 11 at 00:24
@Oliver Ah, danke. Sollte mehr testen 😉
http://pastie.org/1547043
max
10 Feb 11 at 00:26
Ich leg dann mal nach, weil so einen großen Abstand kann ich dann doch nicht stehen lassen. Es ist ca. 25 % schneller als das letzte und kommt damit ziemlich nah an max seins dran. 🙂
http://pastie.org/1547941
Oliver
10 Feb 11 at 07:56
habe meine Lösung auch nochmal korrigiert
http://www.pastie.org/1548059
jetzt schneller und ohne Notice
Stefan Gaudes
10 Feb 11 at 09:01
Hm, irgendwie kommt meine neue Version gar nicht an 🙁
Oliver
10 Feb 11 at 16:45
So, ich habe mir mal die Mühe gemacht, und den Speicherverbrauch gemessen. Im Großen und ganzen liegen alle relativ dicht beeinander. Schade nur, dass Sebastian, der ein Kollege von mir ist, effizienter war als ich. 🙂
smares (326216 Byte; nur uncompress)
Oliver 2 (330264 Byte)
Daniel (330304 Byte)
Paloran (331600 Byte)
chuckySTAR (331792 Byte)
Lena Fuchs (331904 Byte)
Phil (333064 Byte; Ergebnis scheint in beide Richtungen nicht korrekt zu sein.)
Artem (337064 Byte)
Sebastian (337704 Byte)
DukeNightcrawler (346656 Byte)
max (350760 Byte)
Tobias Rohde (350944 Byte)
Stefan Gaudes (351048 Byte)
frank (351184 Byte)
Uwe (351192 Byte)
Patrick (351216 Byte)
Wasrun (351384 Byte)
Oliver 1 (351400 Byte)
Martin Schäpker (352504 Byte)
Tobias Rohde
10 Feb 11 at 23:31
So, einen hätte ich dann noch 🙂
http://pastie.org/1551161
Oliver
11 Feb 11 at 02:42
Mein letzter Code. Mehr kann ich nicht raus holen.
http://pastie.org/1551446
Oliver
11 Feb 11 at 05:28
[…] Eine simple Aufgabenstellung erzeugte 19 Lösungsansätze von Lesern, mit äußerst unterschiedlichen Laufzeitverhalten: https://www.phpgangsta.de/ergebnisse-der-array-umbau-aufgabe […]
Lasset die Spiele beginnen « think.ahead
11 Feb 11 at 09:47
@Oliver: Ich habe gerade 4 Kommentare von dir freigeschaltet, Akismet meinte das wäre Spam. Frag mich nicht woran das lag, vielleicht zu wenig Text und zu viele Links? 😉
Michael Kliewe
12 Feb 11 at 02:31
Verdammter Spammer, ich 🙂
Ich hab da übrigens richtig Schwein gehabt. Die Funktion von max skaliert nämlich besser. Bei kleinen Arrays ist meine Funktion schneller – bei großen seine. 10.000 ist grade noch in dem Bereich, wo es minimal schneller ist. *gg*
Meinen tiefen Respekt für seine Vorlage.
Oliver
12 Feb 11 at 04:22
Und wenn max seine neueste Version (http://pastie.org/1547043) noch weiter optimiert dann schafft er nochmals eine Verbesserung in der Geschwindigkeit von 11%.
– Deklaration des $ret-Array
– Präinkrement in der for-Schleife
– ===-Operator anstatt dem ==-Operator (achten auf 32-Bit/PHP_MAX_INT)
Version Original: 0.013093948364258s
Version Modifiziert: 0.011685848236084s
Wobei das wieder typische Mikro-Optimierungen sind. Wichtiger ist, wenn man von Anbeginn des Programmierens, „logisch“ korrekten Code schreibt.
Beispiel:
if (schnelleFunktion() || langsameFunktion())
if (langsameFunktion() || schnelleFunktion())
Die erste Variante ist schneller als die zweite da bei der Oder-Verknüpfung nur eine Bedingung erfüllt sein muss. So könnte man z.B. die Anfragen an die Datenbanken vermindern.
phpgangsta
14 Feb 11 at 00:31
Habe den Link zu http://phpbar.de/w/Code-Optimierung vergessen, dort sind noch weitere Tipps wie man seinen Code optimieren kann. Auf http://net-beta.net/ubench/ sind auch nochmals Benchmarks verschiedener Vorgehensweisen aufgelistet.
phpgangsta
14 Feb 11 at 00:37
Das ist interessant. Das hier sieht jetzt extrem seltsam aus, aber dieses Konstrukt ist etwa 25 % schneller als is_int().
if((int)$o===$o)) ...
Mit ein paar Änderungen sollte es jetzt bei etwa 0.0329 raus kommen.
http://pastie.org/1564671
Oliver
15 Feb 11 at 01:16
So, schneller krieg ich meine Lösung nicht:
compress 0.038938999176025s
decompress 0.01375412940979s
http://www.pastie.org/1566441
DukeNightcrawler
15 Feb 11 at 15:13
Ob das seltsam ist sei mal dahingestellt, da wir eben mit der schwachen/dynamischen Typisierung arbeiten. Ansonsten ist das Type-Casting mit die effizienteste Variante den Typ zu verändern ((array)$object). Ich habe gesehen, dass Du deine Array-Schlüssel als String behandelst was Du eigentlich gar nicht machen musst/solltest, da der Standard-Typ des Schlüssels ein Integer ist, sinnvoll ist es erst den Schlüssel als String zu behandeln wenn Du den maximalen Integerwert überschreitest.
phpgangsta
15 Feb 11 at 15:37
Ich hatte es hier ausprobiert. $a[‚1‘] ist minimal schneller als $a[0] – ist jetzt kein Riesen Performancegewinn, aber schon messbar.
Seltsam fand ich nur, dass so ein seltsames Konstrukt schneller ist, als die eigentlich vorgesehene Funktion. Die Klammern wirken sich übrigens auch aus. Lässt man sie weg, sinkt die Ausführungszeit.
Oliver
15 Feb 11 at 15:46
Stimmt, habe es eben ausprobiert, aber bei größeren Integerwerten ist dies langsamer. 10 Millionen Iterationen mit 100000000 = 1.0333909988403s und mit ‚100000000‘ = 1.352774143219s. Man sollte dennoch vorsichtig sein wie man auf die Array-Schlüssel zugreift bzw. sie deklariert werden, weil dies schnell zu Verwirrung führen kann, siehe Beispiel unten. Um auf die Performance zurückzukommen das Äquivalent von if((int)$o===$o) wäre if(intval($o)===$o), Funktionen sind in PHP aber immer?! langsamer als Konstrukte?!. Wenn Du aber nun deine eigene isInt-Funktion erstellst (function isInt($o) { return (int)$o===$o; } ) wäre diese wieder fast doppelt so langsam wie is_int(). Bezüglich dem Type-Casting steht im Manual „Type casting in PHP works much as it does in C: the name of the desired type is written in parentheses before the variable which is to be cast.“. Ansonsten ist das Type-Casting eine feine Sache.
var_dump(array_keys(array(‚1‘ => 0, ‚2147483647‘ => 0, 2147483648 => 0, ‚2147483648‘ => 0)));
array(4) {
[0]=>
int(1)
[1]=>
int(2147483647)
[2]=>
int(-2147483648)
[3]=>
string(10) „2147483648“
}
phpgangsta
15 Feb 11 at 16:41
Ich habe mir im Laufe der Jahre angewöhnt immer ‚1‘ zu schreiben. KA warum 🙂
Bis auf solche Sachen hier, ist es ja meistens auch uninteressant, weil die Unterschiede in der Performance bei einzelnen Aufrufen eh keine Rolle spielen. Das mit den Funktionen wusste ich schon, allerdings, dass es so einen krassen Unterschied macht, hätte ich nicht gedacht.
Oliver
15 Feb 11 at 21:02
Noch schneller als Max, trotz:
„- Deklaration des $ret-Array
– Präinkrement in der for-Schleife
– ===-Operator anstatt dem ==-Operator (achten auf 32-Bit/PHP_MAX_INT)“
Ist aber so ziemlich die gleiche Funktion ^^
http://pastie.org/1585872
Max: compress 0.010066032409668s
Neu: compress 0.0096249580383301s
Jetzt gehts doch wirklich nicht mehr schneller, oder?
chuckySTAR
20 Feb 11 at 16:19
Mir fällt gerade auf, dass es noch so einige Spezialfälle gibt mit dem Array:
$origNumbers = array(13,81,80,79,78,79,77,76,19,40,41,42,43,44,45);
$origCompressed = array(13,“81-78″,79,“77-76″,19,“40-45″);
Das Ergebnis sieht etwas überraschend aus ^^
Daniel: compress 6.2942504882812E-5s
FEHLER ENTDECKT!
Daniel: decompress 5.6028366088867E-5s
Patrick: compress 5.2928924560547E-5s
Patrick: decompress 4.0054321289062E-5s
smares: decompress 4.6014785766602E-5s
chuckySTAR: compress 3.0994415283203E-5s
Phil: compress 7.7962875366211E-5s
Phil: decompress 3.504753112793E-5s
frank: compress 5.6982040405273E-5s
FEHLER ENTDECKT!
frank: decompress 3.3140182495117E-5s
Paloran: compress 3.0994415283203E-5s
FEHLER ENTDECKT!
Tobias: compress 4.6014785766602E-5s
FEHLER ENTDECKT!
Tobias: decompress 3.9100646972656E-5s
Lena: compress 3.1948089599609E-5s
FEHLER ENTDECKT!
Lena: decompress 3.9100646972656E-5s
Martin: compress 9.7036361694336E-5s
FEHLER ENTDECKT!
Martin: decompress 4.1007995605469E-5s
Oliver1: compress 0.00048589706420898s
FEHLER ENTDECKT!
Oliver1: decompress 0.00021886825561523s
Oliver2: compress 3.1948089599609E-5s
Oliver2: decompress 2.598762512207E-5s
Wasrun: compress 5.0067901611328E-5s
FEHLER ENTDECKT!
Wasrun: decompress 3.7908554077148E-5s
Duke: compress 4.6968460083008E-5s
Duke: decompress 3.0040740966797E-5s
Max: compress 2.1934509277344E-5s
FEHLER ENTDECKT!
Uwe: compress 3.814697265625E-5s
Uwe: decompress 3.504753112793E-5s
Stefan: compress 2.8848648071289E-5s
Stefan: decompress 3.3140182495117E-5s
sprain: compress 2.6941299438477E-5s
FEHLER ENTDECKT!
sprain: decompress 2.598762512207E-5s
Und noch mal eine schnellere Komprimierungsfunktion:
https://gist.github.com/815282
chuckySTAR
21 Feb 11 at 22:47
@Tobias Rohde: Kannst du dein Speicherverbrauchs-Script veröffentlichen? Irgendwie kommen mir die Zahlen falsch vor, die werden alle nur größer, kann es sein dass du einfach memory_get_peak_usage() dazwischengebaut hast? Um die richtigen Werte zu messen muss man jeden Algorithmus in einem eigenen Scriptaufruf messen.
@chuckySTAR: Du meinst den Spezialfall, dass das letzte Element Teil einer Range ist? Ja, das ist korrekt, einige Algorithmen scheinen das nicht richtig abzufangen.
Michael Kliewe
22 Feb 11 at 09:40
@Michael: Ich habe jedes Skript einzeln laufen lassen und in jedem memory_get_peak_usage() ausgeben lassen. Die Werte werden deshalb immer größer, weil ich sie von Hand der Reihe nach sortiert habe, damit jeder weiß, wo er steht.
Tobias Rohde
1 Mrz 11 at 01:06