MeinPHP: Typsicheres Set – Auflösung Teil 3

Lesetipps

1. MeinPHP: Typsicheres Set – Auflösung Teil 1
2. MeinPHP: Typsicheres Set – Auflösung Teil 2
3. MeinPHP – Eine Aufgabe, viele Lösungen

So einen Dreiteiler zu erstellen ist wirklich anstrengend. Normalerweise kann man ja schreiben, über was man an dem Tag Lust hat, hier aber leider nicht. Wäre aber doof, wenn ich nicht mit der Auflösung weiter machen würde, also los geht’s!

Im ersten Teil habe ich euch von den eingegangenen Lösung berichtet, im zweiten kurz skizziert, wie wir uns die “Musterlösung” vorstellen. Heute möchte ich die tatsächliche Implementierung zeigen. Da es etwas mehr Code geworden ist, als wir gedacht haben, werde ich unsere Klassen einfach in eine externe Datei packen. Ich werde auch nur auf die relevanten Stellen eingehen, da es sonst zu aufwendig werden würde.

Fangen wir also an. Ich hatte mich ja bei den anderen Lösungen “beschwert”, dass alle in O(n) ihre Elemente einsortieren. Es verdoppelt sich also der Aufwand, sobald die Anzahl der Elemente sich verdoppelt. Verwendet man einen normalen Array mit den natürlichen Zahlen als Index, dann hat man eben das Problem, dass sie nach der Reihenfolge, wie sie dem Set hinzugefügt wurden in dem Array liegen. Natürlich muss ich so das Array komplett durchgehen, bevor ich mein Element finde. Wenn aber jedem Element ein spezieller Hashwert zugeordnet wird, der die Position im Array definiert, so reduziert sich meine Suche auf ein Feld. Dieser Hashwert wird bei uns über spl_object_hash berechnet, da dieser eindeutig ist und für jedes Objekt bereits existiert. Nutzt man diesen jetzt als Schlüssel im Array, so verringert sich die Komplexität von O(n) auf O(1) . Das gilt natürlich nur, wenn PHP intern Hashmaps verwendet, um den Zugriff auf einen Array zu gewährleisten. Könnte man ganz einfach testen, in dem man schaut auf der Zugriff ein ein Array mit 10 Elementen genau so lange dauert, wie bei 10.000.

Dieses Problem haben wir also beseitigt. Den Rest haben wir sehr ähnlich den anderen Lösungen gemacht, die wir ja bereits auseinander genommen haben. Wir haben is_a verwendet, anstatt über get_class und “==” zu vergleichen, haben uns an die Java Collection angelehnt und das “Separation of Concerns” Paradigma befolgt, haben mit Interfaces hantiert und einen Dekorierer erstellt, damit wir über Delegation arbeiten können und nicht die Vererbungshierarchie verändern, haben unsere eigenen Exceptions verwendet. Ansonsten sind die Lösungen relativ ähnlich.

Wenn man sich unsere Lösung anschaut, dann mag sie anfänglich ein wenig komplexer wirken, als die anderen. Ich meine wir haben fast 220 Zeilen Code geschrieben. Dafür sind aber die einzelnen Klassen wiederverwendbar und nicht sonderlich komplex. Bei der Entwicklung einer typsicheren Liste z.B. wäre unsere Arbeit relativ schnell getan und er “Mehraufwand” hätte sich bereits gelohnt.

Bis jetzt ist die Lösung nur ein Prototyp und wir haben ihn, wenn ich ehrlich bin auch noch nie getestet. Es ging uns ja auch eher um den theoretischen Ansatz. Die lauffähige Version werde ich die nächsten Tage online stellen. Ich wollte es anfangen meine Klassenbibliothek mal öffentlich zugänglich zu machen, vielleicht hat ja der ein oder anderen einen nutzen daran.Ach ja, wenn ihr Fragen habt zu unserer Lösung, dann könnt ihr die jeder Zeit hier stellen. Ihr bekommt auch garantiert eine Antwort.

So ich hoffe euch hat diese kleine Herausforderung Spaß gemacht. Mir hat es das auf jeden Fall und aus diesem Grund wird es auch bald einen neuen Contest geben, in dem ihr zeigen könnt, was ihr drauf habt.  An dieser Stelle möchte ich mich auch noch einmal bei unset, Sebastian, Timo, Schwobeseggl, Schaelle und Andy G. bedanken. Ich hoffe ihr seid das nächste mal auch wieder dabei.

6 Kommentare »

• 
  

  Steffkes

  am 20. Januar 2009 um 19:52 Uhr

  Hi Nils, die Lösung selbst ist natürlich wohl die Ausführlichste von Allen – hätte mich aber auch gewundert wenn es anders gewesen wäre

  Was mich irgendwie irriert, seit dem ich die Methode zum ersten Mal gesehen habe .. ist die Verwendung von $elements und $indexHash – wozu verwendet ihr beide parallel? In meinen Augen liese sich das doch in Form von $this->elements[$hash] = $element; erledigen, oder überseh ich da irgendwas?

  Damit würdigen sich vielleicht auch gleich die “Code-Verrenkungen” in den remove-Methoden ablösen lassen?

  Gruss
  Steffkes

• 
  

  Nils Langner

  am 20. Januar 2009 um 20:06 Uhr

  Da muss ich jetzt auch mal drüber nachdenken Um ehrlich zu sein, weiß ich nicht mehr, warum. Genau die gleiche Frage hatte ich mir vor kurzem nämlich auch selbst gestellt. Ich schlafe einfach mal ne Nacht drüber.

  PS: Arbeitest du eigentlich mit Christine Fey zusammen?

• 
  

  Nils Langner

  am 20. Januar 2009 um 20:11 Uhr

  Was mir gerade einfällt: Was wir so gewinnen, ist Information über die Reihenfolge, wie die Elemente reingekommen sind. Sortiere ich direkt nach den Hashwerten, dann klappt das nicht. Auch können die Hashwerte eines Objektes in zwei Skripten anders sein. Das bedeutet, man hat keine eindeutig definierte Reihenfolge.

• 
  

  Steffkes

  am 20. Januar 2009 um 20:41 Uhr

  Ich fang erst mal mit dem PS an: Ja – sitzt gleich nebenan *g

  Okay die Reihenfolge ist ein Grund, in der Tat – is ja nicht so als würden mir aber damit die Fragen ausgehen Die Bedingung war jedes Objekt nur einmal, somit ist $this->indexHash[$hash][] = $position; doch aber eigentlich eine Dimension zuviel, denn mehrmalige Vorkommen des gleichen Hashs dürft’s ja eigentlich nicht geben.

  Oder hab ich da auch irgendwas Offensichtliches übersehen? :>

• 
  

  Nils Langner

  am 21. Januar 2009 um 07:32 Uhr

  Dann grüß sie mal ganz herzlich und hänge am besten ein “gell” hinter den Satz.

  Bei der Dimension zu viel übersiehst du, dass diese Funktionalität teil der allgemeinen Collection ist. Diese hat die Einschränkung nicht. Hier dürfen Elemente so oft wie möglich vorkommen.
  Also getreu nach dem Motto “Separation of concerns” kommt diese Limitierung erst beim Set zu Stande.

• 
  

  Timo Reitz

  am 9. Juli 2010 um 09:21 Uhr

  Wenn man die Klassen als Typen auffasst, müsste dann nicht gemäß dem Liskovschen Substitutionsprinzip Collection von Set erben und nicht umgekehrt?

  Nehmen wir mal beispielhaft folgende Methode, die eine Kollektion erwartet:
  public function foobar(iCollection $collection){
  $collection->add(100);
  $collection->add(100);}

  Übergebe ich an dieser Stelle Objekt der Klasse Collection, funktioniert es, übergebe ich ein Objekt der erbenden Klasse Set, so kommt es zu einer Ausnahme! Ich kann also nicht überall, wo ich vorher Kollektionen verwendet habe, nun Sets verwenden.

  Im hypothetischen umgekehrten Fall, wo Collection von Set erbt, passiert das nicht. Code, der vorher keine Ausnahme geworfen hat, wirft nun auch keine. Wer natürlich an gewissen Stellen Ausnahmen erwartet hat, erhält nun keine, aber das Erwarten von Ausnahmen ist m.E. ohnehin falsch, denn etwas, was man erwartet, kann wohl kaum eine Ausnahme sein.

RSS Feed für Kommentare zu diesem Artikel. TrackBack URL

Hinterlasse einen Kommentar