AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Speicherverbrauch und Sortierung

Ein Thema von nuclear · begonnen am 12. Okt 2012 · letzter Beitrag vom 12. Okt 2012
Antwort Antwort
Seite 1 von 3  1 23   
nuclear

Registriert seit: 15. Dez 2010
13 Beiträge
 
#1

Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 11:31
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
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.624 Beiträge
 
Delphi 12 Athens
 
#2

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 11:37
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.
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen
  Mit Zitat antworten Zitat
nuclear

Registriert seit: 15. Dez 2010
13 Beiträge
 
#3

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 11:49
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?
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.624 Beiträge
 
Delphi 12 Athens
 
#4

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 11:57
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.
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen
  Mit Zitat antworten Zitat
r2c2

Registriert seit: 9. Mai 2005
Ort: Nordbaden
925 Beiträge
 
#5

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 12:05
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
Kaum macht man's richtig, schon klappts!
  Mit Zitat antworten Zitat
Benutzerbild von p80286
p80286

Registriert seit: 28. Apr 2008
Ort: Stolberg (Rhl)
6.659 Beiträge
 
FreePascal / Lazarus
 
#6

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 12:14
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
Programme gehorchen nicht Deinen Absichten sondern Deinen Anweisungen
R.E.D retired error detector
  Mit Zitat antworten Zitat
r2c2

Registriert seit: 9. Mai 2005
Ort: Nordbaden
925 Beiträge
 
#7

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 12:51
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
Kaum macht man's richtig, schon klappts!
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
44.136 Beiträge
 
Delphi 12 Athens
 
#8

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 13:16
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.
Neuste Erkenntnis:
Seit Pos einen dritten Parameter hat,
wird PosEx im Delphi viel seltener praktiziert.
  Mit Zitat antworten Zitat
Benutzerbild von SirThornberry
SirThornberry
(Moderator)

Registriert seit: 23. Sep 2003
Ort: Bockwen
12.235 Beiträge
 
Delphi 2006 Professional
 
#9

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 13:34
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.
Jens
Mit Source ist es wie mit Kunst - Hauptsache der Künstler versteht's
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.624 Beiträge
 
Delphi 12 Athens
 
#10

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 13:39
Das hatte ich anzudeuten versucht, da ich annahm oder noch annehme, dass das Array die tatsächlichen Daten enthält und keine Zeiger.
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 17:03 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz