Speicherverbrauch und Sortierung

[nuclear]

Hallo zusammen,
ich habe eine Komponente geschrieben, welche änlich zu der WIn32 komponente TreeView ist (jedoch keine grafische Ausgabe). Das Problem ist nur das ich die Daten in ein dynamisches Array schreibe. Dies ist ein Problem, da ich min 2.000.000 Datensätze damit verwalten wollte. Dies verbraucht viel zu viel Ram. Ein anderes Problem ist die Sortierung der Einträge. Da ich bei dem hinzufügen ja schon ein vorsortiertes Array habe dachte ich mir, das es mit InsertionSort relativ schnell gehen müsste. Dies ist bis zu 100.000 Objekten der Fall wird danach jedoch sehr langsam. Gibt es dafür einen schnelleren Algorytmus?
Danke im vorraus.
nuclear

[DeddyH]

Am RAM-Verbrauch kannst Du wahrscheinlich wenig machen, irgendwo müssen die Daten ja vorgehalten werden. Allerdings würde ich selbst wohl statt eines dynamischen Arrays eine (generische) TList/TObjectList verwenden. Die benutzen intern einen Quicksort und tauschen nicht die Daten an sich, sondern nur die Pointer darauf IIRC.

[nuclear]

Danke, ich hatte aus irgend einem Graund nicht an eine TList gedacht. Ist denn quicksort bei einer vorsortierten liste schneller als ein InsertionSort? Ich nutze zum Sortieren selber auch Pointer. Wie ist denn die Geschwindigkeit bei einer TList bei einem erstellen eines neuen Elements im vergleich zu einem dynamischen array? MAcht das wirklich einen großen Unterschied?

[DeddyH]

Es kommt darauf an. Wenn Du immer wieder SetLength() aufrufst, wird ein neues Array in der passenden Größe erstellt, das alte dort hineinkopiert und anschließend freigegeben. TList hingegen hält intern ein statisches Array[integer] of Pointer vor, und merkt sich darin nur die Zeiger auf die Daten, da muss nicht hin und her kopiert werden. Das hat außerdem den Vorteil, dass die Daten nicht im Block vorliegen müssen wie bei einem Array.

[r2c2]

Ich denke das eigentliche Problem ist ein architektonisches.

- Kein User will auf einmal 2 Mio Datensätze sehen (außer vielleicht in nem Scatterplot oder so)
- Keiner sagt, dass du also immer alle Daten im RAM halten musst.
- Um so große Datenmengen vorzuhalten und zu verarbeiten, wurden Datenbanken erfunden
- Um Baumstrukturen in ne DB zu kriegen hast du mehrere Möglichkeiten: FKs auf den Parent, ne n:m-Tabelle, Nested Sets und spezielle Graph-basierte NoSQL-Datenbaken.
- Alle genannten Ansätze haben ihre Vor- und Nachteile, die im konkreten Fall abzuwägen sind.
- Sortierung übernimmt die DB, Datenhaltung übernimmt die DB, Performanceoptimierung übernimtm die DB
- ...

mfg

Christian

[p80286]

Da liegst du nicht ganz falsch, aber falls Datenanalyse betrieben werden muß, mußt Du die Möglichkeit haben alle Daten zu sehen. etwas anderes ist es, nur einen Teil der Daten zur Anzeige zu bringen.

Gruß
K-H

[r2c2]

Zitat von p80286:

Da liegst du nicht ganz falsch, aber falls Datenanalyse betrieben werden muß, mußt Du die Möglichkeit haben alle Daten zu sehen. etwas anderes ist es, nur einen Teil der Daten zur Anzeige zu bringen.

So pauschal kann man das nicht sagen. Je nachdem, was du an Analyse so zu tun hast, kannst du die schon DB-Seitig vornehmen. Oder du lädst häppchenweise aus der DB und aggregierst die Analyseinfos. So hast du nie alles im RAM. Was hier die geschickteste Variante ist, hängt sehr stark von den jeweiligen Anforderungen und Rahmenbedigungen ab. Vielleicht ist es im konkreten Fall auch gut alles im Speicher zu halten. Auch solche Fälle gibts. Kommt halt drauf an...

mfg

Christian

[Delphi-Laie]

Zitat von nuclear:

Gibt es dafür einen schnelleren Algorytmus?

Zuhauf. Such' Dir einen aus meinem Sortierkino aus. Ansonsten gibt es genug Seiten im Internet, die sich mit dem Laufzeitverhalten (der sog Komplexität) der Sortieralgorithmen beschäftigen. Den erstbesten auszusuchen ("ich dachte", "müsste") ist eine bequeme und vorerst schnelle, tendeziell jedoch langsame und schlechte Lösung. Es gibt sogar Sortieralgorithmen, die darauf spezialisiert sind, zu schon sortierten Mengen weitere - noch unsortierte - Mengen hinzuzufügen. Einer davon ist das Proportion Extend Sort (auch in meinem Programm zu finden).

[nuclear]

Zitat von Delphi-Laie:

Den erstbesten auszusuchen ("ich dachte") ist ein bequeme und vorerst schnelle, tendeziell jedoch langsame und schlechte Lösung.

Das ist mir schon bewust nur ist InsertionSort bei vorsortierten Array auch ziemlich schnell (wenn ich ein weiteren Eintrag einsortiere, dann benötigt das bei 50.000 vorsortierten Elementen ca 1 ms). Der Algorythmus ist voll und ganz ausreichend. Außerdem prüft dieser Algorythmus ob das Sortieren nowendig ist weswegen ich denke das es schwer wird noch großartig schneller zu werden. Im übrigen habe ich auch in einem späteren Post geschrieben das dies nicht das Problem war, sondern das ständige kopieren des Datenarrays bei setlength am langsamsten war.

[Delphi-Laie]

Zitat von nuclear:

Das ist mir schon bewust nur ist InsertionSort bei vorsortierten Array auch ziemlich schnell (wenn ich ein weiteren Eintrag einsortiere, dann benötigt das bei 50.000 vorsortierten Elementen ca 1 ms).

Auf die Komplexität kommt es auch an - daß er "ziemlich schnell" sei, las sich oben aber bei den vielen Elementen anders.

Zitat von nuclear:

Der Algorythmus ist voll und ganz ausreichend.

Und warum monierst du ihn dann?

Zitat von nuclear:

Außerdem prüft dieser Algorythmus ob das Sortieren nowendig ist weswegen ich denke das es schwer wird noch großartig schneller zu werden.

Schon wieder: "Ich denke". Wenn, dann richtig "denken" oder nachdenken oder von den (richtigen) Gedanken anderer partizipieren. Bewährtes zu tradieren, ist ein Erfolgsgrund der Menschheit (der von Besserwissern aber zunehmend infragegestellt wird). Daß ein Sortieralgorithmus schneller bei vorsortierten Teilmengen ist, ist eine Eigenschaft, die Adaptivität heißt und bei vielen Sortieralgorithmen existiert.

Und noch etwas: Es gibt zwar z.B. einen Herzrhythmus, aber keinen Algorythmus!