AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Sprachen und Entwicklungsumgebungen Object-Pascal / Delphi-Language Delphi Suchen in unsortiertem Array of Integer beschleunigen.

Suchen in unsortiertem Array of Integer beschleunigen.

Ein Thema von Satty67 · begonnen am 6. Mai 2009 · letzter Beitrag vom 12. Mai 2009
Antwort Antwort
Seite 1 von 2  1 2   
Satty67

Registriert seit: 24. Feb 2007
Ort: Baden
1.566 Beiträge
 
Delphi 2007 Professional
 
#1

Suchen in unsortiertem Array of Integer beschleunigen.

  Alt 6. Mai 2009, 23:31
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.
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#2

Re: Suchen in unsortiertem Array of Integer beschleunigen.

  Alt 6. Mai 2009, 23:44
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
  Mit Zitat antworten Zitat
Satty67

Registriert seit: 24. Feb 2007
Ort: Baden
1.566 Beiträge
 
Delphi 2007 Professional
 
#3

Re: Suchen in unsortiertem Array of Integer beschleunigen.

  Alt 6. Mai 2009, 23:49
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.
  Mit Zitat antworten Zitat
Benutzerbild von 3_of_8
3_of_8

Registriert seit: 22. Mär 2005
Ort: Dingolfing
4.129 Beiträge
 
Turbo Delphi für Win32
 
#4

Re: Suchen in unsortiertem Array of Integer beschleunigen.

  Alt 6. Mai 2009, 23:58
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)
Manuel Eberl
„The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.“
- Terry Pratchett
  Mit Zitat antworten Zitat
Satty67

Registriert seit: 24. Feb 2007
Ort: Baden
1.566 Beiträge
 
Delphi 2007 Professional
 
#5

Re: Suchen in unsortiertem Array of Integer beschleunigen.

  Alt 7. Mai 2009, 00:14
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.
  Mit Zitat antworten Zitat
Reinhard Kern

Registriert seit: 22. Okt 2006
772 Beiträge
 
#6

Re: Suchen in unsortiertem Array of Integer beschleunigen.

  Alt 7. Mai 2009, 01:20
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
  Mit Zitat antworten Zitat
Satty67

Registriert seit: 24. Feb 2007
Ort: Baden
1.566 Beiträge
 
Delphi 2007 Professional
 
#7

Re: Suchen in unsortiertem Array of Integer beschleunigen.

  Alt 7. Mai 2009, 07:50
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.
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#8

Re: Suchen in unsortiertem Array of Integer beschleunigen.

  Alt 7. Mai 2009, 08:19
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.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Satty67

Registriert seit: 24. Feb 2007
Ort: Baden
1.566 Beiträge
 
Delphi 2007 Professional
 
#9

Re: Suchen in unsortiertem Array of Integer beschleunigen.

  Alt 7. Mai 2009, 08:38
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
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
43.016 Beiträge
 
Delphi 12 Athens
 
#10

Re: Suchen in unsortiertem Array of Integer beschleunigen.

  Alt 7. Mai 2009, 10:25
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
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list : BugReports/FeatureRequests
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 20:27 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz