Suche Container-Klasse zur ERstellung eines Index

[0KommaNix]

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.

[Uwe Raabe]

So wie du es beschreibst ist der Index-Record genauso groß wie der Daten-Record. Wenn du den Index komplett im Speicher halten kannst, dann kannst du auch direkt die Daten in den Speicher laden und sortieren.

TDataRecord enthält faktisch zwei Double (8 Byte) (was das packed schon mal überflüssig macht). Somit hat ein TDataRecord eine Größe von 16 Byte, was bei 10.000.000 Datensätzen weniger als 160 MB ergibt - sollte also problemlos alles in den Speicher passen.

Speichert man die TDataRecords in einem TArray<TDataRecord> und baut sich einen IComparer<TDataRecord>, der auf den Time-Anteil prüft, kann man die TArray-Methoden Sort und BinarySearch verwenden um den exakten bzw. nächst-höheren Time-Eintrag zu finden.

Ach ja, da das Array einen zusammenhängenden Speicherbereich verwendet, kann es auch relativ schnell aus einer Datei gelesen und in eine geschrieben werden.

[0KommaNix]

Hallo Uwe,

Zitat von Uwe Raabe:

So wie du es beschreibst ist der Index-Record genauso groß wie der Daten-Record. Wenn du den Index komplett im Speicher halten kannst, dann kannst du auch direkt die Daten in den Speicher laden und sortieren.

Zwar haben die beiden Records die selbe Größe von 16Bit, aber im Index soll pro Kachel nur ein Record gespeichert werden. In meinen Beispiel ergibt sich also ein Größenverhältnis von 1 zu 4096.

Zitat von Uwe Raabe:

TDataRecord enthält faktisch zwei Double (8 Byte) (was das packed schon mal überflüssig macht).

Ja, ich weiss . Ich verwende packed für alles, was das Programm verlässt. Kostet nichts und soll darauf hinweisen, dass es Systemübergreifend kompatible sein soll.

Zitat von Uwe Raabe:

Somit hat ein TDataRecord eine Größe von 16 Byte, was bei 10.000.000 Datensätzen weniger als 160 MB ergibt - sollte also problemlos alles in den Speicher passen.

Da hast du recht. Ich überschätze bestimmt den Zeitbedarf. Allerdings ist der Dateigröße nach oben hin keine Grenze gesetzt.

Zitat von Uwe Raabe:

Speichert man die TDataRecords in einem TArray<TDataRecord> und baut sich einen IComparer<TDataRecord>, der auf den Time-Anteil prüft, kann man die TArray-Methoden Sort und BinarySearch verwenden um den exakten bzw. nächst-höheren Time-Eintrag zu finden.

Das will ich probieren! Leider kenne ich mich mit Generics nicht so gut aus. Kannst du mir bitte die Deklaration einer Implementationsklasse für IComparer<TDataRecord> zeigen?

[0KommaNix]

Zitat von 0KommaNix:

Leider kenne ich mich mit Generics nicht so gut aus. Kannst du mir bitte die Deklaration einer Implementationsklasse für IComparer<TDataRecord> zeigen?

Ok, beim ersten Schreck vor Generics, hab ich Angst bekommen. War dann doch leichter als gedacht. Schreibe nun ein Test für TArray<TDataRecord>.
Danke Uwe!

[Uwe Raabe]

Ich weiß zwar noch nicht wie der Index dann aufgebaut werden soll, aber hier mal ein paar Ansätze:

Delphi-Quellcode:

type
  TTimeRecord<T> = record
    Time: TDateTime;
    Value: T;
  end;

type
  TDataRecord = TTimeRecord<Double>;
  TDataArray = TArray<TDataRecord>;

  TIndexRecord = TTimeRecord<Int64>;
  TIndexArray = TArray<TIndexRecord>;

function MakeIndexRecordComparer: IComparer<TIndexRecord>;
begin
  Result := TComparer<TIndexRecord>.Construct(
    function(const Left, Right: TIndexRecord): Integer
    begin
      Result := CompareDateTime(Left.Time, Right.Time);
    end
    );
end;

var 
  FIndex: TIndexArray;

procedure SortIndex;
begin
  TArray.Sort<TIndexRecord>(FIndexArray, MakeIndexRecordComparer);
end;

function FindIndexValue(const ATime: TDateTime; out AIndex: Int64): Boolean;
var
  foundIndex: NativeInt;
begin
  var item: TIndexRecord;
  item.Time := ATime;
  Result := TArray.BinarySearch<TIndexRecord>(FIndexArray, item, foundIndex, MakeIndexRecordComparer);
  { falls bei nicht gefunden der kleinere Record verwendet werden soll }
//  if not Result then
//    Dec(foundIndex);
  if not Result and (foundIndex < 0) then begin
    AIndex := -1;
    Exit;
  end;
  AIndex := FIndexArray[foundIndex].Value;
end;

[0KommaNix]

Uwe, ich kann meine Begeisterung kaum Ausdruck verleihen - Ich freue mich wie Rumpelstilzchen!
SortIndex werde ich nicht brauchen, weil es ein Fehler wäre, wenn es einen Rücksprung bei der Aufnahmezeit gibt. Dann wäre eine Reparatur der Daten nötig. Das muss ich nur erkennen und den Anwender entscheiden lassen.

Zwischenzeitlich hatte ich einen einfachen Testfall geschrieben, bei dem ich für 1024*1024*1024 Daten-Records jede 4096 Records große Kachel einlese und in den Index stecke. Das ist zwar noch zu langsam, aber nach deiner Vorlage ist es sehr einfach einen kleineren Index aufzubauen und zwischen den Stützstellen einfach linear zu interpolieren, so wie oben angedacht. Das wird so schnell, dass ich mir ein Speichern und Laden sparen kann.

Vielen, vielen Dank!