String-Indizierte Arrays

[Die Muhkuh]

Hi,

ich hab hier eine Unit für string-indizierte Arrays geschrieben. Vllt. kann es ja einer gebrauchen .

Die Unit ist im Anhang drinne. Einmal rar und einmal zip.

Verwendung sollte auch klar sein. (In der Hilfe ist nen kleines Beispiel).

Tipps und Optimierungen erwünscht.


@alcaeus und Robert,

ich weiß, dass einer von euch zwei sagen wird, dass ich alcaeus' Object-Templates benutzen soll, um die ganzen Typecast zu sparen. Da es sich hier nur um eine Liste handelt und deswegen keinen langen typecast-code habe, habe ich die Object-Templates nicht verwendet.

[edit=alcaeus]Schreibfehler im Titel auf Wunsch korrigiert. Mfg, alcaeus[/edit]

[alzaimar]

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.

[Robert_G]

Zitat von alzaimar:

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.

Ich musste schon an deine Dictionaries denken, als Spider den Beitrag reingesetzt hat.

[Die Muhkuh]

Hi alzaimar,

ich kenne mich mit so Zeugs nicht aus. Ich werde es aber versuchen zu implementieren.

[alzaimar]

Hi Spider,

Ich will nicht oberlehrerhaft wirken, aber was Du da fabriziert hast ist echt erste Sahne! Und das 'Zeugs', von dem ich geredet habe, ist nicht so schwer. Die binäre Suche ist ziemlich leicht zu verstehen. Hashlisten sind dann doch ein wenig komplizierter.

Sag Bescheid, dann gibts Hilfe!

[alcaeus]

Hallo Manu,

ich hab mir deine Unit mal angesehn, nicht schlecht um ehrlich zu sein.
Was ich vermisse (abgesehn davon dass du wirklich eine typisierte Objectlist verwenden sollst ), sind Enumeratoren, um unter Delphi 2005 das for-in-do-Konstrukt verwenden zu koennen. Auch in frueheren Delphi-Versionen bringen diese einen Vorteil: ich muss nicht mit Laufvariablen arbeiten und habe somit ganz bestimmt keine Index-Fehler, die ja (leider) immer wieder vorkommen, weil man mal ein "-1" vergisst oder so. Wenn du mein ObjectList-Template verwendest koenntest du die enums auch einfach "weiterreichen", und muesstest dich gar nicht mehr um die Implementierung kuemmern

Greetz
alcaeus

[nailor]

@alzaimar: wenn du eine liste (kein array) hast - wie sieht das dann mit der von dir angesprochenen binären suchen aus? man kann ja - im gegensatz zum array - bei 1000 elementen nicht einfach an position 500 springen, sondern muss sich erstmal bis dorthin "durchhangeln".

[dizzy]

Eine Liste ließe sich im Zweifelsfall noch zusätzlich über ein Pointerarray indizieren, so dass du sowohl listenartig als auch arraymäßig darauf zugreifen kannst. Bei Problemen in Bäumen geht das nicht mehr ohne Kenntnis über die Daten (bzw. garnicht mehr).

[alzaimar]

@nailor:
Binary search geht natürlich nur mit Arrays. Du meinst mit 'Listen' die 'linked lists', oder?

@dizzy:
Die Idee hatte ich auch mal, bin aber auf keinen grünen Zweig gekommen. Ich habe keine Vorteile ggü. den Arrays gesehen.

Hier mein Rezept für Listen.
Brauch ich nur einen Container, nehme ich eine TList oder eine TStringlist. Die reichen mir.
Benötige ich Zugriff über einen Schlüssel, wirds schon schwieriger:

• - Bei Listen muss man sich überlegen, was die zeitkritische Operation ist:
  - Muss ich schnell suchen, nehme ich Hashlisten.
  - Muss ich schnell einfügen/löschen auch.
  - Benötige ich einen schnellen Iterator übber die sortieren Elemente, sind Skiplists erste Wahl. Sortierte Listen gehen auch, zumal sie einfach zu implementieren sind.
  - Habe ich verdammt viele Daten, tuts nur der B-Baum (Bayer-Baum), oder gleich eine DB.