Eine kleine Hashtabelle (jetzt ohne Speicherlecks!)

[Alves]

Danke, NTQ.

[Kaeru Gaman]

@NTQ

das ist doch aber nur dann sinnvoll, wenn die haupttabelle nicht alphabetisch sortiert sein kann, oder?

weil, bei alphabetischer sortierung der grunddatensätze brauche ich
mit index-binärer suchmethode längst nicht so lange.

da kann ich mit 256 zugriffen einen von max. 2^256 datensätzen finden...

[NicTheQuick]

Ja, bei alphabetisch sortierten Datensätzen hast du quasi auch eine Art
Hashtabelle, nur ohne Hash.

Problematisch kann es dann allerdings werden, wenn alle oder viele der
Strings gleich anfangen, z.B. "Bild_Inhalt_#Text#.jpg", wobei #Text# sich
ändert.

Fügst du die Einträge durch einen Quicksort-Alogorhythmus in deine Liste ein,
dann geht es auch sehr schnell. Nachteil sind dabei die langsamen
LinkedLists, die sich nicht direkt per Index anspringen lassen, oder im Falle
von Arrays das Verschieben aller nachfolgenden Daten um eins nach hinten.

Es gibt viele Möglichkeiten, solche Aufgaben schnell zu erfüllen. Hashtabellen
sind die gebräuchlisten. Sie werden unter anderem auch bei SQL-Anfragen
verwendet, weil man nicht alle Spalten gleichzeitig sortieren kann. Und genau
das Problem hab ich auch in meiner Datenbank. Und da pflege ich die
Hashtabelle gerade ein.

///Edit:
Und wegen deinen 256 Zugriffen bei 2^256 Datensätzen. Dann erstell mal
eine Zugriffstabelle mit 2^256 Einträgen. Das möcht' ich seh'n.

[Kaeru Gaman]

///Edit:
Und wegen deinen 256 Zugriffen bei 2^256 Datensätzen. Dann erstell mal
eine Zugriffstabelle mit 2^256 Einträgen. Das möcht' ich seh'n.

schon klar

es ging nur um das prinzip des index-binären suchens und wieviel zugriffe es benötigt,
und du hattest was von 256 zugriffen gesagt, deshalb.

bei den von dir angemerkten 1.000.000 datensätzen bräuchte ich mit IndBin max 20 zugriffe.

[NicTheQuick]

Mach mal ein Beispiel in Pseudocode für mich, der nicht versteht, wie du das
mit deinem Index-Binär-Suchen meinst.

[Kaeru Gaman]

pseudocode, ok

Code: Alles auswählen

Anzahl = 100000
LoadArray( Wort$, Anzahl ) ; 100.000 sortierte strings ins Array Wort$()

Input Such$
Sprung = Anzahl / 2
Satz = Sprung

:LABEL:
  Sprung / 2
  If Wort$( Satz ) > Such$
    Satz - Sprung
    Jump LABEL
  EndIf
  If Wort$( Satz ) < Such$
    Satz + Sprung
    Jump LABEL
  EndIf

  If Wort$( Satz ) = Such$
    Print "Gefunden in Satz";Str(Satz)
  Else
    Print "Nicht gefunden"
  EndIf

is jetzt ohne netz (keine prüfung auf Sprung < 1)
und mit nem Jump statt ner schleife...
aber prinzip sollte verstehbar sein...

..hoffe, ich hab mich nich vertan irgendwo, is halt mal runtergehackt...

PS:
http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche

[NicTheQuick]

Ah, klar, okay, dacht' ich's mir doch. Ein abgewandelter QuickSort-Algo zum
Finden von Strings. Wenn das Array einmal steht, ist das kein Problem.

Möchte man jetzt aber das Array on-the-fly füllen, dauert es wieder sein Zeit.

Natürlich könnte man es füllen und erst danach zum Suchen sortieren. Aber
was ist, wenn man es füllt, sucht, füllt, sucht, füllt, sucht, ... Vor jedem
Suchen muss es neu sortiert werden.

Jetzt kann man sich darüber streiten oder einfach sagen:
"Ich optimiere meinen Suchalgo auf mein Problem."

Und ich brauche eben eine Hashtabelle.

[Kaeru Gaman]

ja is klar. für dynamische datenmengen ist eine hashtabelle bestimmt eine gute lösung.

z.b. bei nem textparser, fürn adventure oder nen Eliza-Clone, ist IndBin einfach unschlagbar,
weil man bei nem Realese eine komplette, vorsortierte Wortschatz-tabelle mitliefern kann.

[remi_meier]

Aber was ist, wenn man es füllt, sucht, füllt, sucht, füllt, sucht, ...
Vor jedem Suchen muss es neu sortiert werden.

Dann versuch mal mit Heapsort, meiner Erinnerung nach geht das dynamische
Einfügen in einen Sortierten Heap dort sehr schnell. Wenn ich mal zu viel
Zeit hab, werd ich mich daran ev. mal versuchen.

Aber Hash-Table wird wohl trotzdem im allgemeinen Fall am schnellsten
sein, nicht umsonst wird es wohl so oft angewandt.

[uweb]

Ich kann leider Nichts zu der Diskussion beitragen, aber zumindest mit dem gewünschten Feedback dienen :

Es gehört zu den Dingen die noch auf meiner Liste stehen. Ich habe eine grobe Vorstellung davon WAS mein Programm tun soll. Für das WIE habe ich diese Liste die ich nun Schritt für Schritt abarbeite. Es wird also für mich interessant.

Unabhängig davon :
Es wäre schade wenn Du (oder jemand anderes) irgendetwas nicht realisieren würde weil er den Eindruck hat es würde niemanden interessieren. Wir Deutschen sind da wohl stark durch die Schwaben geprägt ("Nicht gemotzt ist genug gelobt."). Ich denke die Gemeinde ist so groß und vielfältig, daß es außer Frage steht ob irgendjemand etwas brauchen kann. Brauchen und gebrauchen ist allerdings zweierlei. Manche Perlen gehen wohl deshalb unter weil man um sie gebrauchen zu können schon fit sein muß.

Also hiermit an ALLE die dazu beitragen, daß das Forum eine riesige Schatzkiste ist : VIELEN DANK !
Damit meine ich nicht nur die Rubrik "Code, Tipps und Tricks".

@NicTheQuick : Ein Extra-Danke für die Erklärungen und Beispiele die Du i.d.R. mitlieferst.