Indexstruktur mit Gleitkommazahlen

Hallo zusammen

Ich muss einen statischen Index aufbauen, der folgende Daten enthält:

double timeStamp, short matchedNode, int indexTree

Dabei geht es um eine Baumstruktur welche dargestellt werden soll. Der Zeitstempel ist der eigentliche Index, die beiden nachfolgenden Felder repräsentieren die Baumstruktur zum jeweiligen Index-Zeitpunkt.

Nun soll von außen auf die Baumstruktur zugegriffen werden, eben anhand des Zeitstempels. Der Zeitstempel unterscheidet sich jeweils um 400 Millisekunden vom vorherigen Zeitstempel. Es werden dabei etwa maximal 45.000 Einträge im Index vorhanden sein. Bei einer Größe eines Eintrages von 14Byte werden ca. 630K an Speicher benötigt, also vernachlässigbar. Und wie geschrieben, dieser wird statisch aufgebaut und ist dann nicht mehr änderbar.

Habt ihr mir Tipps, wie ich das umsetzen könnte? Auch im Bezug auf Zugriff (Suche?), da es mit Gleitkommazahlen nicht gerade leicht sein wird.

Würde mich über Hilfestellung oder auch nur einem Lösungsansatz freuen!

Beste Grüße
HamsterBacke

Wieso Baumstruktur? Einfach Array/Vector und dann binäre Suche.

Dravere

Ich frage mich allerdings auch, wieso ein double Wert für einen Timestamp? Einfach den Timestamp als Millisekunden speichern oder vielleicht als Zehntelsekunden, da es ja nicht kleinere Unterschiede als 0.4 Sekunden geben wird.

Grüssli

Mit Baumstruktur meinte ich eigentlich die Daten, auf die der Index verweist.

Zurück zum Problem: also erstelle ich ein Struct-Array und führe eine binäre Suche über den Zeitstempel durch?

struct xyz
{
   double timeStamp;
   short matchedNode;
   int indexTree;
};

xyz index[45000];

Muss ich noch etwas wegen den Fließkommazahlen bei der binären Suche beachten?

Danke für die Antwort!
Gruß HamsterBacke

knivil

Mach es einfach und komme wieder bei Problemen!

Dravere, du meinst also den Timestamp anstatt bspw. 12.4577 als Ganzzahl 1245 zu speichern? Ja das wäre natürlich eine Möglichkeit, und leichter zu verarbeiten. Muss mal überlegen ob ich den exakten Timestamp noch mal benötige...

Beste Grüße
HamsterBacke

HamsterBacke schrieb:

Muss ich noch etwas wegen den Fließkommazahlen bei der binären Suche beachten?

Die Fließkommaspezifischen Probleme (Inf, NaN, etc.), Timestamp muss streng monoton sein und du musst überlegen was du machst wenn du einen Timestamp suchst den des nicht gibt (also nimmt man den nächstkleineren bzw. nächstgrößeren) (dadruch fallen die Standard-Implementierungen iirc raus).