Kleine Aufgabe: Ein Array umbauen
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.
Auf die Schnelle: https://gist.github.com/02cb126265597135c8ac
Daniel
7 Feb 11 at 21:42
Sieht jetzt nicht so toll aus, aber sollte funktionieren 😉
https://gist.github.com/9020b83e6a13f51c24ed
Patrick
7 Feb 11 at 21:45
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
Hier mal meine uncompress-Methode:
http://pastie.org/1538370
smares
7 Feb 11 at 22:01
Meine super schnelle kleine Lösung (Ok, nicht gemessen ^^):
https://gist.github.com/815282
🙂
chuckySTAR
7 Feb 11 at 22:43
Mein Versuch 🙂
https://gist.github.com/815294
Phil
7 Feb 11 at 22:46
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
Hm, ein mal + 1 zu viel. Jetzt gehts auch mit dem neuen Array ^^
chuckySTAR
7 Feb 11 at 23:05
meine version http://pastie.org/1538632
frank
7 Feb 11 at 23:08
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
Nette Übung zum Feierabend
http://pastie.org/1538690
Tobias Rohde
7 Feb 11 at 23:23
@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
@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
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
@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
@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
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
hab das mal in eine klasse gepackt
https://gist.github.com/815643
Martin
8 Feb 11 at 02:09
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
Ich hab mal was ganz anderes gemacht
http://pastie.org/1539436
Oliver
8 Feb 11 at 04:28
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
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
Hier die aktualisierte Variante: http://pastie.org/1539934
Lena
8 Feb 11 at 08:43
So jetzt mal die aktuelle Variante
https://gist.github.com/815643
Martin Schäpker
8 Feb 11 at 09:34
@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
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
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
http://pastie.org/1540348
30 min Arbeit
Wasrun
8 Feb 11 at 12:19
ausversehen gelöscht, hier die Version
https://gist.github.com/05ba0f732555e4223613
Martin Schäpker
8 Feb 11 at 13:22
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
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
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
3,2 wird nicht zu „3-2“, dennoch:
http://pastie.org/1541048
max
8 Feb 11 at 16:01
@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
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
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
http://pastie.org/1541657
Uwe
8 Feb 11 at 18:45
http://pastie.org/1543912
Stefan Gaudes
9 Feb 11 at 08:25
[…] 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 […]
Ergebnisse der Array-Umbau-Aufgabe | PHP Gangsta - Der PHP Blog
9 Feb 11 at 10:25
[…] Als Beispiel sei hier der kürzlich erschienene Blogbeitrag „Ein Array umbauen“ von Michael Kliewe zu nennen: https://www.phpgangsta.de/kleine-aufgabe-ein-array-umbauen […]
Lasset die Spiele beginnen « think.ahead
11 Feb 11 at 09:47
Hier mal noch mein Beitrag:
http://pastie.org/1562665
sprain
14 Feb 11 at 15:10
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
http://nopaste.info/a8595018eb.html
Stefan
16 Mrz 11 at 00:15