Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
02.04.2011, 13:23 Uhr
~scr
Gast

Hallo!

Ich habe ein Programm geschrieben in dem ich wiederholt die Häufigkeit von gewissen Histogram bins (von einem startbin bis zu einem endbin innerhalb des gesammten Histogram Wertebereichs) von verschiedenen histogrammen gezählt werden. Nachdem dabei wiederholt die selben Wertebereiche vorkommen dachte ich es wäre besser die schon berechneten Werte zu speichern um sie wiederverwenden zu können. Allerdings bin ich mir dabei nicht sicher welche Datenstruktur und welches vorgehen dabei am besten geeignet sind. Und leider weiss ich im voraus auch nicht welche Wertebereiche benötigt werden. Das ergibt sich erst während den laufenden Berechnungen.

Konkret will ich meine gezählten werte speichern nach: startbin, endbin, und zugehörigem histogramindex. Das wäre also eine 3D lookuptable.

Bisher sind meine Überlegungen in diese Richtung gegangen: Ich mir nicht sicher ob ich gleich am anfang eine lookup table mit allen theoretisch möglichen start und endbins erstellen sollte und dann die Werte die ich einmal benötigt habe dort eintrage (rest zb. auf -1 sätzen um zu wissen dass für diesen Wertebereich die Berechnung noch nicht durchgeführt wurde). Diese Option würde halt bedeuten dass ich bei einer Histogramgröße von 2000 bins gleich von Anfang an einen Speicher von "2000^2 x anzahl der histogramme x sizeof(double)" benötige. Dabei dabei kann die Anzahl der Histogramme durchaus sehr hoch sein (um die 30.000 histogramme).
Hier könnte ich ja zb einen vector (vector<vector<vector<double>>>

als Datenstruktur verwenden?!
Alternativ könnte ich nur jene Einträge erstellen die schon berechnet wurden. Allerdings wäre dann der vector als Datenstruktur ungeeignet weil die start und endbins ja nicht dem entsprechenden Eintrag im Vector zuzuordnen sind. Und ausserdem müsste ich dann meine Datenstruktur dynamisch vergrößern was ja auch einen gewissen Zeitaufwand bedeutet.

Daher nochmal kurz meine Fragen:
- Welche Datenstruktur würdet ihr für diese Situation verwenden
- Und wie würdet und ihr sie verwenden (also von Anfang an alle Einträge erstellen und bei Bedarf die Werte Eintragen, oder die Einträge überhaupt erst dann erstellen wenn sie benötigt werden).

Vielen Dankt für eine Antwort.
LG scr

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
02.04.2011, 22:24 Uhr
Hans
Library Walker
(Operator)

Hi,

ich hab sowas zwar noch nicht gemacht, aber so spontan würde ich sagen, dass das ein Fall für dynamische Datenstrukturen ist. Wobei der vector dabei wohl wirklich ungünstig ist, wenn er sehr gross wird. Aber eine Baumstruktur wie z.B ein binärer Baum wäre denkbar. Oder möglicherweise auch eine etwas umfangreichere Baumstruktur, wo jeder Datensatz mit einem Hashcode versehen wird, um ihn schneller wieder zu finden. (Das wird meines Wissens nach bei Compilern so gemacht, wenn die ihre Symboltabelle aufbauen.) Dieses Vorgehen würde bedeuten, dass Du die Lookuptable erstellst, während Du deine Histogramme vergleichst. Die Ergebnisse speicherst du dann einweder in einem neuen Knoten (bzw. Blatt) der Baumstruktur oder, wenn sich ein Ergebniss wiederholt, erhöst du einen Zähler innerhalb eines schon vorhandenen Eintrags. - Hoffe, das bringt Dich etwas weiter.

Hans
--
Man muss nicht alles wissen, aber man sollte wissen, wo es steht. Zum Beispiel hier: Nachdenkseiten oder Infoportal Globalisierung.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: