(Moderator)
Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
Delphi 2007 Enterprise
|
Re: String-Indexierte Arrays
21. Jun 2005, 19:50
Nicht schlecht.
Aber, ich glaube mit einer TStringlist geht das genauso gut. Es gibt doch die Property 'Value'. Der kann man zwar zunächst nur Strings zuweisen, aber das lässt sich sehr leicht ändern.
Wenn Du aber etwas Besseres als die TStringlist implementieren möchtest, dann verbessere die Suchfunktion, die dir den entsprechenden Eintrag zu einem 'Schlüssel' liefert. Du verwendest eine Iteration. Die benötigt im Mittel n/2 Schritte, bis sie die den Eintrag findet.
Verdoppelst Du die Liste, verdoppelt sich auch die Zugriffszeit. Das ist schon sehr ordentlich, aber es geht noch schneller:
Versuche zunächst, Deine Liste immer sortiert zu halten. Dann kannst Du mit dem 'binary search' viel Schneller suchen. Das geht so:
Die Liste ist ja sortiert. Also nehmen wir uns das Element in der Mitte. Ist dieses Element größer als der Suchtext, muss er sich links von der mitte befinden (die Liste ist ja sortiert!). Wenn es kleiner ist, dann suchen wir in der rechten Hälfte weiter. Und wenn es gleich ist, na ja.
Egal, wir haben wieder eine Teilliste. Da machen wir genau das Gleiche. Mittleres Element nehmen, vergleichen und entscheiden, ob oben oder unten weiter zu suchen ist.
Das geht so schnell, das bei einer Verdoppelung der Listengröße gerade mal ein einziger neuer Suchschritt dazukommt. Bei 1000 Elementen sucht man maximal 10x, Bei 2.000.000.000 maximal 32 mal. Das ist schon sauschnell. Nur das Einfügen ist etwas aufwändig, weil wir ja das Element irgendwo in der Liste einfügen müssen: Dazu müssen wir die Liste ab der Stelle nach rechts verschieben, um Platz zu machen. Ähnliches gilt für das Löschen.
Wenn Du wirklich fit bist, dann suche mal nach Hashlisten. Die sind nicht soo schwer zu implementieren, aber ein bischen aufwändiger ist es schon. Dann hast Du aber eigentlich eine optimale Performance.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
|