Array durchsuchen

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

[himitsu]

Zitat:

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

[himitsu]

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

[xZise]

Zitat von himitsu:

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

Was ich nicht sag

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

MfG
Fabian