Schnellstmöglich Wert im Array finden ?

[TiGü]

Eine Lösung mit Delphi 6 Professional funktionieren?
900 Millisekunden für 5 Millionen Datensätze sind zu hoch -> welche Zeit wird angestrebt?

[Neutral General]

Binäre Suche in einem sortierten Array.
Aber der Satz "Mein Array ist eine Datenbank" macht mir etwas sorgen
Ich denke dein Problem liegt tiefer und wahrscheinlich solltest du dein grundlegendes Vorgehen überdenken.
Das ist aber von außen ohne mehr Infos schwer zu sagen.

[p80286]

Zitat von Neutral General:

Binäre Suche in einem sortierten Array.
Aber der Satz "Mein Array ist eine Datenbank" macht mir etwas sorgen
Ich denke dein Problem liegt tiefer und wahrscheinlich solltest du dein grundlegendes Vorgehen überdenken.
Das ist aber von außen ohne mehr Infos schwer zu sagen.

Wenn wirklich eine DB im Spiel ist, dann sollte dort gesucht werden, denn dafür ist eine Datenbank gemacht.

Gruß
K-H

[Jasocul]

Ein statisches Array mit 5 Mio Records?
Warum glaube ich das jetzt nicht?

Selbst bei maximaler Ausreizung des Stacks in einer 64Bit-Anwendung müsste das doch einen Stack-Overflow geben, oder?

Sorry, vergesst es.
Mit der Compiler-Direktive geht es. Nur die Einstellung in de Projekt-Optionen ist begrenzt.

Sinnvoll erscheint mir dieses Konzept aber trotzdem nicht.

[OlafSt]

Ich denke, mit statisch ist hier gemeint "unveränderlich".

[QuickAndDirty]

Zitat von p80286:

Zitat von Neutral General:

Binäre Suche in einem sortierten Array.
Aber der Satz "Mein Array ist eine Datenbank" macht mir etwas sorgen
Ich denke dein Problem liegt tiefer und wahrscheinlich solltest du dein grundlegendes Vorgehen überdenken.
Das ist aber von außen ohne mehr Infos schwer zu sagen.

Wenn wirklich eine DB im Spiel ist, dann sollte dort gesucht werden, denn dafür ist eine Datenbank gemacht.

Gruß
K-H

Wenn er das nicht will...
Oder wenn es keinen Schlüssel in der DB auf der gesuchten Spalte gibt?
Man hat ja nicht immer Vollzugriff auf fremdadministrierte Datenbanken.
Wobei es dann irgendwann wohl sinnvoll ist die ganze Datenbank in eine eigene zu spiegeln...hm..stimmt.

[Neutral General]

Zitat von QuickAndDirty:

Zitat von p80286:

Zitat von Neutral General:

Binäre Suche in einem sortierten Array.
Aber der Satz "Mein Array ist eine Datenbank" macht mir etwas sorgen
Ich denke dein Problem liegt tiefer und wahrscheinlich solltest du dein grundlegendes Vorgehen überdenken.
Das ist aber von außen ohne mehr Infos schwer zu sagen.

Wenn wirklich eine DB im Spiel ist, dann sollte dort gesucht werden, denn dafür ist eine Datenbank gemacht.

Gruß
K-H

Wenn er das nicht will...
Oder wenn es keinen Schlüssel in der DB auf der gesuchten Spalte gibt?
Man hat ja nicht immer Vollzugriff auf fremdadministrierte Datenbanken.
Wobei es dann irgendwann wohl sinnvoll ist die ganze Datenbank in eine eigene zu spiegeln...hm..stimmt.

Wenn er das nicht will, dann ist er falls es keine weiteren guten Gründe dafür gibt selbst Schuld wenn das Ergebnis Müll ist.
Selbst wenn auf der Spalte nach der er Suchen will kein Schlüssel/Index drauf ist, ist eine Abfrage über eine Datenbank garantiert immer noch schneller.
Und er hat ja zumindest so viel Zugriff dass er die Daten die er braucht aus der Datenbank ausgelesen hat (vorausgesetz es existiert überhaupt irgendwo eine richtige Datenbank mit den Daten aus seiner Array-"Datenbank")..

[himitsu]

TArray.BinarySearch, für ältere Delphi auch leicht selbst implementierbar (Binäre Suche).

Das Array muß natürlich sortiert sein.

[QuickAndDirty]

Für einen schnellen Zugriff würde ich eine Hashlist statt eines Arrays nehmen.
Damit spart man sich das "sortieren" beim auslesen.
Und das "suchen" beim Anzeigen eines Records fällt auch weg.
Capazität der Hashlist sollte in etwa doppelt so groß sein wie die zu erwartende menge an Records,
da das Einfügen in eine volle Hashlist länger dauert und diese Datensätze danach auch langsamer gefunden werden.(Je nach implementierung)
Bei 5 Millionen Records sind ein Hashwerte von 24 Bit aufwärts zu ermitteln.
Die Hashfunction sollte vor allem schnell sein.

Ich denke THashedStringlist stellt so etwas bereit.


Mittlere Suchzeit:
Hashlist O(1)
Sortiertes Array und Binärbaum O(Log N)
Sequentielle Suche O(N)

Wobei man sagen muss du gewinnst mit nem Sortierten Array schon ungemein, sparst dir halt ein paar millionen vergleiche