PHPGangsta - Der praktische PHP Blog

PHP Blog von PHPGangsta


Kleine Aufgabe: Ein Array umbauen

with 43 comments

Eine kleine Aufgabe, die es zu lösen gibt. Ich habe folgendes Ausgangsarray, das nur positive ganze Zahlen enthält, die nur einmal vorkommen:

$numbers = array(13,81,80,79,78,77,76,19,40,41,42,43,44,45,48);

und möchte:

$numbers = array(13,"81-76",19,"40-45",48);

Es sollen also alle zusammenhängenden Arrayelemente zusammengefasst werden, um das Array kleiner zu machen (weniger Speicherplatz/Traffic).

In einem zweiten Schritt soll dann dieses Array wieder zurück umgewandelt werden in das Original:

$numbers = array(13,81,80,79,78,77,76,19,40,41,42,43,44,45,48);

Die Reihenfolge soll beibehalten werden, sodass es möglich ist das Array vor- und zurück umzuwandeln.

Wer hat die schönste und einfachste Lösung für die beiden Funktionen? Lösungen per Gist oder Pastie etc. posten.

Written by Michael Kliewe

Februar 7th, 2011 at 8:11 pm

Posted in PHP

Tagged with , ,

43 Responses to 'Kleine Aufgabe: Ein Array umbauen'

Subscribe to comments with RSS or TrackBack to 'Kleine Aufgabe: Ein Array umbauen'.

  1. Daniel

    7 Feb 11 at 21:42

  2. Sieht jetzt nicht so toll aus, aber sollte funktionieren 😉
    https://gist.github.com/9020b83e6a13f51c24ed

    Patrick

    7 Feb 11 at 21:45

  3. Omg, jetzt wo ich Daniel’s seh :X
    Mir fiel nur array_fill() statt range() ein 😀
    Die Variante mit abs() sieht auch etwas eleganter aus als mein Konstrukt :)

    Patrick

    7 Feb 11 at 21:54

  4. Hier mal meine uncompress-Methode:

    http://pastie.org/1538370

    smares

    7 Feb 11 at 22:01

  5. Meine super schnelle kleine Lösung (Ok, nicht gemessen ^^):
    https://gist.github.com/815282
    :)

    chuckySTAR

    7 Feb 11 at 22:43

  6. Phil

    7 Feb 11 at 22:46

  7. Ich schlage übrigens vor, das folgendes Array getestet wird: 13,81,80,79,78,79,77,76,19,40,41,42,43,44,45,48. Also mit einer weiteren 79 nach der 78. :-)

    Phil

    7 Feb 11 at 22:56

  8. Hm, ein mal + 1 zu viel. Jetzt gehts auch mit dem neuen Array ^^

    chuckySTAR

    7 Feb 11 at 23:05

  9. frank

    7 Feb 11 at 23:08

  10. So, ich habe mich auch mal daran versucht…ist nichts besonders tolles dabei herausgekommen, aber für mich und meine Verhältnisse eigentlich ganz in Ordnung 😉

    http://pastie.org/1538647

    die Kommentare sollte man am besten gar nicht beachten…

    Paloran

    7 Feb 11 at 23:10

  11. Nette Übung zum Feierabend
    http://pastie.org/1538690

    Tobias Rohde

    7 Feb 11 at 23:23

  12. @Phil: Es dürfen keine Zahlen doppelt vorkommen (siehe Artikel). Denn sonst ist die Lösung nicht mehr eindeutig.

    Michael Kliewe

    7 Feb 11 at 23:40

  13. @chuckySTAR: Bei deiner Komprimierungsfunktion bekomme ich eine Notice (Undefined offset in line 7), das Ergebnis ist aber korrekt. Vielleicht möchtest du nochmal nachbessern? 😉

    Michael Kliewe

    7 Feb 11 at 23:49

  14. Noch ne Variante:
    http://pastie.org/1538852

    Schon interessant, wieviele Lösungen es für ein solches Problem gibt 😉

    Lena Fuchs

    8 Feb 11 at 00:09

  15. @Paloran: Deine Lösung funktioniert fast wie gewünscht, zwei Kleinigkeiten könntest du noch verbessern:
    – Das Ergebnis von makeArrayShort() sollte kontinuierlich indiziert sein, sprich mit Keys 0,1,2,3,4 etc., in deinem Ergebnis gibt es „Lücken“
    – Es wäre toll wenn es auch für Zahlen > 100 funktionieren würde, da ich gerade ein Testscript schreibe wo ich eure Funktionen mit 10.000 Zahlen laufen lasse

    Deine makeArrayLong() Funktion ist übrigens aktuell die schnellste von allen 6 eingereichten, obwohl sie die längste ist…

    Michael Kliewe

    8 Feb 11 at 00:09

  16. @Tobias + Lena: Bei eurem Code bekomme ich auch Notices (Undefined offset), die Ergebnisse sind aber korrekt. Tobias Zeile 23 und Lena Zeilen 8+10.

    @all: Heute (Dienstag) Abend veröffentliche ich das Testscript mit 10.000 Zahlen und die Liste aller Scripte, die bis dahin eingereicht wurden.

    Michael Kliewe

    8 Feb 11 at 00:49

  17. hab mir mal erlaubt Palorans Paste auch für Zahlen mit mehr stellen benutzbar zu machen.

    http://pastie.org/1538996

    Das mit der Indizierung würd ich nich mal als Problem ansehen. Davon abgesehen reicht ein einfaches $array = array_merge($array) um die indizierung neu generieren zu lassen.

    Flyingmana

    8 Feb 11 at 00:52

  18. hab das mal in eine klasse gepackt

    https://gist.github.com/815643

    Martin

    8 Feb 11 at 02:09

  19. Ist mit Sicherheit nicht die schnellste Lösung aber vielleicht gehört sie wenigstens zu den kürzesten (PHP 5.3 erforderlich)

    https://gist.github.com/815737

    Artem

    8 Feb 11 at 03:29

  20. Ich hab mal was ganz anderes gemacht

    http://pastie.org/1539436

    Oliver

    8 Feb 11 at 04:28

  21. Performancetechnisch dürfte das hier die bessere Wahl sein. Es ist zwar langsamer als Palorans Version, aber dafür sind die keys richtig, mehr Stellen sind kein Problem und array(13,81,80,79,78,79,77,76,19,40,41,42,43,44,45,48) funktioniert auch korrekt.

    http://pastie.org/1539702

    Oliver

    8 Feb 11 at 06:25

  22. Hier meine funktionale Lösung (in Haskell): http://pastie.org/1539837

    Daraus ließe sich mit Sicherheit eine objektorientierte Variante ableiten. Im komprimierten Array würden dann einzelne Zahlen als „Number“-Objekte und Sequenzen von Zahlen als „Sequence“-Objekte dargestellt. Die Komprimierung würde über eine Faltung (vgl. array_reduce) erfolgen. Zum Entpacken kann man jedem dieser Objekte eine toArray-Methode zuweisen, mit deren Hilfe das komprimierte Array in ein zweidimensionales Array umgewandelt wird, deren Elemente letztendlich konkateniert werden. Habe leider gerade keine Zeit, um den Code zu schreiben.

    Wäre mit Sicherheit nicht schneller, aber für einige Leute eleganter. :-)

    Andre

    8 Feb 11 at 07:56

  23. Hier die aktualisierte Variante: http://pastie.org/1539934

    Lena

    8 Feb 11 at 08:43

  24. So jetzt mal die aktuelle Variante

    https://gist.github.com/815643

    Martin Schäpker

    8 Feb 11 at 09:34

  25. @Oliver: Tolle Lösung, eine Funktion für beides, und mit regex, whao! Leider liefert deine erste Funktion nur Strings zurück, sprich array(„13″,“81-76“,“19″…
    Auch bei deiner zweiten Funktion erhalte ich einen Fehler, irgendwie scheinen manche aufeinanderfolgenden Zahlen (in diesem Fall waren es zwei) nicht erkannt zu werden. Bis auf diesen Fehler sind sie aber mit vorn an der Spitze.

    @Andre: Fein, eine andere Sprache! Leider kann ich sie nicht mit den anderen vergleichen oder ausprobieren, aber sie funktioniert sicherlich! 😉

    @Lena: Fehlerfrei!

    Michael Kliewe

    8 Feb 11 at 10:45

  26. Ja, ich sollte das nächste Mal die Aufgabe richtig lesen :-)

    Erstmal auf Performance getrimmt
    http://pastie.org/1540173

    Welche Werte waren denn falsch? Wenn Du sowas meinst wie 10, 40, 41, 11 dann wurden oben 40 und 41 nicht zusammengefasst, weil es eigentlich keinen Nutzen bringt. Das war schon Absicht. Hier hab ich es jetzt mal auf Zusammenfassen ohne Rücksicht auf Verluste gemacht. 😀

    Oliver

    8 Feb 11 at 11:01

  27. Korrektur. Da war noch ein Fehler, wenn die Reihe am Ende war:
    http://pastie.org/1540226

    Und hier ist die andere Version mit ints bei Zahlen und den Fehlern von oben entfernt:
    http://pastie.org/1540227

    Oliver

    8 Feb 11 at 11:24

  28. Wasrun

    8 Feb 11 at 12:19

  29. ausversehen gelöscht, hier die Version

    https://gist.github.com/05ba0f732555e4223613

    Martin Schäpker

    8 Feb 11 at 13:22

  30. Beim kürzen hab ich noch mal 20 % etwa raus kitzeln können. Ich denke, schneller krieg ich es nicht hin.

    http://pastie.org/1540508

    Oliver

    8 Feb 11 at 13:32

  31. Ohne mir jetzt mal alle durchzulesen würde mich interessieren, ob es eine Lösung besser o(n)=n gab. Würde mir nämlich jetzt spontan keine Idee kommen zu.

    Sebastian

    8 Feb 11 at 13:47

  32. Mein Versuch:

    http://pastie.org/private/88owgfxs2s93zatuwc93sa

    Ist etwas zu lang geraten, jetzt, wo ich mir das andere Zeug so anseh…

    DukeNightcrawler

    8 Feb 11 at 14:17

  33. 3,2 wird nicht zu „3-2“, dennoch:

    http://pastie.org/1541048

    max

    8 Feb 11 at 16:01

  34. @Sebastian: Es ist nicht möglich, ein n-elementiges Array in weniger als n Schritten zu iterieren. Wenn man davon ausgeht, dass man sich alle Elemente ansehen muss, kann es keine bessere Lösung als O(n) geben. Anders gefragt: Ist es möglich, ein n-elementiges Array mit weniger als n Schritten zu komprimieren?

    @Michael: Bei solch trivialen Aufgaben sehen die Lösungen sowieso sehr ähnlich aus – dem kann man entgehen, indem man eine andere Sprache wählt. 😉 Sie hat mir jedoch beim Aufwachen sehr geholfen, danke! 😉

    Andre

    8 Feb 11 at 16:33

  35. Hmm hatte error_reporting nicht auf E_ALL und dann ist mir der Fehler nicht aufgefallen ^^ Danke Michael
    Habe nur „- 1“ hinzugefügt und das wars 😉
    https://gist.github.com/815282

    chuckySTAR

    8 Feb 11 at 18:20

  36. Noch ein paar kleine Bugfixes (z. B. array fängt mit 1 an) und alles zusammen geschrieben
    http://pastie.org/1541543

    Oliver

    8 Feb 11 at 18:21

  37. Uwe

    8 Feb 11 at 18:45

  38. Stefan Gaudes

    9 Feb 11 at 08:25

  39. […] heute morgen wurden von 17 Lesern 18 Lösungen zur gestrigen Array-Umbau-Aufgabe eingereicht, und ich habe alle Funktionen durchlaufen lassen mit einem Testarray. Nun möchte ich […]

  40. […] Als Beispiel sei hier der kürzlich erschienene Blogbeitrag „Ein Array umbauen“ von Michael Kliewe zu nennen: http://www.phpgangsta.de/kleine-aufgabe-ein-array-umbauen […]

  41. Hier mal noch mein Beitrag:
    http://pastie.org/1562665

    sprain

    14 Feb 11 at 15:10

  42. Ist zwar schon vorbei, aber anbei meine Lösung:
    https://gist.github.com/841110

    Interessant, dass foreach mit value (zmnd. in php 5.3) schneller ist als for.

    DracoBlue

    23 Feb 11 at 21:23

  43. Stefan

    16 Mrz 11 at 00:15

Leave a Reply

You can add images to your comment by clicking here.