Hallo,
meine Frage in Kurzform:
Kann mir jemand eine Container-Klasse empfehlen, die gut als Nachschlage-Index geeignet ist?
Sie sollte dazu auf folgende Beschreibung passen:
1. Die Einträge sind sortiert nach Key: TDateTime. Value ist int64.
2. Schnelle Suche nicht nach dem Key: TDateTime, sondern nach Item[i].Time <= Key < Item[i+1].Time.
Gesucht wird also nicht nur der Eintrag mit dem exakten Schlüsselwert, sondern der Vorgänger- und Nachfolger-Eintrag.
Leider kenne ich keine Container-Klasse die das von sich aus unterstützt.
3. Schnelles Laden und Schreiben aus/von einer Datei.
4. Gut wäre die Verwendung von "Memory-Mapped Files", weil dann das Laden und Speichern praktisch entfällt.
Im Gegenzug wäre das Sortieren, bzw. Einfügen, dann aber sicher sehr schwierig. Deshalb dies nur optional, als alternative Variante.
Die lange Fassung meiner Frage, damit der Verwendungszweck gut beschrieben wird:
Der Zugriff auf eine binären Daten-Datei soll beschleunigt werden, in dem ein Index (bzw. eine Index-Datei) aufgebaut wird.
Die Daten-Datei enthält Zeitreihen Daten, die durch folgenden Code-Schnipsel beschrieben wird:
Delphi-Quellcode:
const
REC_PER_TILE = 4096;
type
TDataRecord = packed record
Time: TDateTime;
Value: double;
end;
TDataRecordArray = array[0..REC_PER_TILE-1] of TDataRecord; // Eine Kachel
PDataRecordArray = PDataRecordArray; // Zeiger auf Kachel
TIndexRecord = packed record
Time: TDateTime; // Der Schlüssel im Index-Container
RecNr: int64; // Der Verweis in die Daten-Datei
end;
Die Datei kann beliebig groß werden (typisch sind 10.000.000 TDataRecord Einträge). Bei einer fehlerfrei geschriebenen Daten-Datei sind die Einträge nach Time aufsteigend sortiert (recs[i].Time<=recs[i+1].Time).
Der Lesezugriff erfolgt Kachelweise über ein "Memory-Mapped File". Hier der Pseudocode ohne Index:
Delphi-Quellcode:
function ReadSeek(ATime: TDataTime; out RecNr: int64): boolean;
var
Left, Right,dcnt: int64;
MinTime, MaxTime, dt: TDateTime;
TileNr: int64;
recs: PDataRecordArray;
cnt: integer;
begin
// 1. Suche initialisieren und auf gültigen Bereich beschränken
Left := 0;
Right:= RecordCount-1;
MinTime:= StartTime;
MaxTime:= EndTime;
if (ATime ... ) then
...
// binäre Suche bis gefunden
found := False;
repeat
// 2. Schätze die Position in der Datei:
dcnt:= (Right-Left);
found := dcnt<=0;
if found then
break;
dt := (MaxTime-MinTime)/ dcnt;
RecNr := Left+(ATime-MinTime) / dt;
// 3. zugehörige Kachel einlesen:
TileNr := RecNr div REC_PER_TILE;
Read(TileNr, recs, cnt);
// 4. Im gelesenen Buffer recs den Vorgänger zu ATime suchen. Es gibt 3 mögliche Fälle:
// 4.1 ATime gefunden. Sonderfall, dass i+1 in der nächsten Kachel liegt, hier nicht berücksichtigt
found := (recs[i].Time<=ATime) and (recs[i+1].Time>=ATime);
...
// 4.2 recs[0].Time>ATime
Right := TileNr * REC_PER_TILE;
MaxTime := recs[0].Time;
...
// 4.3 recs[cnt-1].Time<ATime
Left := (TileNr+1) * REC_PER_TILE;
MinTime := recs[cnt-1].Time;
...
until(found);
end;
Mit Index würde ich unter 1. zuerst Prüfen, ob der Suchbereich sich durch einen Vorgänger und/oder Nachfolger einschränken lässt.
Unter 3. könnte man dann, nach jedem Read Aufruf, recs[0] in den Container eintragen. So könnte man den Index nebenbei, bei der
Benutzung, weiter aufbauen.
Ich überlege, ob man sich das Laden und Speichern sogar sparen könnte, wenn man nach den Öffnen der Daten-Datei jede n-te Kachel liest und deren recs[0] in den Index einträgt.
Bei kleinen Dateien ist n=1, also jede Kachel. Bei größeren Dateien wird solange n erhöht, bis die Anzahl der Lesevorgänge einen Grenzwert unterschreitet.
Über Ideen und Anregungen würde ich mich freuen.