PHPGangsta - Der praktische PHP Blog

PHP Blog von PHPGangsta


Ergebnisse der Array-Umbau-Aufgabe

with 42 comments

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:

AutorNotices/
Warnings
Korrektheit
Compress/Decompress
Laufzeit Compress
(in s)
Laufzeit Decompress
(in s)
smaresNeinJa/Ja2,450
maxNeinJa/Nein0,0230,044
Oliver 2NeinJa/Ja0,0230,047
Stefan GaudesNeinJa/Ja0,0270,091
Lena FuchsNeinJa/Ja0,03724,868
UweNeinJa/Ja0,0642,334
DukeNightcrawlerNeinJa/Ja0,0730,051
sprainNeinJa/Ja0,1060,052
WasrunNeinJa/Ja0,1290,111
SebastianNeinJa/Ja0,1912,162
DanielNeinJa/Ja0,2044,212
Tobias RohdeNeinJa/Ja0,2100,083
Oliver 1NeinJa/Ja0,2500,277
PatrickNeinJa/Ja0,2620,125
frankNeinJa/Ja0,2662,296
PaloranNeinNein/Ja0,2740,057
ArtemNeinJa/Ja0,2920,225
Martin SchäpkerNeinJa/Ja0,4234,650
PhilNeinJa/Ja0,59923,710
chuckySTARNeinJa/Ja2,9562,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:

Daniel: compress 0.20110702514648s
Daniel: decompress 4.9928300380707s
Patrick: compress 0.26004981994629s
Patrick: decompress 0.12317204475403s
smares: decompress 2.2549409866333s
chuckySTAR: compress 2.9389398097992s
chuckySTAR: decompress 2.9813008308411s
Phil: compress 0.60249018669128s
Phil: decompress 24.294103860855s
frank: compress 0.27095603942871s
frank: decompress 2.3924989700317s
Paloran: compress 0.28259706497192s
FEHLER ENTDECKT!
Tobias: compress 0.21055603027344s
Tobias: decompress 0.083432912826538s
Lena: compress 0.036540985107422s
Lena: decompress 26.168859004974s
Martin: compress 0.43871307373047s
Martin: decompress 4.735780954361s
Artem: compress 0.29701495170593s
Artem: decompress 0.22398996353149s
Oliver1: compress 0.2545440196991s
Oliver1: decompress 0.27919983863831s
Oliver2: compress 0.023215097427368s
Oliver2: decompress 0.047801971435547s
Wasrun: compress 0.13014006614685s
Wasrun: decompress 0.11161994934082s
Duke: compress 0.075024843215942s
Duke: decompress 0.051630973815918s
Max: compress 0.024842023849487s
Max: decompress 0.045427083969116s
FEHLER ENTDECKT!
Uwe: compress 0.065070867538452s
Uwe: decompress 2.404002904892s
Stefan: compress 0.027276992797852s
Stefan: decompress 0.090695858001709s
Sebastian: compress 0.18792200088501s
Sebastian: decompress 2.4671220779419s
sprain: compress 0.1064178943634s
sprain: decompress 0.052311897277832s

Written by Michael Kliewe

Februar 9th, 2011 at 10:25 am

Posted in PHP

Tagged with , ,

42 Responses to 'Ergebnisse der Array-Umbau-Aufgabe'

Subscribe to comments with RSS or TrackBack to 'Ergebnisse der Array-Umbau-Aufgabe'.

  1. Doch immerhin 4. respektive 2. schnellste Lösung xD

    DukeNightcrawler

    9 Feb 11 at 11:41

  2. 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

  3. 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

  4. 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

  5. Schön 🙂

    Oliver

    9 Feb 11 at 15:38

  6. @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

  7. @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

  8. 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

  9. 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

  10. 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

  11. @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

  12. Wie sieht es denn mit dem Speicherverbrauch der Lösungsansätze aus?

    Jens

    9 Feb 11 at 23:13

  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

  14. 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

  15. @Tobias: upgedated, die Notice ist weg, Geschwindigkeit ist gleich geblieben.

    Michael Kliewe

    9 Feb 11 at 23:46

  16. 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

  17. @Martin: Bei mir klappts wunderbar. Stürzt Firefox komplett ab? Welche Firefox Version hast du?

    Michael Kliewe

    10 Feb 11 at 00:17

  18. Firefox 3.6.13 allerdings mit einer Menge Plugins aufgerüstet….

    Martin Schäpker

    10 Feb 11 at 00:21

  19. 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

  20. stürzt natürlich.. tztzt

    Martin Schäpker

    10 Feb 11 at 00:24

  21. @Oliver Ah, danke. Sollte mehr testen 😉

    http://pastie.org/1547043

    max

    10 Feb 11 at 00:26

  22. 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

  23. 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

  24. Hm, irgendwie kommt meine neue Version gar nicht an 🙁

    Oliver

    10 Feb 11 at 16:45

  25. 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

  26. So, einen hätte ich dann noch 🙂

    http://pastie.org/1551161

    Oliver

    11 Feb 11 at 02:42

  27. Mein letzter Code. Mehr kann ich nicht raus holen.

    http://pastie.org/1551446

    Oliver

    11 Feb 11 at 05:28

  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 […]

  29. @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

  30. 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

  31. 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

  32. 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

  33. 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

  34. 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

  35. 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

  36. 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

  37. 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

  38. 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

  39. 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

  40. 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

  41. @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

  42. @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

Leave a Reply

You can add images to your comment by clicking here.