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.

[jfheins]

Zitat von Satty67:

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

Kurze Antwort: Nein.

Um einen Integerwert in einem unsortierten Array zu finden, musst man im Besten Fall 1, im Durchschnitt n/2 und Worst-case n Elemente überprüfen. Das macht dein Code bereits.

Lösungen hast du bereits genannt: Markieren, komprimieren oder das ganze vor den 100000 Suchen sortieren, dann geht das ruck, zuck

[Satty67]

Ok, klare Antwort, hatte ich auch schon befürchtet, aber die Hoffnung stirbt zuletzt.

Gut, dann werde ich einen zweiten Index pflegen, der ein sortierter Index auf die Werte des ersten Index ist. Das Prinzip kenne ich dann (mittlerer Eintrag -> rechts/links usw.)

PS: Markieren und Komprimieren passiert auch, aber auf einer höheren Ebene. Die Low-Level Ebene muss alles sofort innerhalb der Datei umsetzen und wird so nur selten eingesetzt, aber trotzdem soll es für den Fall auch nicht zu Kaffee-Pause führen.

[3_of_8]

Wenn du n Datensätze hast und die Hälfte davon suchen musst, hat das eine Zeitkomplexität von O(n²). Wenn du es zuerst sortierst und dann einfach die erste Hälfte abschneidest, kommst du auf O(n log n), was zwar immer noch eine Weile dauern wird, aber trotzdem schon eine deutliche Verbesserung darstellt - vor allem bei derart großen Datenmengen.

(Alternativ könnte man das ganze von vorn herein in einem Binärbaum, einem Heap oder einem B-Baum verwalten. B-Bäume wurden genau für so etwas entwickelt)

[Satty67]

Mir fällt gerade ein, da ich ja den größten Offset suche, wäre bei sortiertem Index of Index kein suchen mehr nötig, sondern dort wäre es der höchste Eintrag. So ein Index kann ich parallel pflegen und muss ihn nur neu aufbauen, wenn der Hauptindex neu aufgebaut wird.

Problem der Low-Level Routine ist, dass Sie nicht weis, das sie jetzt 100.000x aufgerufen wird (soll sie auch nicht wissen, sie ist unabhängig von äußeren Umständen). Deshalb kann auch nicht vor den 100.000 Aufrufen ein Baum etc. erstellt werden werden, es würde bei jedem Aufruf die Aktion gestartet.

Der Code der die Routine aufruft kann, nein sollte solche Strategien einsetzen. Aber für den Fall das es nicht gemacht wird, soll wenigstens diese Routine mir ihren wenigen Informationen optimal laufen.

[Reinhard Kern]

Hallo,

eine nicht ganz, aber fast perfekte Lösung: du löscht einfach nur den Record, markierst ihn als frei und verkettest ihn mit anderen freien Records soweit schon vorhanden. Beim Zufügen werden diese freien Records zuerst verwendet. Damit gibt es je nach Bedienung zwar mehr als 1, aber nicht beliebig viele freie Records. Mit einem Wartungslauf kannst du die ja immer noch entfernen (z.B. wenn mal jemand 50000 am Stück löscht), aber für den normalen Betrieb ist das nicht notwendig. Das Verfahren entspricht der Strategie zur Belegung von Directory-Einträgen und ist daher lange bewährt.

Gruss Reinhard

[Satty67]

Hallo Reinhard,

ja auch das ist eine gute Strategie... aber eben für eine Ebene höher. Dort verwende ich aber schon Strategien. Das ganze sieht grob so aus:

Anwendungscode -> class RecordTable -> class TableAccess

Im Anwendungscode kann ich machen was das beste und schnellste ist. Die Klasse RecordAccess ist da aber etwas eingeschränkt. Auch RecordTable hat noch die Bürde, das keine Datenspalten zur Verwaltung zugefügt werden dürfen.

Weil auf die Datei auch andere (nicht kontrollierbare) Programme zugreifen können, ist es manchmal nötig, das keine gelöschten Datenbereiche in der Datei zurückbleiben. Auch kann ich bei manchen Dateien keine weiteren Spalten zur Verwaltung zufügen. Deine Strategie wäre zumindest auf der Ebene RecordTable einführbar... nur wenn ich die Datei schließe müsste ich für die anderen Anwendungen aufräumen und verschiebe damit nur das Zeitproblem.

Das ganze gibt ein System, um auf File of Record zuzugreifen... das ganze so, dass die alten Programme, die weiterhin damit arbeiten, nicht negativ beeinflusst werden.

[alzaimar]

Zwei Möglichkeiten, das Suchverhalten zu verbessern:
a) Verwende eine andere Datenstruktur.
b) Verwende eine Hilfsstruktur, die die Suche beschleunigt.

Ich würde Dir Skiplisten oder Hashmaps empfehlen. Für Beides findest Du in der DP Code-Beispiele (Ich würde nicht darauf setzen, das eine Binärsuche das Non-Plus-Ultra ist).

Mir fällt ürigens kein Grund ein, bei einer sortierten Liste zu bleiben.

[Satty67]

Ich bin kurz vor Abschluß des Systems... genauer bin ich im Moment an Detail Verbesserungen dran, eben dort beschleunigen, wo es noch schlechter umgesetzt ist. Mögliche Fehler erkennen und abfangen, soweit das nicht schon im Vorfeld gesehen wurde.

Seinen ursprünglichen Zweck hat es schon erfüllt, aber warum Code wegwerfen, wenn man ein brauchbares Tools draus basteln kann. Ein umfangreiches neu codieren möchte ich aber trotzdem vermeiden. Es ist jetzt auch so, das es erst bei Datenmengen schlecht wird, wo man schon längst auf ein SQL-System umsteigen sollte. Die alten Programme halten nur Datenmengen bis ca. 20.000 Datensätze, dafür arbeitet es schon einwandfrei.

Denke in ein paar Tagen werden ich das komplette System hier vorstellen und mich Eurer Kritik stellen. Bis dahin versuche ich etwas aus den Vorschlägen zu machen, sofern ich das umgesetzt bekomme.

PS: Das ganze ist auch nur die Funktion Delete... da gibt es noch Cut (Datensatz durch aufrücken löschen, also korrektes ausschneiden). Was auch nötig ist, wenn das alte Programm weiterhin eine korrekte Reihenfolge innerhalb der Datei erwartet... da kommt erst richtig Freude auf

[himitsu]

löschts du die "Datensätze" nacheinander oder liegt 'ne Liste der zu löschenden Datensätzte vor, so daß man alles in einem Durchgang machen könnte?


praktisch das Array 2-mal parallel durchgehn
- einmal um die zu löschenden Datensätze zu suchen
- und zugleich nocheinmal wo die zu verschiebenden Datensätze gesucht werden

zu verschieben sind ja alle mit
Index >= (Dateigröße / Datensatzgröße - LöschendeDatensätze)


so könntest du die Suche (n/2)*großesArray
in 2*(n/2)*großesArray + n*(n/2)*kleinesArray ersetzen

das kleine Array = die Liste der zu löschenden Datensätze
(beim Durchgang des großen arrays wird ja nun nichtmehr je ein Datensatz gesucht, sondern gleich alle zusammen)



das könntest du dann höchstens nochmal optimieren, indem du deine aktuelle Löschmethode (jeden Datensatz einzaln suchen und löschen) mit dem hier Beschriebenem kombinierst

wenn AnzählZuLöschenderDatensätze > Datensatzanzahl/2 dann deine aktuelle Methodem, ansonsten mein Vorschlag