Suchen in unsortiertem Array of Integer beschleunigen.

[Satty67]

Folgende Situation:

Ich hab' ein Index : Array of Integer, das die Offset-Werte aus einer File of Record hält. Zum Löschen eines Record wird der zu löschende Record mit Daten aus letzten Record überschrieben und die Datei um ein Record gekürzt. (Ja, Record markieren und später Komprimieren, aber im speziellen Fall ist diese Lösung nicht möglich)

Wenn das passiert, muss natürlich auch der der Index synchronisiert werden. Dazu muss ich den Eintrag mit dem größten Offset suchen und an die Stelle des gelöschten setzen. (Index dann auch kürzen)

Solange der Index unsortiert ist, alles kein Problem (denn dann sind die Offsets sortiert). Wenn er nach Record-Werten sortiert ist (Offsets unsortiert), muss ich den Eintrag mit dem größten Offset suchen. Dafür wird der größte Offset anhand Record-Size und File-Size berechnet (LastOffset) und dann gesucht...

Delphi-Quellcode:

for i := Low(Index) to High(Index)-1 do
  if Index[i] = LastOffset then begin
    Result := i;
    Break;
  end;

Das dauert für einen Fall nicht lange, aber manchmal muss die Hälfte der sortierten Datei abgeschnitten werden (über 100.000 Datensätze), also 100.000x diese Suchroutine. Das macht den größten Teil der Laufzeit der Truncate-Routine aus (> 65%)

Erster Versuch das zu verbessern:

- Letzten größten Index merken und vorm Suchen prüfen. Allerdings war das nichts, genau der fällt ja immer aus der Liste.

Aktuelle Überlegung (aber noch nicht umgesetzt):

- Index auf Index und den sortieren. Dann wäre ein Eintrag sehr schnell gefunden.

bekomme aber jetzt schon einen Knoten im Gehirn und wollte Zeiger auf Zeiger auf Zeiger verhindern.

Gibt es einen Ansatz, eine Suche in unsortierter Liste wie im Code-Beispiel zu beschleunigen?

Sollte einfacher als Index auf Index sein, da ich sonst eher die Lösung umsetze.