|
|
|
Was wir machen wollen, ist im Prinzip ziemlich einfach: Wir wollen die Liste so erweitern, dass ihre Einträge sortiert abgespeichert werden. Das ist ja nicht weiters schwierig: Statt die neuen Einträge einfach hinten dran zu hängen, sucht die Speicherroutine jedesmal die Liste ab, an welcher Stelle das neue Element der Sortierung nach reinpasst. Die Sache hat nur zwei Haken: Erstens: Wir sind anspruchsvoll. Wir wollen nicht nur Zahlen oder Strings als Key zulassen, sondern beliebige Datentypen.
Sie können sich darunter nichts vorstellen? Nun, nehmen wir an, Sie haben es mit recht grossen Speicher-Objekten zu tun, die Sie in die Liste packen wollen, jedes sehr unübersichtlich. Eine grosse Erleichterung kann es sein, "Visitenkarten" für diese Objekte zu pflegen, mit wenigen charakteristischen Informationen, die schnell zugreifbar und durchsuchbar sind. Solche Visitenkarten sind in grossen und komplexen Programmen viel besser als Zeiger, da sie "sprechend" sind: Man sieht sofort, mit welchem Objekt man es zu tun hat. Man kann das natürlich auf mehrere Art und Weisen realisieren - das ist ein eigenes Kapitel. Aber die mit Abstand eleganteste Art ist es, die Objekte in einer Hash-Liste zu halten und als Key die Visitenkarte zu benutzen: myobj=omahash_find(vistenkarte). Das ist nur eines von vielen Beispielen. Ein anderes wäre z.B., dass es wünschenswert ist, Grafikobjekte in einer 3D-Landschaft schnell zu finden, wenn man sie mit der Maus aktiviert. Führt man die Grafikobjekte in einer Hash-Liste mit den 3D-Koordinaten als Key, findet man sie sehr schnell - einen schnelleren Weg gibt es nicht.
Das alles geht mit Freebasic. Allerdings: Wie sortieren wir nach "beliebigen Datentypen"? Sortierung benötigt eine Vorstellung von "kommt nachher" und "kommt vorher". Beschränken wir uns beim Sortieren auf String-Keywords, dann ist das auch kein grosses Problem: Wir können ja die alphabetische Ordnung benutzen. Aber bei beliebigen Objekten können wir nicht so einfach von "alphabetisch" sprechen. Der Trick ist, dass man dem Anwender der Hash-Listen überlässt, wie er die Sortierung bildet. Für andere Datentypen als Zahlen oder Strings ist die Art der Sortierung auch gar nicht so wichtig, wichtig ist nur, dass sortiert wird. Der Anwender übergibt der Hash-Liste selbst eine ganze Sortierfunktion als Argument und sagt: "Da! Benutz das!" Das nennt man dann eine Callback-Funktion.
Der andere Haken ist die Tatsache, dass allein durch die Sortierung die Suche noch nicht beschleunigt wird. Was wir noch brauchen, ist einen echten wahlfreien Zugriff auf unsere Listenelemente. Wie bekommen wir den? Nun, hier muss man an irgendeiner Stelle einen Kompromiss machen. Wir werden ihn so machen, dass wir beim ersten Lese-Zugriff nach einem Schreibzugriff ein Array mit Zeigern auf die Listenelemente bilden. Das dauert natürlich. Bei allen folgenden Lesezugriffen ist dieses Array bereits erstellt und es geht schnell. Man sollte also diesen Typ von Hash-Liste nicht für Einsatzzwecke hernehmen, in denen laufend zwischen Lesen und Schreiben gewechselt wird und es noch gleichzeitig auf Geschwindigkeit ankommt. Aber das kommt in der Programmierung sehr selten vor. Viel häufiger ist der Fall, dass Lesen und Schreiben Vorgänge sind, die eher getrennt gehalten werden: Z.B. werden bei der Initialisierung oder bei einer User-Aktion alle Daten geladen und ab da wird nur noch gelesen. Insofern wird unsere Hash-Liste in den allermeisten Fällen gute Leistung erbringen. Nun zur Realisierung.
Callback-Funktionen treffen wir an verschiedenen Stellen immer wieder an. In Bibliotheken ("Libs") tauchen sie oft auf, wenn es darum geht, dass eine Routine auf ein bestimmtes Ereignis reagieren soll: Die Callback-Funktion sagt dann, wie reagiert werden soll. Bei der Hardwareansteuerung werden dem Betriebssystem die Übersetzerroutinen als Callbackfunktionen übergeben. Auch im Bereich der Compiler wird oft mit Callback-Funktionen gearbeitet. Generell kann man folgende Fälle unterscheiden:
Wie funktioniert das? Der Trick ist, dass die Funktion als Variablentyp deklariert und behandelt wird:
' Beispiel für einfache Callback-Funktion SUB routine(xsub AS SUB(x AS DOUBLE)) ? xsub(2.5) END SUB
Wir übergeben also ein Argument vom Typ SUB oder FUNCTION. Das geht. Dabei sieht die SUB- oder FUNCTION-Deklaration ganz genauso aus wie ein SUB- oder FUNCTION-Header - nur ohne Namen.
Wir können allerdings nun nicht einfach beim Aufruf eine Funktion reinstecken, die denselben Header hat:
'Das funktioniert nicht: SUB x1SUB(x AS double) ? x SLEEP END SUB SUB routine(xsub AS SUB(x AS DOUBLE)) xsub(2.5) END SUB routine(x1sub)
Das liegt daran, dass x1sub kein Typ zugewiesen wurde, der dann mit dem Typ des xsub-Arguments verglichen werden könnte. Also muss das vorher noch gemacht werden, und zwar mit DECLARE. Man schreibt einfach den Header der Funktion ein zweites Mal hin, aber mit dem Schlüsselwort "DECLARE" davor. Das ist syntaktisch inkonsequent, konsequenter müsste es mit dem Schlüsselwort "AS" funktionieren, wie bei Variablen hinter DIM und wie in der Argumentenliste der aufrufenden Funktion auch. Aber das sind Altlasten von QBASIC, da kann man nichts machen:
' Jetzt funktionierts immer noch nicht: DECLARE x1SUB AS SUB(x AS double) SUB x1SUB(x AS double) ? x SLEEP END SUB SUB routine(xsub AS SUB(x AS DOUBLE)) xsub(2.5) END SUB routine(x1sub)
Es funktioniert immer noch nicht. Das liegt am Auruf von routine(). Obwohl das optisch in der Deklaration von routine() nicht ersichtlich ist, erwartet routine() einen Zeiger - etwas anderes kann sie ja gar nicht erwarten. Ein Zeiger auf eine Funktion ist schlicht eine Adresse, ab der das Maschinenprogramm weiter ausgeführt werden soll. Eine GOTO-Zeilennummer, wenn man so will. Das kann man übergeben. Die Funktion selbst - was sollte das sein? Aber leider wird diese Natur des Arguments in der Argumentenliste nicht deutlich: Man deklariert "as SUB", nicht as "as SUB PTR". Trptzdem muss man beim Aufruf den Adressoperator @ verwenden, um den Zeiger auf die Funktion zu übergeben: routine(@x1sub), nicht routine(x1sub)!
' Jetzt funktionierts: DECLARE SUB x1SUB(x AS double) SUB x1SUB(x AS double) ? x SLEEP END SUB SUB routine(xsub AS SUB(x AS DOUBLE)) xsub(2.5) END SUB routine(@x1sub)
Solche Funktionenzeiger kann man sogar in Verbundvariablen (Objekten, UDT's) speichern:
' Jetzt funktioniert's: DECLARE SUB x1SUB(x AS double) TYPE tdata mysub AS SUB(x AS double) END TYPE DIM SHARED AS tdata xdata SUB x1SUB(x AS double) ? x SLEEP END SUB SUB routine(xsub AS SUB(x AS DOUBLE)) xdata.mysub=xsub xdata.mysub(2.5) END SUB routine(@x1sub) ? "Nun Aufruf direkt:" xdata.mysub(3)
Gute Sache? Jetzt wollen wir das noch auf unseren konkreten Fall anwenden.
Übung1:
(Sehr leicht): Schreiben Sie eine Sortierfunktion für zwei Integerzahlen a und b. Sie gibt -1 zurück, falls a < b, 0, falls a=b und 1, falls a >=b.So, nun kleiner Haken: Gestalten Sie den Header so, dass zwei any ptr übergeben werden. Sie können voraussetzen, dass diese auf Integers zeigen.
Übung2:
Erweitern Sie tomalist so, dass es auch eine Sortierfunktion des obigen Typs aufnehmen kann. Generieren Sie eine Liste und übergeben Sie Ihre Integer-Sortierfunktion an Ihre Liste!
Die Integer-Sortierfunktion war natürlich fast die einfachste aller denkbaren Sortierfunktionen. Die nächste Standardsortierfunktion wäre eine für Strings. Dazu brauchen wir aber zunächst eine allgemeine Funktion, die Strings alphabethisch vergleicht. Freebasic hat keine solche in der Runtime-Lib, so sollten wir uns selbst eine basteln.
Übung3:
Bauen Sie eine Routine FUNCTION compstr(s1 as string, s2 as string) as integer, die -1 zurückgibt, falls s1 vor s2 im Alphabet kommt, 0, falls s1 und s2 auf der Länge des jeweils kürzeren Strings identisch sind und +1, falls s1 nach s2 im Alphabet kommt. Beispiele: s1="hallo", s2="halli" ==> +1. s1="hallo", s2="hallo-hallo" ==> 0. s1="1234", s2="a234" ==> -1.
Ob die Sortierung auf Gross- und Kleinschreibung sensitiv sein soll, das überlasse ich Ihnen.
Meine Version (allerdings mit zstring):
FUNCTION compstr(s1 AS ZSTRING PTR, s2 AS ZSTRING PTR) AS INTEGER
'Gibt 1 zurueck, falls s1 alphabetisch nach s2 kommt
'Gibt 0 zurueck, falls s1 und s2 alphabetisch gleich anfangen
'Gibt -1 zurueck, falls s1 alphabetisch vor s2 kommt
'Gross/Klein wird ignoriert
DIM AS STRING ss1,ss2,ss3
DIM AS INTEGER slen1,slen2,slen3
DIM AS INTEGER i,j1,j2,found,retval
ss1=*s1:ss2=*s2
ss1=UCASE(ss1):ss2=UCASE(ss2)
slen1=LEN(ss1):slen2=LEN(ss2)
i=1
found=FALSE
DO
j1=ASC(mid$(ss1,i,1))
j2=ASC(mid$(ss2,i,1))
'? j1,j2
found=(j1<>j2)
i+=1
LOOP UNTIL (found OR i=slen1+1 OR i=slen2+1)
retval=0
IF (found) THEN
IF (j1>j2) THEN retval=1 ELSE retval=-1
END IF
compstr=retval
END FUNCTION
Übung 4:
Schreiben Sie nun mit Hilfe von compstr() eine zweite Sortierfunktion mit zur integer-Sortierfunktion identischem Header, die aber Strings sortiert!
Nun haben wir schon zwei Sortierfunktionen für Standardfälle. Es wird praktisch sein, diese beiden Standardfälle mit in die Lib aufzunehmen. Das heisst, der Anwender muss nicht, wenn er nach Integer oder Strings sortieren will, sich jedes Mal selbst mühevoll eine Sortierfunktion zusammenpopeln, sondern kann sagen: "Benutze String-Sortierung!" oder "Benutze Integer-Sortierung!". Diese beiden Fälle bekommen die Konstanten const OMAHASH_KEYSTRING=1 und const OMAHASH_KEYINT=2 zugewiesen. const OMAHASH_GEN=0 wird gesetzt, wenn eine benutzerdefinierte Sortierfunktion zur Anwendung kommt.
Übung 5:
Erweitern Sie die omalist-Lib so, dass bei der init-Routine zwei optionale Argumente übergeben werden können:
Ich habe die resultierende omalist schon mal "omahash" genannt und dann sieht das so aus:
'Eigene Listen und Hashes
#INCLUDE "fbgfx.bi"
CONST NULL=0
CONST FALSE=0
CONST TRUE=-1
CONST OMALIST_START=0
CONST OMALIST_END=1
CONST OMALIST_FWD=2
CONST OMALIST_BWD=3
CONST OMA_BEHIND=1
CONST OMA_BEFORE=-1
CONST OMAHASH_KEYGEN=0
CONST OMAHASH_KEYSTRING=1
CONST OMAHASH_KEYINT=2
option EXPLICIT
option BYVAL
TYPE tomahash_element
prev AS tomahash_element PTR
nex AS tomahash_element PTR
cont AS ANY PTR
key AS ANY PTR
END TYPE
' ------------------------------------------------------------
TYPE tomahash
start AS tomahash_element PTR
last AS tomahash_element PTR
current AS tomahash_element PTR
size AS INTEGER
typename AS STRING
sortfunc AS FUNCTION (apkey1 AS ANY PTR, apkey2 AS ANY PTR) AS INTEGER
END TYPE
DECLARE FUNCTION omahash_std_sort(apkey1 AS ANY PTR, apkey2 AS ANY PTR) AS INTEGER
DECLARE FUNCTION omahash_str_sort(apkey1 AS ANY PTR, apkey2 AS ANY PTR) AS INTEGER
' ------------------------------------------------------------
FUNCTION omahash_std_sort(apkey1 AS ANY PTR, apkey2 AS ANY PTR) AS INTEGER
'Gibt 1 zurueck, falls key1 > key2 und 0, falls key1=key2 und -1, falls key1 < key2
DIM AS LONGINT PTR pkey1, pkey2
DIM AS INTEGER retval=1
pkey1=apkey1:pkey2=apkey2
IF (*pkey1=*pkey2) THEN retval=0
IF (*pkey1 < *pkey2) THEN retval=-1
omahash_std_sort=retval
END FUNCTION
' ------------------------------------------------------------
FUNCTION omahash_str_sort(apkey1 AS ANY PTR, apkey2 AS ANY PTR) AS INTEGER
'Gibt 1 zurueck, falls key1 > key2 und 0, falls key1=key2 und -1, falls key1 < key2
DIM AS ZSTRING PTR pkey1, pkey2
DIM AS INTEGER retval=0
DIM AS INTEGER i,j1,j2,found,slen1,slen2
pkey1=apkey1:pkey2=apkey2
retval=compstr(*pkey1,*pkey2)
omahash_str_sort=retval
END FUNCTION
' ------------------------------------------------------------
SUB omahash_init(BYREF list AS tomahash, typename AS STRING, mode0 AS INTEGER = OMAHASH_KEYINT, _
sortfunc AS FUNCTION (apkey1 AS ANY PTR, apkey2 AS ANY PTR) AS INTEGER = NULL)
list.start=NULL
list.last=NULL
list.current=NULL
list.size=0
list.typename=typename
list.hashgenerated=FALSE
list.hashtable=NULL
IF (mode0=OMAHASH_KEYINT) THEN list.sortfunc=@omahash_std_sort
IF (mode0=OMAHASH_KEYSTRING) THEN list.sortfunc=@omahash_str_sort
END SUB
Bei einer Hash-Liste macht "Hintenanfügen", also eine push-Routine keinen Sinn. Der Witz ist, dass man immer sofort alle Inputs ordentlich einsortiert. Wir nennen diese Routine "put". Sie macht zwei Dinge:
Wir benutzen also die omalist_insert()-Routine, die wir nur ein klein wenig abwandeln müssen, da key ja nun kein Stringtyp mehr ist, sondern ein typenloser Pointer.
Beim Suchen bleibt uns hier nur die einfache Variante der linearen Suche übrig: Wir suchen in einer linearen Schleife, bis wir die richtige Stelle gefunden haben. Eine bessere Variante wäre, eine schnelle Suchroutine zu benutzen, wie wir sie dann auch beim Lesezugriff anwenden. Aber das würde wahlfreien Zugriff voraussetzen und den haben wir zu diesem Zeitpunkt nicht.
Übung 6:
Schreiben Sie eine put-Routine für die neuen Daten! Suchen Sie mittels der eingestellten Sortierfunktion nach der richtigen Position. Berücksichtigen Sie, dass diese Position auch vor dem Beginn oder nach dem Ende der bisherigen Liste liegen kann und dass am Anfang die Liste leer ist.
Meine Lösung:
SUB omahash_put(BYREF list AS tomahash, px AS ANY PTR, typename AS STRING, pkey AS ANY ptr)
'Fuegt ein neues Element ein
WITH list
IF .typename<>typename THEN brkmess("tomahash, put(): typename error")
IF px=NULL THEN brkmess("tomahash, put(): content is NULL")
'Suche Einfuegeposition
IF (.start<>NULL) THEN
SCOPE
DIM AS INTEGER foundend=FALSE
DIM AS tomahash_element PTR newelem
'Die SOrtierung ist der sortfunc-Groesse nach, das kleinste bei .start.
.current=.start
'pkey > current key
WHILE(NOT foundend AND .sortfunc(pkey,.current->key)=1)
IF (.current->nex<>NULL) THEN .current=.current->nex ELSE foundend=TRUE
WEND
'Drei moegliche Ergebnisse der Schleife:
IF (foundend=FALSE) THEN
'"Regulaeres" Ergebnis: .current zeigt auf das erste Element, das sortfunc-groesser
'ist als pkey ==> Fuege pkey vor .current ein
omahash_insert(list,.current,px,typename,OMA_BEFORE,pkey)
ELSE
'Falls die while-Schleife wegen foundend verlassen wurde, ist nicht
'klar wie der sortfunc() ausging
IF (.sortfunc(pkey,.current->key)=1) THEN
'pkey muss als Letztes Element rein
omahash_insert(list,.current,px,typename,OMA_BEHIND,pkey)
ELSE
'pkey muss als vorletztes Element rein
omahash_insert(list,.current,px,typename,OMA_BEFORE,pkey)
END IF
END IF
END SCOPE
ELSE
'Liste noch leer
'==> Position ist egal
omahash_insert(list,NULL,px,typename,OMA_BEFORE,pkey)
END IF
.hashgenerated=FALSE
END WITH
END SUB
Nun machen wir uns auf die Suche nach einem schnellen Such-Algorithmus. Wir entwickeln diesen nicht selbst - es ist schon soviel auf dem Gebiet "Suchen" und "Sortieren" gemacht worden, da muss man das Rad nicht zum zwanzigsten Mal neu erfinden. Einfach mal in der Wikipedia (www.wikipedia.de) auf das Informatik-Portal unter "Algorithmen" gehen. Da stossen wir schnell auf die "Binäre Suche". Ich habe den Algorithmus allerdings dem Standardwerk "Algorithmen" von Robert Sedgewick entnommen - da werden keine grossen Unterschiede sein, nehme ich an.
Der Haken an der binären Suche ist, dass sie neben der Sortierung des Arrays auch einen wahlfreien Zugriff benötigt. Nehmen wir an, wir haben ein Integer-Array xdata(), das nach der Grösse sortiert ist. Suchen wir nach einem Wert y, dann liefert uns die binäre Suche im Mittel in ln(N) Schritten (und nicht in N/2 Schritten) das gewünschte Ergebnis. Das ist eine erhebliche Verkürzung, wenn es N=100000: ln(N)=11,5. Ein Geschwindigkeitszuwachs um einen Faktor 1000!
Das setzt allerdings voraus, dass wir auf xdata[i] für beliebiges 0<=i<N zugreifen können.
Der Trick, den wir uns einfallen lassen: Wir erzeugen ein solches Array dynamisch. Und zwar beim ersten Lesezugriff nach einem Schreibzugriff. Allerdings stecken wir natürlich nicht die ganze Liste in das Array, sondern nur die Zeiger auf die Listenelemente. Dann können wir sowohl auf die Key's als auch auf die Inhalte zugreifen. Wir nennen dieses Array "hashtable". hashtable[i] liefert uns also einen Zeiger auf ein Listenelement. Da wir laufend sortiert abgespeichert haben, müssen wir nur noch alle Listenelementzeiger in einer Liste in hashtable[] übertragen. Dann ist die Reihenfolge bzgl. key auch gleich sortiert. Wunderbar.
Übung 7:
Schreiben Sie eine Routine SUB omahash_genhash(byref list as tomahash), die hashtable erzeugt. Führen Sie in tomahash ein Flag hashgenerated ein, das zu Anfangs auf FALSE gesetzt ist, von jedem Schreibzugriff auf FALSE gesetzt wird, beim Lesezugriff geprüft wird. Ggf. wird omahash_genhash() aufgerufen. Dieses wiederum setzt das Flag auf TRUE.
Meine Lösung von omahash_genhash():
SUB omahash_genhash(BYREF list AS tomahash)
'Generiere Hashtable
DIM AS INTEGER i
WITH list
IF (.hashgenerated) THEN EXIT SUB
IF (.hashtable<>NULL) THEN DEALLOCATE .hashtable
.hashtable=ALLOCATE(LEN(tomahash_element PTR)*.size)
i=0
.current=.start
WHILE (.current<>NULL)
IF (i<=.size-1) THEN .hashtable[i]=.current
.current=.current->nex
i+=1
WEND
.hashgenerated=TRUE
? "hash generated ..."
END WITH
END SUB
Die eigentliche binäre Suche kann man in eine Routine omahash_search() packen. Hier der allgemeine Algorithmus:
Eingabe: (S)uchschlüssel, (A)rray (sortiert)
Variable: SucheErfolgreich = falsch (Boolesche Variable)
Variable: ErstesElement = 1
Variable: LetztesElement = Anzahl der Elemente im Array
Wiederhole
Variable: Mitte = ErstesElement + ((LetztesElement - ErstesElement) DIV 2)
Wenn A[Mitte] = S ist dann
SucheErfolgreich = wahr
Sonst
Wenn S < als A[Mitte] ist dann
links weitersuchen (LetztesElement = Mitte - 1)
Sonst
rechts weitersuchen (ErstesElement = Mitte + 1)
Ende Wenn
Ende Wenn
Solange (SucheErfolgreich = falsch) und (ErstesElement <= LetztesElement)
Wenn SucheErfolgreich = wahr dann
Ausgabe: A[Mitte]
Sonst
Ausgabe: Suche nicht erfolgreich (Suchschlüssel nicht in Array vorhanden)
Ende Wenn
Quelle: http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche
Übung 8:
Setzen Sie diese in einer Funktion FUNCTION omahash_search(byref list as tomahash, key as any ptr) as integer um, die .current auf das gesuchte Element setzt und TRUE zurückgibt, falls das gesuchte Element gefunden wurde.
Schreiben Sie omalist_find() in omahash_find() um, indem Sie von dort nur noch omahash_search() aufrufen.
Meine Lösung:
FUNCTION omahash_search(BYREF list AS tomahash, key AS ANY PTR) AS INTEGER
'Sucht key und setzt .current auf diese Position
'Binäre Suche
'Rueckgabe: TRUE, falls key gefunden, FALSE, falls nicht.
DIM AS INTEGER i,LEFT0,right0
WITH list
IF (.hashgenerated=FALSE) THEN omahash_genhash(list)
LEFT0=0
RIGHT0=.size-1
DO
i=INT((RIGHT0+LEFT0)/2)
.current=.hashtable[i]
IF .sortfunc(key,.current->key)<=0 THEN RIGHT0=i-1 ELSE LEFT0=i+1
LOOP UNTIL (.sortfunc(.current->key,key)=0 OR LEFT0>right0)
omahash_search=(.sortfunc(.current->key,key)=0)
END WITH
END FUNCTION
' ------------------------------------------------------------
FUNCTION omahash_find(BYREF list AS tomahash, key AS ANY PTR) AS ANY PTR
DIM AS INTEGER retval
WITH list
retval=omahash_search(list,key)
IF (retval) THEN omahash_find=.current->cont ELSE omahash_find=NULL
END WITH
END FUNCTION
Das war's! Die restlichen Routinen omalist_start() usw. können 1:1 in omahash_ übertragen werden. Damit funktioniert unsere neue Hashliste!
Übung 9:
Schreiben Sie einen Wrapper für String-String-Listen. Das heisst: Key ist Stringtyp, Content ist Stringtyp. Schreiben Sie auch einen Logger, der Ihnen den Inhalt der Liste in eine Datei schreibt. Testen Sie Hash-Liste und Wrapper.
Ein Wrapper und ein kleiner, sehr einfacher Test:
SUB hash_strstr_put(BYREF list AS tomahash,s AS STRING, si AS string)
DIM AS ZSTRING PTR s1
DIM AS ANY PTR s2
DIM AS ANY PTR qi
DIM AS ZSTRING PTR pi
'%%2
s1=ALLOCATE(LEN(s)+1)
*s1=s
s2=s1
pi=ALLOCATE(LEN(si)+1)
*pi=si
qi=pi
omahash_put(list,s2,"strstr",qi)
END SUB
' ------------------------------------------------------------
FUNCTION hash_strstr_find(BYREF list AS tomahash, si AS STRING) AS STRING
DIM AS STRING ss
DIM AS ZSTRING PTR s1
DIM AS ANY PTR s2
DIM AS ANY PTR qi
DIM AS ZSTRING PTR pi
pi=ALLOCATE(2*LEN(si)+1)
*pi=si
qi=pi
s2=omahash_find(list,qi)
IF (s2=NULL) THEN
ss=""
ELSE
s1=s2
ss=*s1
END IF
hash_strstr_find=ss
END FUNCTION
' ------------------------------------------------------------
SUB hash_strstr_log(BYREF list AS tomahash)
DIM pcont AS ZSTRING PTR
DIM pi AS ZSTRING PTR
DIM endoflist AS INTEGER
DIM AS INTEGER i
OPEN "hashlog2.txt" FOR OUTPUT AS #9
endoflist=FALSE
i=0
omahash_setstart(list)
WHILE (NOT endoflist)
pi=list.current->key
pcont=list.current->cont
? #9,i,*pi,*pcont
endoflist=(NOT omahash_stepfwd(list))
'? "**",i,endoflist
'sleep
i+=1
WEND
CLOSE(9)
END SUB
' ------------------------------------------------------------
SUB testomahash2
DIM AS tomahash hash
DIM AS STRING ns,s1,kstr(10)
DIM AS INTEGER i,j
omahash_init(hash,"strstr",OMAHASH_KEYSTRING)
kstr(0)="adam"
kstr(1)="isidor"
kstr(2)="isidor2"
kstr(3)="isidor-adam"
kstr(4)="foo"
kstr(5)="foofoo"
kstr(6)="aoma"
kstr(7)="boma"
kstr(8)="omaa"
kstr(9)="oma-oma"
FOR i=0 TO 9
j=RND*10
ns=LTRIM(STR(j))
s1=STRING(9,ns)
? i,j,kstr(j),s1
hash_strstr_put(hash,s1,kstr(j))
omahash_log(hash)
hash_strstr_log(hash)
'sleep
NEXT i
FOR i=0 TO 19
j=RND*10
? i,j,kstr(j),hash_strstr_find(hash,kstr(j))
NEXT i
SLEEP
omahash_close(hash,"strstr")
END SUB
Übung 10:
Vergleichen Sie die Zugriffsgeschwindigkeiten beim Lesen und Schreiben zwischen Array, omalist und omahash, indem Sie String-String-Listen unterschiedlicher Grösse generieren und befüllen und die Zeit für das komplette Schreiben und die Zeit für 1 Mio. Lesezugriffe auf zufällige Elemente messen. Lassen Sie aus den Messergebnissen automatisch eine csv-Datei generieren.
Übung 11: Alternative Implementierung
An sich ist das Vorgehen hier noch suboptimal. Das Einsortieren während dem Schreiben dauert sehr lange, weil nur linear gesucht wird. Günstiger wäre es, zunächst gar nicht zu sortieren und das auf den Zeitpunkt zu verschieben, an dem die Hashtable generiert wird. Der Witz: Bei der Einsortierung von Element i ist die Hashtable schon bis Schritt i-1 fertig - und daher kann binär nach der richtigen Position gesucht werden. Eine schnelle Sortierung mit Quicksort dauert N x ln(N) Schritte. Schreiben Sie die Hash-Routinen daher um: _insert() und _push() können exakt genauso benutzt werden und funktionieren wie bei omalist und omahash_genhash() sortiert die hashtable mit einem schnellen Verfahren.
Dieses Verfahren hat übrigens auch einen Nachteil: Die Rechenzeit wird ungleichmässiger verteilt. Bei N=100.000 wird das ohnehin langsame erste Lesen mit Hashtable-Generierung nochmals um einen Faktor 10 verlängert. Dafür geht das Schreiben sehr fix.
Übung 12: Optimierung der alternativen Implementierung
Optimieren Sie die Übung11-Implementierung, indem Sie in jedem Element ein Flag verwalten, das anzeigt, ob es schon in die Hashtable einsortiert ist oder nicht. Beschränken Sie dann bei omahash_genhash() die Einsortierung auf die Elemente, die noch nicht einsortiert wurden.
Die können Sie sich hier runterladen. Achtung! Sie ist noch für FBC 0.15, bei Benutzung von FBC 0.16 aufwärts muss die Besetzung der Konstanten TRUE und FALSE angepasst werden!