Array durchsuchen

[Muellermilchtrinker]

Hallo DP,

stehe mal wieder vor einem Problem. Ich hab ein array:

Delphi-Quellcode:

azs: array['a','b','c',...,'z'] of string

. Wenn ich jetzt wissen will, an welcher Stelle das h steht, dann muss ich das Array durchsuchen.
Nur wie mache ich das.
Habe mir gedacht, dass ich eine Funktion schreibe, die von Anfang bis Ende bzw. bis zum Fundort das Array durchgeht und dann schaut, ob der Inhalt das entsprechende Suchwort ist.
Aber ich denke, dass das nicht sehr effizient ist und unter Umständen sehr lange dauern kann, wenn mein Suchwort sehr weit hinten steht, da das Array noch ein bisschen größer sein wird.
Hab schon in der Delphi-Reference gesucht, aber kein entsprechenden Eintrag gefunden.
Vielleicht gibt es ja schon eine fertige optimierte Lösung.
Danke schonmal.

[mkinzler]

Ist der einfachste Weg. Schneller wäre es nur, wenn du andere Konstrukte, wie z.B. eine Baumstruktur verwenden würdest, oder ein Index mit entsprechender Struktur

[Matze]

Ich vermute, dass jede Lösung zum Durchsuchen eines einfachen Arrays intern mit einer Schleife arbeiten wird.

[Satty67]

Sind die Elemente im Array sortiert?

[Muellermilchtrinker]

Sind nicht sortiert. Ich werd es einfach mal ausprobieren.
BTW: Wie messt ihr da eigentlich immer die Zeit???

[Satty67]

Zum messen eine StopUhr ;-) (kein Scherz!... siehe Suche: TStopUhr )

Unsortiert dann wohl wie vorgeschlagen nur ein Baum, SkipList/HaschList etc.

[mkinzler]

Ein Baum ohne Sortierung bringt nichts.
Und bei einer Hasch-Liste ist es einem vielleicht egal :wink:

[Satty67]

Ich dachte mehr, die Liste gleich beim erzeugen so zu generieren. Wenn die Liste wie beschrieben nur ein Array bleiben muss, dann halt wirlich nur der Schleifendurchlauf.

Aber denke doch, dass das eigener Quellcode ist und wenn es zu lange dauert müsste man halt die Art der Liste anpassen.

[himitsu]

Wer sagt denn daß der Baum nicht sortiert wäre?
Wenn die Hashliste nicht reicht, dann wäre ein Baum schon möglich.

Bei der Hashliste muß zwar immernoch das "ganze" Array durchlaufen werden, aber dafür müssen nur noch Integer und nicht rießige Strings verglichen werden.

Für den Baum muß, wenn das Array nicht sortiert ist, doch einfach nur ein zusätzlicher Index angelegt werden, in Form des Baums.

Wobei man auch bei der HashListe parallel die Hashs in einer sortierten Hash+Index-Liste halten kann.

[Matze]

Zitat:

Zitat von Muellermilchtrinker (Beitrag 1049077)

BTW: Wie messt ihr da eigentlich immer die Zeit???

Ich i.d.R. so:

Delphi-Quellcode:

var
  i: Integer;
  Start, Stop: Integer;
begin
  Start := GetTickCount;

  for i := 1 to 1000 do
  begin

    // dein Funktionsaufruf

  end;

  Stop := GetTickCount;

  ShowMessage(FloatToStr((Stop - Start) / 1000) + ' ms');

Die Test-Funktionen rufe ich immer mehrfach auf, um reproduzierbare Ergebnisse zu erhalten, auch bei sehr kurzen Durchlaufzeiten.

[Satty67]

Kommt halt darauf an, wie oft die Liste durchsucht werden muss. Wenn öfter, lohnt sich ein Umbau oder notfalls Nebenkonstrukt.

Bei der HashListe dachte ich nun auch daran, das die Hash sortiert vorliegen und damit eben der Suchaufwand minimiert wird.

[alzaimar]

Eine Hashliste sagt mir nicht viel, aber eine Hashmap oder auch Assoziativarray ist eine Struktur, bei der die Daten schon an der richtigen Stelle liegen.

Dabei kommt der Hashfunktion eine zentrale Bedeutung zu: Sie berechnet aus dem Schlüssel direkt die Adresse der Daten. Hier wird also nichts gesucht oder ein Array durchlaufen.

Idealerweise findet man in einer Hashmap die Daten so:

Delphi-Quellcode:

GesuchteDaten := Daten[HashFunktion(Schluessel)];

.

Wobei 'Daten[]' hier ein irgendwie dimensioniertes Array darstellt und die Hashfunktion so dermaßen genial ist, das sie die richtige Stelle für einen gegebenen Schlüssel ausrechnet.

In der Praxis ist es natürlich nicht so einfach, eine dermaßen superdupergeile Funktion zu implementieren, weshalb man zu diversen Tricks greifen muss, um die Suche trotzdem fast so einfach wie oben beschrieben durchzuführen.

Also: Eine Hashmap wird nicht durchsucht und ist somit hinsichtlich der Performance beim Einfügen und Suchen optimal.

[mkinzler]

Wurde früher ekzessiv eingesetzt ( Regional-3)

[Satty67]

HashListe kenne ich als Liste, bei der die Array-Position durch den HashCode definiert ist. Also der Hash quasi als Index. Also im Prinzip das was Alzaimar als HashMap kennt.

Wo ich Alzaimars Post nochmal durchlese:

Delphi-Quellcode:

GesuchteDaten := Daten[HashByte1, HashByte2, HaschByte2, ... HaschByteN];

.
Die Länge eines HashCodes ist bei den meisten Hash-Funktionen ja bekannt... Will mann doppelte (identische) Listeeinträge aber nicht ignorieren, wird es lustig.Für doppelte Einträge eine Struktur Count,Value.

Wenn ich mich nicht verrechnet habe, braucht eine Einfache Hashliste basierend auf MD5 nur 40 KB für den Index.

Ich überlege gerade, ob der Threadstarter überhaupt an weiterführenden Lösungen interessiert ist.

[xZise]

Moin Matze,
dürfte da nicht Sekunden statt Millisekunden raus kommen?

MfG
Fabian

[Muellermilchtrinker]

Als ich versteh da was nicht:
meine Funktion:

Delphi-Quellcode:

function SearchArray(Suchmaske:String):Integer;
  var i:Integer;
begin
  Result := 0;
  for i := 0 to high(asz) do
  begin
    if asz[i]=Suchmaske then
    begin
      result := i;
      break;
    end;
  end;
end;

So mach ich die Zeitmessung:

Delphi-Quellcode:

procedure TForm1.Button2Click(Sender: TObject);
  var
  i: Integer;
  Start, Stop: Integer;
begin
  Start := GetTickCount;

  for i := 1 to 1000 do
  begin
    SearchArray('Z');
  end;

  Stop := GetTickCount;

  ShowMessage(FloatToStr((Stop - Start) /1000) + ' ms');
end;

Asz ist das Array da steht A bis Z drin.

Ich bekomm bei Z eine Zeit von 0 ms.
Da stimmt doch was net. :stupid:

[himitsu]

Zitat:

Delphi-Quellcode:

ShowMessage(FloatToStr((Stop - Start) /1000) + ' ms');

Das vor dem Komma sind Sekunden (wegen dem /1000)

Erhöhe mal die Anzahl der Durchläufe.
GetTickCount hat 'ne Auflösung von etwa 16ms und es wird abgerundet.
(eine Dauer von weniger als 16ms kann 0 ergeben)

[Muellermilchtrinker]

Bei 1 Millionen Durchläufen bekomm ich eine Zeit von 0,562 ms :D

[himitsu]

Nimm mal das /1000 aus der Berechnung oder nimm "s" statt "ms" :zwinker:

[xZise]

Zitat:

Zitat von himitsu (Beitrag 1049351)

Nimm mal das /1000 aus der Berechnung oder nimm "s" statt "ms" :zwinker:

Was ich nicht sag :D

Aber abgesehen davon: Wenn man 26 Einträge 1000 Durchsucht und man erwartet werte mit mehreren hunderstel Sekunden (so ab 30 ms), dann braucht man eine CPU die selbst du schlagen kannst beim Kopfrechnen :mrgreen:

MfG
Fabian