TStringList, Dynamisches Array oder Verknüpfte Liste in Delphi?

Question

Ich habe eine Wahl.

Ich habe eine Reihe von bereits bestellten Zeichenfolgen, die ich speichern und abrufen muss. Es sieht so aus, als ob ich wählen kann zwischen der Verwendung von:

1. A TStringList

2. Ein dynamisches Array von Zeichenketten, und

3. Eine verknüpfte Liste von Zeichenketten (einfach verknüpft)

   und Alan schlug in seinem Kommentar vor, dass ich auch die Auswahl ergänzen sollte:

4. TList<string>

Unter welchen Umständen ist jede dieser Möglichkeiten besser als die anderen?

Was eignet sich am besten für kleine Listen (unter 10 Einträge)?

Was eignet sich am besten für große Listen (über 1000 Einträge)?

Was eignet sich am besten für große Listen (über 1.000.000 Einträge)?

Was ist das Beste, um den Speicherverbrauch zu minimieren?

Was ist das Beste, um die Ladezeit zu minimieren und zusätzliche Elemente am Ende hinzuzufügen?

Was ist am besten geeignet, um die Zugriffszeit für den Zugriff auf die gesamte Liste vom Anfang bis zum Ende zu minimieren?

Welche Datenstruktur wäre auf dieser (oder einer anderen) Grundlage vorzuziehen?

Als Referenz verwende ich Delphi 2009.

---

Dimitry sagte in einem Kommentar:

Beschreiben Sie Ihre Aufgabe und Ihr Datenzugriffsmuster, dann ist es möglich, Ihnen eine genaue Antwort zu geben

Okay. Ich habe ein Genealogieprogramm mit vielen Daten.

Für jede Person habe ich eine Reihe von Ereignissen und Attributen. Ich speichere sie als kurze Textstrings, aber es gibt viele davon für jede Person, von 0 bis zu einigen hundert. Und ich habe Tausende von Personen. Ich brauche keinen zufälligen Zugriff auf sie. Ich brauche sie nur als eine Anzahl von Zeichenketten in einer bekannten Reihenfolge, die jeder Person zugeordnet sind. Dies ist mein Fall von Tausenden von "kleinen Listen". Das Laden dieser Listen nimmt Zeit in Anspruch und beansprucht Speicherplatz, und der Zugriff auf sie ist zeitaufwändig, wenn ich sie alle benötige (z. B. um den gesamten erstellten Bericht zu exportieren).

Dann habe ich noch ein paar größere Listen, z. B. alle Namen der Abschnitte meiner "virtuellen" Baumansicht, die Hunderttausende von Namen haben kann. Auch hier brauche ich nur eine Liste, auf die ich per Index zugreifen kann. Diese werden aus Gründen der Effizienz getrennt von der Baumansicht gespeichert, und die Baumansicht ruft sie nur bei Bedarf ab. Das Laden dauert eine Weile und ist für mein Programm sehr speicherintensiv. Aber ich muss mir keine Gedanken über die Zugriffszeit machen, da immer nur auf einige wenige Daten gleichzeitig zugegriffen wird.

Ich hoffe, das gibt Ihnen eine Vorstellung davon, was ich zu erreichen versuche.

p.s. Ich habe hier bei StackOverflow eine Menge Fragen zur Optimierung von Delphi gestellt. Mein Programm liest 25 MB große Dateien mit 100.000 Personen und erstellt Datenstrukturen, einen Bericht und eine Baumansicht für sie in 8 Sekunden, verbraucht dabei aber 175 MB RAM. Ich arbeite daran, das zu reduzieren, weil ich Dateien mit mehreren Millionen Personen in 32-Bit-Windows laden möchte.

---

Ich habe gerade einige ausgezeichnete Vorschläge zur Optimierung einer TList bei dieser StackOverflow-Frage gefunden: Gibt es eine schnellere TList-Implementierung?

Answer 1

Ausgehend von Ihrer Beschreibung bin ich mir nicht ganz sicher, ob es in Ihr Design passen könnte, aber eine Möglichkeit, die Speichernutzung zu verbessern, ohne einen großen Leistungsverlust zu erleiden, ist die Verwendung einer trie .

Vorteile gegenüber dem binären Suchbaum

Dies sind die wichtigsten Vorteile von Tries gegenüber binären Suchbäumen (BSTs):

• Das Nachschlagen von Schlüsseln geht schneller. Das Nachschlagen eines Schlüssels der Länge m dauert im schlimmsten Fall O(m) Zeit. Ein BST führt O(log(n)) Vergleiche von Schlüsseln durch, wobei n für die Anzahl der Elemente im Baum ist, weil die Nachschlagezeit von der Tiefe des des Baums abhängen, die logarithmisch in der Anzahl von Schlüsseln, wenn der Baum ausgeglichen ist. Im schlimmsten Fall benötigt daher ein BST O(m log n) Zeit. Außerdem, im schlimmsten Fall wird log(n) annähernd m. Auch die einfachen Operationen, die während des Nachschlagens, wie die Array Indizierung mittels eines Zeichens, sind schnell auf echten Maschinen.

• Versuche können weniger Platz beanspruchen, wenn sie eine große Anzahl von Kurzversuchen enthalten Zeichenfolgen enthalten, da die Schlüssel nicht explizit gespeichert werden und die Knoten zwischen Schlüsseln mit gemeinsamen Anfangs Teilsequenzen.

• Versucht, die Suche nach dem längsten Präfix zu erleichtern, um den Schlüssel zu finden zu finden, der das längste mögliche Präfix von Zeichen, die alle eindeutig sind.

Answer 2

Mögliche Alternative:

Ich habe kürzlich SynBigTable entdeckt ( http://blog.synopse.info/post/2010/03/16/Synopse-Big-Table ), die eine TSynBigTableString-Klasse für die Speicherung großer Datenmengen mit einem String-Index enthält.

Es handelt sich um eine sehr einfache, einschichtige Bigtable-Implementierung, die hauptsächlich Plattenspeicher verwendet, um bei der Speicherung von Hunderttausenden von Datensätzen viel weniger Speicher zu verbrauchen als erwartet.

So einfach wie:

aId := UTF8String(Format('%s.%s', [Name, Nachname]));

bigtable.Add(data, aId)

y

bigtable.Get(aId, data)

Einziger Haken: Die Indizes müssen eindeutig sein, und die Kosten für die Aktualisierung sind etwas hoch (erst löschen, dann neu einfügen).