@Alves:
Eine Hashtabelle verwendet man, um z.B. Strings in einer großen Liste von
Strings wieder zu finden, ohne umständlich die ganze Liste durchzugehen,
indem man Hashfunktionen wie CRC32 oder MD5 verwendet und geschickt
eine Baumstruktur oder ähnliches bastelt.
@all:
Hier mal ein Speedvergleich. Beim Starten öffnet sich ein PathRequester().
Dann sollte man ein möglichst großes Verzeichnis auswählen. Das wird
dann dreimal rekursiv durchlaufen. Das erste Mal ist nur, weil das erste
Einlesen eines Verzeichnis oft am längsten dauert, ab dem zweiten Mal
geht es dann schneller.
Beim zweiten Durchlauf werden dann alle Dateinamen in die Hashtabelle
geschrieben, solange sie nicht schon vorhanden sind. Und das ist der auch
der springende Punkt, wo es auf die Geschwindigkeit ankommt. Beim
dritten Einlesen werden nämlich alle Dateinamen in eine LinkedList
geschrieben und vorher wird sie immer komplett durchgegangen um zu
schauen, ob die Datei nicht schon existiert.
Nach dem Hinzufügen der Dateien meldet sich ein MessageRequester(),
das die Zeit zum Einfügen angibt, die Dateien, die momentan in der Liste
sind und die Anzahl der Dateien, die gerade eingelesen wurden.
Aber testet einfach mal selbst:
Code: Alles auswählen
Global NewList HTList.s(), *HT.HT
Global NewList List.s()
Procedure HTFileCallback(Path.s, File.s)
Protected *s.String, Add.l
Add = #True
Path = Path + File
*s = *HT\GetS(Path)
While *s
If *s\s = Path : Add = #False : Break : EndIf
*s = *HT\GetNext()
Wend
If Add
If AddElement(HTList())
HTList() = Path
EndIf
*s = AllocateMemory(SizeOf(String))
*s\s = Path
*HT\AddS(Path, *s)
EndIf
EndProcedure
Procedure FileCallback(Path.s, File.s)
Protected Add.l
Path = Path + File
Add = #True
ForEach List()
If List() = Path : Add = #False : Break : EndIf
Next
If Add
If AddElement(List())
List() = Path
EndIf
EndIf
EndProcedure
Procedure Recursive(Path.s, *procFile)
Protected Name.s, Count.l
Static NewList Dir.l()
If Right(Path, 1) <> "\" : Path + "\" : EndIf
LastElement(Dir())
If AddElement(Dir())
Dir() = ExamineDirectory(#PB_Any, Path, "")
If Dir()
While NextDirectoryEntry(Dir())
Name = DirectoryEntryName(Dir())
If DirectoryEntryType(Dir()) = #PB_DirectoryEntry_Directory
If Name <> "." And Name <> ".."
Count + Recursive(Path + Name + "\", *procFile)
EndIf
Else
Count + 1
If *procFile : CallFunctionFast(*procFile, Path, Name) : EndIf
EndIf
Wend
LastElement(Dir())
FinishDirectory(Dir())
DeleteElement(Dir())
LastElement(Dir())
EndIf
EndIf
ProcedureReturn Count
EndProcedure
Define Path.s, time1.l, time2.l, files1.l, files2.l
*HT = HT_Create()
If *HT = 0 : End : EndIf
*HT\SetMaxTreeSize(5)
Repeat
Path.s = PathRequester("Pfad auswählen...", "c:\")
If Path
Recursive(Path, 0) ;weil der erste Durchlauf immer länger braucht als der zweite
time1 = ElapsedMilliseconds()
files1 = Recursive(Path, @HTFileCallback())
time1 = ElapsedMilliseconds() - time1
time2 = ElapsedMilliseconds()
files2 = Recursive(Path, @FileCallback())
time2 = ElapsedMilliseconds() - time2
MessageRequester("Zeiten", "(Dateien in Liste) [Dateien im Verzeichnis]" + Chr(13) + "Mit Hashtable: " + Str(time1) + " ms (" + Str(CountList(HTList())) + ") [" + Str(files1) + "]" + Chr(13) + "Ohne Hashtable: " + Str(time2) + " ms (" + Str(CountList(List())) + ") [" + Str(files2) + "]")
EndIf
Until Path = ""
Noch etwas allgemeines zu meiner Hashtabelle. Die Zugriffszeiten sind
sehr wahrscheinlich unterschiedlich bei den versch. Hashverfahren.
Hier mal die zwei Beispiele CRC32 und MD5 und ihre maximale Weglänge
bis zum passenden Hash:
CRC32: 4 Bytes, jedes Byte hat 256 Zustände
MD5: 32 Bytes, jedes Byte hat 16 Zustände
Extremfälle:
CRC32: 4 * 256 + x = 1024 + x Einträge müssen durchlaufen werden zum Finden des passenden Hashes
MD5: 32 * 16 + x = 512 + x Einträge müssen durchlaufen werden zum Finden des passenden Hashes
x steht für die geringe Wahrscheinlichkeit, dass zwei oder mehr Einträge
den gleichen Hash haben und dementsprechend nebeneinander stehen.
Selbst wenn in der Tabelle 1.000.000 Strings liegen, bräuchte man mit
MD5 nur maximal 512 Schritte um ihn wiederzufinden. Durchschnittlich
liegt die Anzahl der Schritte aber ca. bei 256, also der Hälfte, was logisch
erscheint.
Vielleicht hat das dem ein oder anderen ja geholfen und er weiß jetzt, was
eine Hashtabelle ist.
