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

Wenn Sie keine besonderen Bedürfnisse haben, ist ein TStringList ist schwer zu übertreffen, denn es bietet die TStrings Schnittstelle, die viele Komponenten direkt nutzen können. Mit TStringList.Sorted := True wird die binäre Suche verwendet, was bedeutet, dass die Suche sehr schnell sein wird. Sie erhalten auch Objektzuordnung kostenlos, jedes Element kann auch mit einem Zeiger verbunden werden, und Sie erhalten alle vorhandenen Methoden für Marshalling, Stream-Schnittstellen, Komma-Text, begrenzten Text, und so weiter.

Andererseits wäre für spezielle Zwecke, wenn Sie viele Einfügungen und Löschungen vornehmen müssen, etwas, das eher einer verknüpften Liste ähnelt, besser geeignet. Aber dann wird die Suche langsamer, und es ist in der Tat eine seltene Sammlung von Zeichenketten, die nie durchsucht werden muss. In solchen Situationen wird oft eine Art von Hash verwendet, bei dem ein Hash aus, sagen wir, den ersten 2 Bytes einer Zeichenkette erstellt wird (ein Array mit der Länge 65536 wird vorab zugewiesen, und die ersten 2 Bytes einer Zeichenkette werden direkt in einen Hash-Index innerhalb dieses Bereichs umgewandelt), und dann wird an dieser Hash-Position eine verknüpfte Liste gespeichert, wobei jeder Elementschlüssel aus den restlichen Bytes der Zeichenketten besteht (um Platz zu sparen - der Hash-Index enthält bereits die ersten beiden Bytes). Die anfängliche Hash-Suche ist dann O(1), und die nachfolgenden Einfügungen und Löschungen sind schnell wie eine verknüpfte Liste. Dies ist ein Kompromiss, der manipuliert werden kann, und die Hebel sollten klar sein.

Answer 2

1. Eine TStringList. Vorteile: hat eine erweiterte Funktionalität, die es erlaubt, dynamisch zu wachsen, zu sortieren, zu speichern, zu laden, zu suchen, etc. Nachteile: bei einer großen Anzahl von Zugriffen auf die Elemente durch den Index führt Strings[Index] zu einem spürbaren Leistungsverlust (einige Prozente) im Vergleich zum Zugriff auf ein Array, Speicher-Overhead für jede Elementzelle.

2. Ein dynamisches Array von Zeichenketten. Vorteile: kombiniert die Fähigkeit, dynamisch zu wachsen, wie ein TStrings, mit dem schnellsten Zugriff durch den Index, minimale Speichernutzung von anderen. Nachteile: eingeschränkte Standardfunktionalität der "Stringliste".

3. Eine verknüpfte Liste von Zeichenketten (einfach verknüpft). Vorteile: die lineare Geschwindigkeit beim Hinzufügen eines Elements zum Listenende. Nachteile: langsamster Zugriff über den Index und die Suche, eingeschränkte Standardfunktionalität der "String-Liste", Speicher-Overhead für den Zeiger auf das nächste Element, schneller Overhead für die Speicherzuweisung für jedes Element.

4. TList< string >. Wie oben.

5. TStringBuilder. Ich habe keine gute Idee, wie man TStringBuilder als Speicher für mehrere Strings verwenden.

Eigentlich gibt es viel mehr Ansätze:

• verknüpfte Liste von dynamischen Arrays
• Hash-Tabellen
• Datenbanken
• Binärbäume
• usw.

Der beste Ansatz hängt von der jeweiligen Aufgabe ab .

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

Jeder, vielleicht sogar ein statisches Array mit einer Variablen für die Gesamtzahl der Elemente.

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

Für große Listen werde ich mich entscheiden: - dynamisches Array, wenn ich viele Zugriffe über den Index oder die Suche nach einem bestimmten Element benötige - Hash-Tabelle, wenn ich nach einem Schlüssel suchen muss - verknüpfte Liste mit dynamischen Arrays, wenn ich viele Einträge anhängen muss und keinen Zugriff über den Index benötige

Was ist das Beste, um den Speicherverbrauch zu minimieren?

dynamisches Array wird weniger Speicherplatz benötigen. Aber die Frage ist nicht der Overhead, sondern die Frage, ab welcher Anzahl von Elementen dieser Overhead sinnvoll wird. Und wie man dann mit dieser Anzahl von Elementen richtig umgeht.

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

Ein dynamisches Array kann dynamisch wachsen, aber bei einer wirklich großen Anzahl von Elementen findet der Speichermanager möglicherweise keinen kontinuierlichen Speicherbereich. Eine verknüpfte Liste funktioniert so lange, bis mindestens eine Zelle im Speicher vorhanden ist, allerdings auf Kosten der Speicherzuweisung für jedes Element. Der gemischte Ansatz - verknüpfte Liste mit dynamischen Arrays - sollte funktionieren.

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

dynamisches Array.

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

Für welche Aufgabe?

Answer 3

Wenn es Ihr erklärtes Ziel ist, Ihr Programm so weit zu verbessern, dass es Genealogie-Dateien mit Millionen von Personen laden kann, dann wird die Entscheidung zwischen den vier Datenstrukturen in Ihrer Frage Sie nicht wirklich ans Ziel bringen.

Rechnen Sie nach - Sie laden gerade eine 25 MB große Datei mit etwa 100000 Personen darin, was dazu führt, dass Ihre Anwendung 175 MB Speicher verbraucht. Wenn Sie Dateien mit mehreren Millionen Personen laden möchten, können Sie davon ausgehen, dass Sie ohne drastische Änderungen an Ihrem Programm Ihren Speicherbedarf um das Mehrfache erhöhen müssen n * 10 auch. Es gibt keine Möglichkeit, dies in einem 32-Bit-Prozess zu tun und gleichzeitig alles im Speicher zu halten, so wie Sie es derzeit tun.

Sie haben grundsätzlich zwei Möglichkeiten:

1. Nicht alles auf einmal im Speicher zu halten, sondern eine Datenbank oder eine dateibasierte Lösung zu verwenden, aus der man Daten lädt, wenn man sie braucht. Ich erinnere mich, dass Sie bereits andere Fragen dazu hatten und sich wahrscheinlich dagegen entschieden haben, also lasse ich es dabei bewenden.

2. Behalten Sie alles im Speicher, aber auf möglichst platzsparende Weise. Solange es kein 64-Bit-Delphi gibt, sollte dies für ein paar Millionen Personen ausreichen, je nachdem, wie viele Daten es für jede Person geben wird. Eine Neukompilierung für 64 Bit wird auch diese Begrenzung aufheben.

Wenn Sie sich für die zweite Option entscheiden, müssen Sie den Speicherverbrauch sehr viel stärker minimieren:

• Verwenden Sie String-Praktikum . Jedes geladene Datenelement in Ihrem Programm, das dieselben Daten enthält, aber in verschiedenen Strings enthalten ist, ist im Grunde genommen verschwendeter Speicher. Da es sich bei Ihrem Programm um einen Betrachter und nicht um einen Editor handelt, können Sie sich wahrscheinlich damit begnügen, nur Zeichenketten zu Ihrem Pool von internierten Zeichenketten hinzuzufügen. Das Internieren von Strings mit Millionen von Strings ist immer noch schwierig, die "Optimierung des Speicherverbrauchs mit String-Pools" Blog-Beiträge im SmartInspect-Blog können Ihnen einige gute Ideen liefern. Diese Leute arbeiten regelmäßig mit riesigen Datendateien und mussten die gleichen Einschränkungen in Kauf nehmen, mit denen Sie konfrontiert sind.
  Dies sollte auch diese Antwort auf Ihre Frage zu verbinden - wenn Sie String-Interning verwenden, würden Sie nicht brauchen, um Listen von Strings in Ihren Datenstrukturen zu halten, sondern Listen von String-Pool-Indizes.
  Es kann auch von Vorteil sein, mehrere String-Pools zu verwenden, z. B. einen für Namen, aber einen anderen für Orte wie Städte oder Länder. Dies sollte das Einfügen in die Pools beschleunigen.

• Verwenden Sie die Zeichenkettenkodierung, die die kleinste speicherinterne Darstellung ergibt. Wenn Sie alles als nativen Windows-Unicode-String speichern, wird wahrscheinlich viel mehr Speicherplatz benötigt als beim Speichern von Strings in UTF-8, es sei denn, Sie haben regelmäßig mit Strings zu tun, die hauptsächlich Zeichen enthalten, die in der UTF-8-Kodierung drei oder mehr Bytes benötigen.
  Aufgrund der notwendigen Zeichensatzkonvertierung wird Ihr Programm mehr CPU-Zyklen für die Anzeige von Zeichenketten benötigen, aber bei dieser Datenmenge ist dies ein lohnender Kompromiss, da der Speicherzugriff der Engpass sein wird und eine geringere Datengröße dazu beiträgt, die Speicherbelastung zu verringern.

Answer 4

TStringList speichert ein Array von Zeigern auf (String, TObject) Datensätze.

TList speichert ein Array von Zeigern.

TStringBuilder kann keine Sammlung von Zeichenketten speichern. Er ähnelt dem StringBuilder von .NET und sollte nur zur Verkettung (vieler) Strings verwendet werden.

Die Größenanpassung dynamischer Arrays ist langsam, daher sollte sie nicht einmal als Option in Betracht gezogen werden.

Ich würde Delphi's generische TList<string> in all Ihren Szenarien. Es speichert ein Array von Strings (keine String-Zeiger). Der Zugriff sollte in allen Fällen schneller sein, da kein (Un-)Boxing stattfindet.

Möglicherweise können Sie eine etwas bessere Lösung mit verknüpften Listen finden oder implementieren, wenn Sie nur sequentiellen Zugriff wünschen. Siehe Delphi-Algorithmen und Datenstrukturen .

Delphi fördert seine TList y TList<> . Die interne Array-Implementierung ist hochgradig optimiert, und ich habe bei ihrer Verwendung noch nie Leistungs-/Speicherprobleme erlebt. Siehe Effizienz von TList und TStringList

Answer 5

Eine Frage: Wie erfolgt die Abfrage: Werden die Zeichenfolgen abgeglichen oder eine ID oder eine Position in der Liste abgefragt?

Am besten für kleine # Strings:

Was auch immer Ihr Programm leicht verständlich macht. Die Lesbarkeit des Programms ist sehr wichtig, und Sie sollten sie nur an wirklichen Brennpunkten in Ihrer Anwendung der Geschwindigkeit opfern.

Am besten für den Arbeitsspeicher (wenn dieser am meisten eingeschränkt ist) und die Ladezeiten:

Alle Zeichenketten in einem einzigen Speicherpuffer (oder einer speicherabgebildeten Datei) aufbewahren und nur Zeiger auf die Zeichenketten (oder Offsets) aufbewahren. Wann immer Sie eine Zeichenkette benötigen, können Sie diese mit zwei Zeigern ausschneiden und als Delphi-String zurückgeben. Auf diese Weise vermeiden Sie den Overhead der Stringstruktur selbst (refcount, length int, codepage int und die Speichermanagerstrukturen für jede Stringzuweisung).

Dies funktioniert nur, wenn die Zeichenfolgen statisch sind und sich nicht ändern.

TList, TList<>, array of string und die obige Lösung haben einen "Listen"-Overhead von einem Zeiger pro String. Eine verkettete Liste hat einen Overhead von mindestens 2 Zeigern (einfach verkettete Liste) oder 3 Zeigern (doppelt verkettete Liste). Die Lösung mit der verketteten Liste hat keinen schnellen Zufallszugriff, ermöglicht aber eine Größenänderung von O(1), während die anderen Optionen O(lgN) (unter Verwendung eines Faktors für die Größenänderung) oder O(N) unter Verwendung einer festen Größenänderung haben.

Was ich tun würde:

Bei weniger als 1000 Einträgen und wenn die Leistung nicht so wichtig ist: Verwenden Sie TStringList oder ein dyn-Array, was für Sie am einfachsten ist. else if static: Verwenden Sie den obigen Trick. Dies führt zu O(lgN) Abfragezeit, geringstem Speicherverbrauch und sehr schnellen Ladezeiten (einfach einlesen oder eine Memory-Mapped-Datei verwenden)

Alle in Ihrer Frage erwähnten Strukturen versagen bei großen Datenmengen (1M+ Strings), die im Code dynamisch geändert werden müssen. Zu diesem Zeitpunkt würde ich einen ausgeglichenen Binärbaum oder eine Hashtabelle verwenden, je nach Art der Abfragen, die ich machen muss.