MeinPHP: Typsicheres Set – Auflösung Teil 3

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.