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 März 11 at 00:15