Suchaufwand

[Christoph Zurnieden]

Hi,

Wie durchsuche ich am schnellsten?

Solltest Du nicht erstmal etwas funktionierendes haben, bevor Du optimierst? Wenn es dann überhaupt noch nötig ist?

Vielleicht.

Das war ja eigentlich eine rhetorische Frage ;-)

Problem ist eben, dass in den meisten Fällen, "E" zurückgegeben werden soll,

Ist nicht erstmal das Problem, das Du ein Skript benötigst, das die Funktion erfüllt? Oder hast Du das schon?

d.h. es wird keine Übereinstimmung geben. Es sollten also möglichst wenige Vergleiche gemacht werden, d.h. bereits ein erster Vergleich sollte wenn möglich entscheiden ob weitere Vergleiche überhaupt nötig sind.

Du kannst nichts optimieren, das nicht existiert. Obwohl manch einer sagen würde, das aus dem selbem Grund eine Optimierung nicht nötig ist, denn etwas nicht existierendes ist schon optimal, da es genau Null Schritte benötigt.

Aber Scherz beiseite: im Vornherein kannst Du auch optimieren und zwar durch Sortieren und Entfernen der Redundanzen.
Nach einigen der anderen Posts bin ich mir nicht mehr ganz so sicher, ob ich Dein Problem korrekt verstanden habe. Statt lästig zu werden und nachzufragen hier einfach mal noch ein Versuch:
Sortierung der umgedrehten Strings und Suche nach dem "längstem gemeinsamem Substring von Anfang an".

"gro.elpmaxe"
"moc.elpmaxe"
"moc.elpmaxe.liam"
"moc.elpmaxe.liam.rennacs"

"Längster gemeinsamem Substring von Anfang an" ist bei dem Beispiel oben "moc.elpmaxe".

Die Suche nach dem vollständigem String durch binäre Suche ist in O(log(n)) durchzuführen.
Die Suche nach dem "längstem gemeinsamem Substring von Anfang an" ist Average Case O(log(n)). (Aufgrund der Sortierung ist Best Case O(1) wenn schon der zweite Eintrag im erstem Buchstaben unterschiedlich ist. Wenn man in meinem Beispiel die beiden ersten Einträge gesondert nimmt ist das so ein Fall. Im schlimmsten Fall muß die ganze Liste abgeklappert werden. Nein, das stimmt nicht ganz, oder? Die ganze Liste muß ja dank der Sortierung und der Struktur der Domainnamen nie vollständig abgeklappert werden?)
Dazu kommen noch die einzelnen Stringvergleiche, die ohne Optimierung in O(n) ablaufen. (aber selbst mit kaum besser werden)

Insgesamt sollte Dein Algorithmus also flott ablaufen können, ich würde mir da keine großen Sorgen machen.

so short

Christoph Zurnieden