![]() |
Speicherverbrauch und Sortierung
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 |
AW: Speicherverbrauch und Sortierung
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.
|
AW: Speicherverbrauch und Sortierung
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?
|
AW: Speicherverbrauch und Sortierung
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.
|
AW: Speicherverbrauch und Sortierung
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 |
AW: Speicherverbrauch und Sortierung
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 |
AW: Speicherverbrauch und Sortierung
Zitat:
mfg Christian |
AW: Speicherverbrauch und Sortierung
Es kommt auch drauf an, was das für Daten sind und wie groß.
Das Array of Object/Pointer ist selber NUR etwa 8 MB (bis zu 16 MB bei Größenänderung). Bei einem Array of Record sieht das dann etwas anders aus. |
AW: Speicherverbrauch und Sortierung
Die Sortierung sollte schneller sein wenn man eine Liste mit Pointern-Objekten hat und somit nur die Pointer in eine andere Reihenfolge bringt. Wenn man die Daten direkt im Array hat kann je nach Größe eines Array-Eintrages schon eine Menge Zeit beim hin und her kopieren verloren gehen.
|
AW: Speicherverbrauch und Sortierung
Das hatte ich anzudeuten versucht, da ich annahm oder noch annehme, dass das Array die tatsächlichen Daten enthält und keine Zeiger.
|
AW: Speicherverbrauch und Sortierung
Ok nur um das klarzustellen. Die Komponente besteht aus einer Unterkomponente, welche wiederrum ein array der Unterkomponente enthält, sodass ich theoretisch unendlich viele Ebenen haben kann. Da ich innerhalb einer sehr kurzen Zeit überprüfen muss ob ein Eintrag bereits existiert muss ich auch alle Dateien im Speicher halten. Ich habe bereits versucht die Daten zwischenzuspeichern. Dies benötigt jedoch fast 20x mehr Zeit. Da ich mehrere Einträge pro Sekunde abgleichen und ewentuell hinzufügen muss ist dies inakzeptabel. Der Ansatz eine TObjectList zu verwenden hat geholfen das hinzufügen von neuen Einträgen zu beschleunigen, ich denke jedoch nicht das es möglich ist den Speicherverbrauch über deine DB zu senken. Ich hatte nur gedacht das es vllt noch andere Möglichkeiten geben könnte.
Vielen Dank an alle Edit: Ich hatte bereits zwei Arrays( Daten und Pointer getrent). Jedoch hat das umkopieren durch setlength sehr viel Zeit in Anspruch genommen, sobald ich etliche 10.000 Elemente hatte. Das SOrtieren benötigte unter eine ms. |
AW: Speicherverbrauch und Sortierung
Zitat:
Und woher kommen sie denn? Da unsere Altvoderen es auch geschafft haben ohne Gigabytes an Hauptspeicher Datenverarbeitung zu betreiben, gibt es da vllt. einen Lösungsansatz? Gruß K-H |
AW: Speicherverbrauch und Sortierung
Jedes TSubObject hat die Möglichkeit weitere SubObjects zu besitzen welche in einer TObjectList verwaltet werden. Weietrhin enthält ein SubObject ein Array of String wo verschiedene Daten gespeichert werden, sowie eine THashedStringlist wo die Namen der jeweiligen SubObjecte drinne stehen um eine schnelle Suche zu ermöglichen, einen String für den Namen und einen Pointer auf das Parent. Alles in allem ist dann das TObject welches selber verschiedene TSubObjects enthält, ca 400 Mb groß bei gerade einmal 100.000 Einträgen. Dies würde einen SPeicherverbrauch von ca 7 Gb für alle Dateien bedeuten. Dies ist leider nicht möglich. Wenn ich jedoch verschiedene Teile auslagere verlangsamt sich die Suche um ein vielfachen.
Edit: Die Daten werden von einem anderen Programm generiert und gespeichert danach von einer weiteren Klasse bearbeitet und an die Klasse TTreeObject (sehr hoher Ram-Verbrauch) weitergegeben, welche sie verwaltet. |
AW: Speicherverbrauch und Sortierung
Zitat:
|
AW: Speicherverbrauch und Sortierung
Zitat:
|
AW: Speicherverbrauch und Sortierung
Wonach willst Du suchen? Ich denke, Du solltest deine Daten als Array Of Record einlesen und dann anhand der Suchmöglichkeiten mit diversen Hashmaps arbeiten.
Wenn Du Speicherprobleme bekommst, dann bedenke, das der Schlüssel, der ein Record in einer Dictionary ablegt, im Record selbst nicht gespeichert werden muss. Ach ja: Vergiss deine sortierte Liste. Das ist überflüssig, wenn Du mit Dictionaries arbeitest. |
AW: Speicherverbrauch und Sortierung
Zitat:
Zitat:
Zitat:
Und noch etwas: Es gibt zwar z.B. einen Herzrhythmus, aber keinen Algorythmus! |
AW: Speicherverbrauch und Sortierung
![]() |
AW: Speicherverbrauch und Sortierung
Zitat:
Bezüglich einer Hashtabelle: Da ist das Problem das ich das Konzept nicht richtig verstehe. Auch ist wie vorher gesagt die Methode für mich nun schnell genug. Man kann vielleicht jetzt noch 1-2ms einsparen, da aber nur ca 50 Abfragen pro sec ausgeführt werden wird das keine große Änderung mehr bewirken. Das wichtigste Problem ist wie vorher schon angesprochen der Arbeitspeicherverbrauch. Ansonsten ist nun alles in Ordnung. |
AW: Speicherverbrauch und Sortierung
Zitat:
Gruß K-H |
AW: Speicherverbrauch und Sortierung
Hallo,
- 7 Gb an Daten und 50 Abfragen pro Sekunde? - innerhalb einer sehr kurzen Zeit überprüfen müssen ob ein Eintrag bereits existiert. - Darf nix kosten? Firebird (embeddet)? LG, Daniel |
Alle Zeitangaben in WEZ +1. Es ist jetzt 00:17 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz