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 2 von 3     12 3   
nuclear

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

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 14:34
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.

Geändert von nuclear (12. Okt 2012 um 14:38 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von p80286
p80286

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

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 15:04
Kommt halt drauf an...
In diesem Sinne, um welche Daten handelt es sich denn?
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
Programme gehorchen nicht Deinen Absichten sondern Deinen Anweisungen
R.E.D retired error detector
  Mit Zitat antworten Zitat
nuclear

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

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 16:00
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.

Geändert von nuclear (12. Okt 2012 um 16:08 Uhr)
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#14

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 16:14
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).

Geändert von Delphi-Laie (12. Okt 2012 um 16:23 Uhr)
  Mit Zitat antworten Zitat
nuclear

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

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 16:24
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.
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#16

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 16:27
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.
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#17

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 16:30
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.

Der Algorythmus ist voll und ganz ausreichend.
Und warum monierst du ihn dann?

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!

Geändert von Delphi-Laie (12. Okt 2012 um 16:33 Uhr)
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#18

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 16:40
Hier ist ein Vergleich der verschiedenen Suchverfahren. Meine Erfahrung ist die, das das Einfügen in eine Dictionary am schnellsten ist (mit Ausnahme des reinen 'Add' in einer unsortierten Liste natürlich). Da das Suchen auch am schnellsten ist, vor allen Dingen bei sehr vielen Einträgen, würde ich wirklich dieses kindische binary Sort vergessen.
  Mit Zitat antworten Zitat
nuclear

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

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 17:25
Der Algorythmus ist voll und ganz ausreichend.
Und warum monierst du ihn dann?
Weil ich zuerst falsch lag und die Zeit inklusive dem kopieren der Array gemessen hatte, was bei etlichen tausend elementen schon relativ lange dauert. Außerdem kann man lesen das ich inzwischen eine TObjectList verwende und somit diese Diskussion vollkommen unnötig ist. Die Geschwindigkeit der jetzt verwendeten Methode ist auch vollkommen ausreichend, da die Eingaben deutlich langsamer kommen.
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.
  Mit Zitat antworten Zitat
Benutzerbild von p80286
p80286

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

AW: Speicherverbrauch und Sortierung

  Alt 12. Okt 2012, 17:41
ich denke jedoch nicht das es möglich ist den Speicherverbrauch über deine DB zu senken.
Ich denke da eher das Gegenteil, da ich aber versuche große Datenmengen durch Strukturierung ihrerselbst in den Griff zu bekommen, (vulgo Datenbank) ist mein Gedanke wohl eher als Vorurteil zu sehen.

Gruß
K-H
Programme gehorchen nicht Deinen Absichten sondern Deinen Anweisungen
R.E.D retired error detector
  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 16:42 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