Schnellstmöglich Wert im Array finden ?

[myicq]

Hallo,

ich habe das Bedarf schnellstmöglich eine Wert in eine Statische Array zu finden.

Mein Array ist eine Datenbank, ändert sich nicht wenn einmal eingelesen, aber mein Programm muss eine Indexwert schnellstmöglich finden können. Die Daten sind zufällig, können Adressen sein, aber genau so gut PINs etc.

Heute mache ich das sequentiell mit Vergleich, geht aber ich brauche etwa 900 mSec für 5 Mio records.

Ich habe Zeit beim Einlesen der Datenbank eine art "index" zu bauen (ich durchsuche meistens 1. Spalte).

Aber wie mache ich das - brauche kleiner Beispiel.

[freimatz]

Hier ist ein Beispiel:
http://docwiki.embarcadero.com/CodeE...onary_(Delphi)

[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.

[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

[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.