Fast Hashtable

cxAlex · Beitrag von **cxAlex** » 08.12.2008 12:23

In diesem Thread habe ich nach einer schnellen Hashtable gesucht:
http://www.purebasic.fr/german/viewtopic.php?t=17659

Da, wie in dem Thread angesprochen, eine Hashtable meist am besten ist, desto spezieller man sie an das jeweilige Einsatztgebiet anpasst, hab ich mir selbst eine gebaut.

Ich habe das ganze auf Speed optimiert, das ist wohl die schnellste Hashtable die je in PB geschrieben worden ist.

Als Basis diente mir dabei diese geniale Hashtable von Inc:
http://www.purebasic-lounge.com/viewtop ... c&start=12

Details:

Die einzelnen Hashtables sind autark, und in der Größe dynamisch.
Die Startblockgröße der Hashtables lässt sich beliebig festelegen, wenn die Table zu 2/3 voll ist (einstellbar) reallociert sie sich von selbst.
Es können Strings und GanzZahlen in der Table gespeichert werden.
Einmal gemachte Einträge können NICHT wieder gelöscht oder geändert werden (im Orginal vorhanden, ich benötige das nicht kostet nur Speed, kann aber leicht wieder eingebaut werden).

Code:

Code: Alles auswählen

; ------------------------------------------------------------------------------------
; Fast Hashtable Include
; Core taken from: http://www.purebasic-lounge.com/viewtopic.php?t=5464&postdays=0&postorder=asc&start=12
; ------------------------------------------------------------------------------------

; ------------------------------------------------------------------------------------
; Structures & Enumerations
; ------------------------------------------------------------------------------------

Enumeration
  #InitialTableSize = 2503
  #CHASHMAP_TYPE_STRING = 1
  #CHASHMAP_TYPE_VALUE
  #CHASHMAP_MAP_OVERFLOW = -1
EndEnumeration

Structure sHASHMAP
  Object.l
  Blocksize.l
  Mapsize.l
  count.l
  *map
EndStructure

Structure sElement
  key.s
  type.l
  used.l
  StructureUnion
    Value.l
    string.s
  EndStructureUnion
EndStructure

Structure MapArray
  map.sElement[0]
EndStructure

; ------------------------------------------------------------------------------------
; Internal
; ------------------------------------------------------------------------------------

Macro Mem_Alloc(_mem)
  AllocateMemory(_mem)
EndMacro

Macro Mem_ReAlloc(_mem, _size)
  ReAllocateMemory(_mem, _size)
EndMacro

Macro Mem_Free(_mem)
  FreeMemory(_mem)
EndMacro

Macro _DoResize(_State, _Maximum)
  _State>(2*_Maximum/3)
EndMacro

Macro _ResizeTo(_current, _blocksize)
  _current + _blocksize
EndMacro

Procedure _CreateHash(*pKey.CHARACTER, Mapsize.l)
  !MOV EAX,5381 ;Startwert hash
  !MOV EBX,EAX ;für erste Addition in Schleife
  !MOV ESI,dword[p.p_pKey] ;oder LEA ESI,[v_pKey], aber wenn p_pKey eh schon da ist...
  !XOR EDX,EDX ;EDX auf Null setzen
  !MOV CL,5 ;sollte so schneller sein
  !@@:
  !MOV DL,[ESI] ;also kein Unicode!
  !OR DL,DL ;Test auf Null
  !JZ @f ;ist Null, Sprung vorwärts
  !SHL EAX,CL ;SHL = SAL; SAL wird selten angegeben
  !ADD EAX,EBX
  !ADD EAX,EDX
  !MOV EBX,EAX ;"alten" hash sichern
  !INC ESI
  !JMP @b ;Sprung rückwärts, nächsten Wert einlesen
  !@@:
  !MOV dword[p.p_pKey],esi ;wirklich Pointer erhöhen? Sonst weg
  !XOR EDX,EDX ;schneller und richtiger (!) als CDQ ich gehe hier mal von vorzeichenlosen Werten aus
  !DIV dword[p.v_Mapsize] ;EAX ist noch hash
  !MOV EAX,EDX ;Divisions-Rest
  ProcedureReturn ;Gibt Hash in EAX zurück
EndProcedure

Procedure _NextPrime(num.l)
  Protected prime.l, i.l, start.l
  num + 1
  Repeat
    i = 2
    While i * i < num
      If num%i = 0 : prime = #False : Break
      Else : prime = #True : EndIf
      i + 1
    Wend
    If prime = #False : num + 1
    Else
    Break : EndIf
  ForEver
  ProcedureReturn num
EndProcedure

Procedure _ReDimHashmap(*object.sHASHMAP)
  Protected NewSize.l = _NextPrime(_ResizeTo(*object\Mapsize, *object\Blocksize))
  Protected *pNewMap.MapArray = Mem_Alloc(NewSize*SizeOf(sElement))
  Protected *p.MapArray = *object\map, i.l, counter.l, r.l, hash.l
  For i = 0 To *object\Mapsize-1
    If *p\map[i]\used = #True
      hash = _CreateHash(@*p\map[i]\key, NewSize)
      counter = 0 : r = 0
      While counter<NewSize


        If *pNewMap\map[hash]\used = #False
          CopyMemory(*p\map[i], *pNewMap\map[hash], SizeOf(sElement))
          Break
        Else
          counter + 1
          hash + ((counter/2)*(counter/2))*(-1 + (r*2))
          hash%NewSize
          If hash<0 : hash + NewSize : EndIf
          r ! 1
        EndIf
      Wend
    EndIf
  Next i
  Mem_Free(*object\map)
  *object\map = *pNewMap
  *object\Mapsize = NewSize
EndProcedure

; ------------------------------------------------------------------------------------
; Public
; ------------------------------------------------------------------------------------

Procedure HT_AddString(*object.sHASHMAP, key.s, string.s)
  Protected hash.l, counter.l, r.l, *p.MapArray
  hash = _CreateHash(@key, *object\Mapsize)
  *p = *object\map
  While counter<*object\Mapsize And Not *object\count = *object\Mapsize
    If *p\map[hash]\used = #False
      *p\map[hash]\key = key
      *p\map[hash]\type = #CHASHMAP_TYPE_STRING
      *p\map[hash]\string = string
      *p\map[hash]\used = #True
      *object\count + 1
      If _DoResize(*object\count, *object\Mapsize)
        _ReDimHashmap(Object)
      EndIf
      ProcedureReturn #True
    Else
      counter + 1
      hash + ((counter/2)*(counter/2))*(-1 + (r*2))
      hash%*object\Mapsize
      If hash<0 : hash + *object\Mapsize : EndIf
      r ! 1
    EndIf
  Wend
  ProcedureReturn #CHASHMAP_MAP_OVERFLOW
EndProcedure

Procedure HT_AddValue(*object.sHASHMAP, key.s, Value.l)
  Protected hash.l, counter.l, r.l, *p.MapArray
  hash = _CreateHash(@key, *object\Mapsize)
  *p = *object\map
  While counter<*object\Mapsize And Not *object\count = *object\Mapsize
    If *p\map[hash]\used = #False
      *p\map[hash]\key = key
      *p\map[hash]\type = #CHASHMAP_TYPE_VALUE
      *p\map[hash]\Value = Value
      *p\map[hash]\used = #True
      *object\count + 1
      If _DoResize(*object\count, *object\Mapsize)
        _ReDimHashmap(Object)
      EndIf
      ProcedureReturn #True
    Else
      counter + 1
      hash + ((counter/2)*(counter/2))*(-1 + (r*2))
      hash%*object\Mapsize
      If hash<0 : hash + *object\Mapsize : EndIf
      r ! 1
    EndIf
  Wend
  ProcedureReturn #CHASHMAP_MAP_OVERFLOW
EndProcedure

Procedure.s HT_GetString(*object.sHASHMAP, key.s)
  Protected ht.l, hash.l, counter.l, r.l, *p.MapArray
  hash = _CreateHash(@key, *object\Mapsize)
  *p = *object\map
  While counter<*object\Mapsize
    If Not *p\map[hash]\used
      ProcedureReturn ""
    ElseIf *p\map[hash]\key = key And *p\map[hash]\type = #CHASHMAP_TYPE_STRING And *p\map[hash]\used = #True
      ProcedureReturn *p\map[hash]\string
    Else; // quadratic probe
      counter + 1
      hash + ((counter/2)*(counter/2))*(-1 + (r*2))
      hash%*object\Mapsize
      If hash<0 : hash + *object\Mapsize : EndIf
      r ! 1 ; // Swap bool
    EndIf
  Wend
  ProcedureReturn ""
EndProcedure

Procedure.l HT_GetValue(*object.sHASHMAP, key.s)
  Protected hash.l, counter.l, r.l, *p.MapArray
  hash = _CreateHash(@key, *object\Mapsize)
  *p = *object\map
  While counter<*object\Mapsize
    If Not *p\map[hash]\used
      ProcedureReturn #False
    ElseIf *p\map[hash]\key = key And *p\map[hash]\type = #CHASHMAP_TYPE_VALUE And *p\map[hash]\used = #True
      ProcedureReturn *p\map[hash]\Value
    Else ; // quadratic probe
      counter + 1
      hash + ((counter/2)*(counter/2))*(-1 + (r*2))
      hash%*object\Mapsize
      If hash<0 : hash + *object\Mapsize : EndIf
      r ! 1 ; // Swap bool
    EndIf
  Wend
EndProcedure

Procedure HT_Exists(*object.sHASHMAP, key.s)
  Protected hash.l, counter.l, r.l, *p.MapArray
  hash = _CreateHash(@key, *object\Mapsize)
  *p = *object\map
  While counter<*object\Mapsize
    If Not *p\map[hash]\used
      ProcedureReturn #False
    ElseIf *p\map[hash]\key = key And *p\map[hash]\used = #True
      ProcedureReturn #True
    Else ; // quadratic probe
      counter + 1
      hash + ((counter/2)*(counter/2))*(-1 + (r*2))
      hash%*object\Mapsize
      If hash<0 : hash + *object\Mapsize : EndIf
      r ! 1 ; // Swap bool
    EndIf
  Wend
EndProcedure

Procedure HT_FreeHashmap(*object.sHASHMAP)
  Protected hash.l, i.l, *ptrStr, *p.MapArray
  *p = *object\map
  For i = 0 To *object\Mapsize-1
    If *p\map[hash]\type = #CHASHMAP_TYPE_STRING
      *ptrStr = @*p\map[hash]\string
      *p\map[hash]\string = ""
      !PUSH dword [p.p_ptrStr]
      !CALL _SYS_FreeString@4
    EndIf
  Next
  Mem_Free(*object\map)
  ProcedureReturn #True
EndProcedure

Procedure HT_New(BlockSize = #InitialTableSize)
  Protected *object.sHASHMAP, i.l, prime.l
  BlockSize = _NextPrime(BlockSize)
  *object = Mem_Alloc(SizeOf(sHASHMAP))
  If *object
    *object\Object = #True
    *object\BlockSize = Blocksize
    *object\Mapsize = Blocksize
    *object\map = Mem_Alloc(Blocksize*SizeOf(sElement))
    ProcedureReturn *object
  EndIf
EndProcedure

Beitrag von **Kiffi** » 08.12.2008 13:10

Danke für den Code!

was ich jetzt auf den ersten Blick vermissen würde, wäre eine Funktion,
mit der man die Anzahl der Elemente ermitteln kann. Sowas, wie
HT_Count().

Und: Mag sein, dass das die schnellste in PB geschriebene HT ist.
Allerdings ist die HT-Lib von edel ein wenig schneller

Testcode cxAlex:

Code: Alles auswählen

z1=ElapsedMilliseconds()

ht = HT_New()

For counter = 0 To 10000
  HT_AddValue(ht, "myKey" + Str(counter), counter)
Next

z2 = ElapsedMilliseconds()

MessageRequester(Str(HT_GetValue(ht,"myKey5000")), Str(z2-z1))

Testcode edel:

Code: Alles auswählen

z1=ElapsedMilliseconds()

ht = HT_New()

For counter = 0 To 10000
  HT_Insert(ht, "myKey" + Str(counter), counter)
Next

z2 = ElapsedMilliseconds()

MessageRequester(Str(HT_Get(ht,"myKey5000")), Str(z2-z1))

Benötigte Zeit:
cxAlex: 2453 ms
edel: 47 ms

Und: HT_GetValue() liefert bei Dir 0, was falsch ist (richtig wäre 5000).

Grüße ... Kiffi

cxAlex · Beitrag von **cxAlex** » 08.12.2008 13:20

Sry, da war ein Fehler beim Redimmen:

Mit Speedtest:

Code: Alles auswählen

; ------------------------------------------------------------------------------------
; Fast Hashtable Include
; Core taken from: http://www.purebasic-lounge.com/viewtopic.php?t=5464&postdays=0&postorder=asc&start=12
; ------------------------------------------------------------------------------------

; ------------------------------------------------------------------------------------
; Structures & Enumerations
; ------------------------------------------------------------------------------------



Enumeration
  #InitialTableSize = 2503
  #CHASHMAP_TYPE_STRING = 1
  #CHASHMAP_TYPE_VALUE
  #CHASHMAP_MAP_OVERFLOW = -1
EndEnumeration

Structure sHASHMAP
  Object.l
  Blocksize.l
  Mapsize.l
  count.l
  *map
EndStructure

Structure sElement
  key.s
  type.l
  used.l
  StructureUnion
    Value.l
    string.s
  EndStructureUnion
EndStructure

Structure MapArray
  map.sElement[0]
EndStructure

; ------------------------------------------------------------------------------------
; Internal
; ------------------------------------------------------------------------------------

Macro Mem_Alloc(_mem)
  AllocateMemory(_mem)
EndMacro

Macro Mem_ReAlloc(_mem, _size)
  ReAllocateMemory(_mem, _size)
EndMacro

Macro Mem_Free(_mem)
  FreeMemory(_mem)
EndMacro

Macro _DoResize(_State, _Maximum)
  _State>(2*_Maximum/3)
EndMacro

Macro _ResizeTo(_current, _blocksize)
  _current + _blocksize
EndMacro

Procedure _CreateHash(*pKey.CHARACTER, Mapsize.l)
  !MOV EAX,5381 ;Startwert hash
  !MOV EBX,EAX ;für erste Addition in Schleife
  !MOV ESI,dword[p.p_pKey] ;oder LEA ESI,[v_pKey], aber wenn p_pKey eh schon da ist...
  !XOR EDX,EDX ;EDX auf Null setzen
  !MOV CL,5 ;sollte so schneller sein
  !@@:
  !MOV DL,[ESI] ;also kein Unicode!
  !OR DL,DL ;Test auf Null
  !JZ @f ;ist Null, Sprung vorwärts
  !SHL EAX,CL ;SHL = SAL; SAL wird selten angegeben
  !ADD EAX,EBX
  !ADD EAX,EDX
  !MOV EBX,EAX ;"alten" hash sichern
  !INC ESI
  !JMP @b ;Sprung rückwärts, nächsten Wert einlesen
  !@@:
  !MOV dword[p.p_pKey],esi ;wirklich Pointer erhöhen? Sonst weg
  !XOR EDX,EDX ;schneller und richtiger (!) als CDQ ich gehe hier mal von vorzeichenlosen Werten aus
  !DIV dword[p.v_Mapsize] ;EAX ist noch hash
  !MOV EAX,EDX ;Divisions-Rest
  ProcedureReturn ;Gibt Hash in EAX zurück
EndProcedure

Procedure _NextPrime(num.l)
  Protected prime.l, i.l, start.l
  num + 1
  Repeat
    i = 2
    While i * i < num
      If num%i = 0 : prime = #False : Break
      Else : prime = #True : EndIf
      i + 1
    Wend
    If prime = #False : num + 1
    Else
    Break : EndIf
  ForEver
  ProcedureReturn num
EndProcedure

Procedure _ReDimHashmap(*object.sHASHMAP)
  Protected NewSize.l = _NextPrime(_ResizeTo(*object\Mapsize, *object\Blocksize))
  Protected *pNewMap.MapArray = Mem_Alloc(NewSize*SizeOf(sElement))
  Protected *p.MapArray = *object\map, i.l, counter.l, r.l, hash.l
  For i = 0 To *object\Mapsize-1
    If *p\map[i]\used = #True
      hash = _CreateHash(@*p\map[i]\key, NewSize)
      counter = 0 : r = 0
      While counter<NewSize
        If *pNewMap\map[hash]\used = #False
          CopyMemory(*p\map[i], *pNewMap\map[hash], SizeOf(sElement))
          Break
        Else
          counter + 1
          hash + ((counter/2)*(counter/2))*(-1 + (r*2))
          hash%NewSize
          If hash<0 : hash + NewSize : EndIf
          r ! 1
        EndIf
      Wend
    EndIf
  Next i
  Mem_Free(*object\map)
  *object\map = *pNewMap
  *object\Mapsize = NewSize
EndProcedure

; ------------------------------------------------------------------------------------
; Public
; ------------------------------------------------------------------------------------

Procedure HT_AddString(*object.sHASHMAP, key.s, string.s)
  Protected hash.l, counter.l, r.l, *p.MapArray
  hash = _CreateHash(@key, *object\Mapsize)
  *p = *object\map
  While counter<*object\Mapsize And Not *object\count = *object\Mapsize
    If *p\map[hash]\used = #False
      *p\map[hash]\key = key
      *p\map[hash]\type = #CHASHMAP_TYPE_STRING
      *p\map[hash]\string = string
      *p\map[hash]\used = #True
      *object\count + 1
      If _DoResize(*object\count, *object\Mapsize)
        _ReDimHashmap(*object)
      EndIf
      ProcedureReturn #True
    Else
      counter + 1
      hash + ((counter/2)*(counter/2))*(-1 + (r*2))
      hash%*object\Mapsize
      If hash<0 : hash + *object\Mapsize : EndIf
      r ! 1
    EndIf
  Wend
  ProcedureReturn #CHASHMAP_MAP_OVERFLOW
EndProcedure

Procedure HT_AddValue(*object.sHASHMAP, key.s, Value.l)
  Protected hash.l, counter.l, r.l, *p.MapArray
  hash = _CreateHash(@key, *object\Mapsize)
  *p = *object\map
  While counter<*object\Mapsize And Not *object\count = *object\Mapsize
    If *p\map[hash]\used = #False
      *p\map[hash]\key = key
      *p\map[hash]\type = #CHASHMAP_TYPE_VALUE
      *p\map[hash]\Value = Value
      *p\map[hash]\used = #True
      *object\count + 1
      If _DoResize(*object\count, *object\Mapsize)
        _ReDimHashmap(*object)
      EndIf
      ProcedureReturn #True
    Else
      counter + 1
      hash + ((counter/2)*(counter/2))*(-1 + (r*2))
      hash%*object\Mapsize
      If hash<0 : hash + *object\Mapsize : EndIf
      r ! 1
    EndIf
  Wend
  ProcedureReturn #CHASHMAP_MAP_OVERFLOW
EndProcedure

Procedure.s HT_GetString(*object.sHASHMAP, key.s)
  Protected ht.l, hash.l, counter.l, r.l, *p.MapArray
  hash = _CreateHash(@key, *object\Mapsize)
  *p = *object\map
  While counter<*object\Mapsize
    If Not *p\map[hash]\used
      ProcedureReturn ""
    ElseIf *p\map[hash]\key = key And *p\map[hash]\type = #CHASHMAP_TYPE_STRING And *p\map[hash]\used = #True
      ProcedureReturn *p\map[hash]\string
    Else; // quadratic probe
      counter + 1
      hash + ((counter/2)*(counter/2))*(-1 + (r*2))
      hash%*object\Mapsize
      If hash<0 : hash + *object\Mapsize : EndIf
      r ! 1 ; // Swap bool
    EndIf
  Wend
  ProcedureReturn ""
EndProcedure

Procedure.l HT_GetValue(*object.sHASHMAP, key.s)
  Protected hash.l, counter.l, r.l, *p.MapArray
  hash = _CreateHash(@key, *object\Mapsize)
  *p = *object\map
  While counter<*object\Mapsize
    If Not *p\map[hash]\used
      ProcedureReturn #False
    ElseIf *p\map[hash]\key = key And *p\map[hash]\type = #CHASHMAP_TYPE_VALUE And *p\map[hash]\used = #True
      ProcedureReturn *p\map[hash]\Value
    Else ; // quadratic probe
      counter + 1
      hash + ((counter/2)*(counter/2))*(-1 + (r*2))
      hash%*object\Mapsize
      If hash<0 : hash + *object\Mapsize : EndIf
      r ! 1 ; // Swap bool
    EndIf
  Wend
EndProcedure

Procedure HT_Exists(*object.sHASHMAP, key.s)
  Protected hash.l, counter.l, r.l, *p.MapArray
  hash = _CreateHash(@key, *object\Mapsize)
  *p = *object\map
  While counter<*object\Mapsize
    If Not *p\map[hash]\used
      ProcedureReturn #False
    ElseIf *p\map[hash]\key = key And *p\map[hash]\used = #True
      ProcedureReturn #True
    Else ; // quadratic probe
      counter + 1
      hash + ((counter/2)*(counter/2))*(-1 + (r*2))
      hash%*object\Mapsize
      If hash<0 : hash + *object\Mapsize : EndIf
      r ! 1 ; // Swap bool
    EndIf
  Wend
EndProcedure

Procedure HT_FreeHashmap(*object.sHASHMAP)
  Protected hash.l, i.l, *ptrStr, *p.MapArray
  *p = *object\map
  For i = 0 To *object\Mapsize-1
    If *p\map[hash]\type = #CHASHMAP_TYPE_STRING
      *ptrStr = @*p\map[hash]\string
      *p\map[hash]\string = ""
      !PUSH dword [p.p_ptrStr]
      !CALL _SYS_FreeString@4
    EndIf
  Next
  Mem_Free(*object\map)
  ProcedureReturn #True
EndProcedure

Procedure HT_New(BlockSize = #InitialTableSize)
  Protected *object.sHASHMAP, i.l, prime.l
  BlockSize = _NextPrime(BlockSize)
  *object = Mem_Alloc(SizeOf(sHASHMAP))
  If *object
    *object\Object = #True
    *object\BlockSize = Blocksize
    *object\Mapsize = Blocksize
    *object\map = Mem_Alloc(Blocksize*SizeOf(sElement))
    ProcedureReturn *object
  EndIf
EndProcedure


DisableDebugger
z1=ElapsedMilliseconds()

ht = HT_New()

For counter = 0 To 10000
  HT_AddValue(ht, "myKey" + Str(counter), counter)
Next

z2 = ElapsedMilliseconds()
EnableDebugger

MessageRequester(Str(HT_GetValue(ht,"myKey5000")), Str(z2-z1))

Bei mir braucht das ganze 79 ms, du musst den Debugger ausschalten damit du das ganze vergleichen kannst weil die Libs aus der Userlib auch nicht debuggt werden!

Beitrag von **Kiffi** » 08.12.2008 13:58

cxAlex hat geschrieben:du musst den Debugger ausschalten damit du das ganze vergleichen kannst weil die Libs aus der Userlib auch nicht debuggt werden!

das ist mir bekannt

Dennoch bekomme ich die Messagebox erst nach 2453ms zu sehen. Und
HT_GetValue(ht,"myKey5000") liefert noch immer den falschen Wert 0
zurück.

Grüße ... Kiffi

// Edit: Ah! I see! In PB4.2 ist Dein Code schnell und der richtige Wert wird
zurückgeliefert. In PB4.3 B5 ist der Code langsam und der falsche Wert wird
zurückgeliefert.

Froggerprogger · Beitrag von **Froggerprogger** » 08.12.2008 14:31

Ich habe das ganze auf Speed optimiert, das ist wohl die schnellste Hashtable die je in PB geschrieben worden ist.

Diese Aussage spornt mich zu ein paar Anmerkungen an, da ich auch vor einiger Zeit mal eine Hashtable-Implementierung geschrieben habe (hier), die wesentlich schneller als diese Implementierung hier ist, aber dafür auch weit restriktiver/spezieller.

Der Begriff 'Hashtable' ist ein Oberbegriff für eine Vielzahl ähnlicher Datenstrukturen mit sehr verschiedenen Implementierungsansätzen. Die Datenstrukturen unterscheiden sich anhand diverser Eigenschaften und sind für diverse Einsatzzwecke jeweils besser/schlechter geeignet als andere. Du implementiert "Hashing mit offener Addressierung und quadratischer Hashfunktion". Hier eine Auflistung einiger solcher konzeptionellen Eigenschaften:

Bestimmte Größe: Die Größe hier muss prim sein (wird ggf. automatisch auf nächste Primzahl erhöht). Nicht bevorzugt werden hier aber Primzahlen, die möglichst weit weg von Zweierpotenzen liegen.

Dynamische Größe: Dynamisches Wachsen bei festem Loadfactor 2/3 ist hier implementiert, nicht aber dynamisches Schrumpfen.

Mapping-Datentypen: Als Keys können ausschließlich Strings verwendet werden (was gerade bei der Starthashgenerierung langsamer ist, als wenn man Integers als Keys verwenden kann/möchte). Als Werte können Strings oder Integer gespeichert werden.

Löschen: Wird nicht unterstützt, ließe sich aber einbauen, z.B. einfach durch einen Wert #Deleted für das Feld \used. Aber bei offener Addressierung entsteht dann das Problem, dass nun die Laufzeit zum Einfügen/Suchen nicht mehr nur vom gegenwärtigen Loadfactor abhängt, sondern auch von den vorausgegangenen Löschvorgängen. Für Löschen eignet sich besser das Hashing mit Listen.

Multiplizität: Hier lassen sich auch zwei verschiedene Keys mit demselben Hashwert speichern. Das ist üblich und praktisch, aber benötigt natürlich zusätzlichen Speicher für den Key.

Hashfunktion: Hier ist Hashen mit quadratischer Funktion implementiert. Der Starthashwert berechnet sich kryptisch aus einigen Assemblerbefehlen, daher ist es mir grad nicht möglich zu analysieren, welche Key-Strings zu Kollisionen führen können.

Unabhängig von diesen Eigenschaften hier noch ein paar Anmerkungen zu der Implementierung selbst:
1. Im Kommentar der _CreateHash-Funktion findet sich irgendwo der Ausspruch "also kein Unicode!". Also wird ein Unicode-Strings nutzendes Programm wohl nicht wie gewünscht funktionieren, sondern ggf. noch schneller Hashes mit Kollisionen erzeugen?
2. In _NextPrime wird num in Einerschritten erhöht, und dann auf Primeigenschaft getestet. Hier könnte man zumindest den Fall, ob die Zahl gerade ist rausnehmen und dann immer um 2 erhöhen. Ebenso könnte man den Teiler i ab dem Wert 3 immer um 2 erhöhen (doppelter Speed!). Auch gibt es für sehr große Zahlen effizientere (aber wesentlich komplexer zu implementierende) Verfahren, als einfach alle Teiler durchzuprobieren.
3. Der Source kompiliert nicht unter Linux, da der Aufruf !CALL _SYS_FreeString@4 einen Assembler Error (undefined symbol) schmeißt.

Diese Anmerkungen sollen zeigen, dass auch diese Implementierung nicht die "eierlegende Wollmilchsau" ist, die es bei Hashtables (leider) auch gar nicht gibt. Aber für den Regelfall scheint dies hier eine gute Implementierung zu sein. In einem einfachen Speedvergleich zu linearer Suche in einem Array lohnt sich dieses Hashen bereits ab Pi mal Daumen ~150-200 Elementen.

cxAlex · Beitrag von **cxAlex** » 08.12.2008 15:17

@Kiffi:

Ich nutze die 4.3 Beta nicht, werd wohl bis zum Final warten,eventuell mal im BugForum posten. Interresant währe es zu wissen wo der Speedverlust entsteht. Wenns in der Final auch noch so langsam ist werd ich mit PX bei 4.2 bleiben, da nutz ich das nämlich.

@Froggerprogger:

Ich hab ja auch gesagt das die HT speziellel für mich zugeschnitten ist, darum sind Sachen wie Dynamisches Schrumpfen/Löschen von Elementen nicht drin, ich brauch nur Strings als Keys und mehr als Longs und Strings muss ich in PX nicht speichern.

Der Hashing - Algo ist übrigens DJB2, Helle hat den für mich in ASM übersetzt.

Ich hab den _NextPrime() Befehl angepasst, müsste jetzt schneller sein:

Code: Alles auswählen

Procedure _NextPrime(num.l)
  Protected prime.l, i.l, start.l
  num + 1
  If Int(zahl/2)*2 = zahl
    num + 1
  EndIf
  Repeat
    i = 2
    While i*i<num
      If num%i = 0 : prime = #False : Break
      Else : prime = #True : EndIf
      If i> = 3
        i + 2
      Else
        i + 1
      EndIf
    Wend
    If prime = #False : num + 2
    Else
    Break : EndIf
  ForEver
  ProcedureReturn num
EndProcedure

Aberd danke für das Feedback!

cxAlex · Beitrag von **cxAlex** » 08.12.2008 19:48

@Kiffi:
http://www.purebasic.fr/english/viewtop ... highlight=

was für ein System benutzt du? Hroudwolf,milan und Freak merk anscheinen gar keinen Unterschied, bei mir braucht der Code mit debugger 60-80 ms und ohne Debugger immer 0 ms, da schwankt nix.

Beitrag von **Kiffi** » 08.12.2008 19:51

cxAlex hat geschrieben:was für ein System benutzt du?

anscheinend ein ziemlich schrottiges

Ich habe das nun hier noch mal
zu Hause getestet und nun funktioniert es auch unter PB4.3 B5 schnell und
fehlerfrei.

Sorry für die unnötige Aufregung!

Grüße ... Kiffi

cxAlex · Beitrag von **cxAlex** » 08.12.2008 19:54

Jeder macht Fehler. Ist auch ein Hobby von mir

edel · Beitrag von **edel** » 08.12.2008 22:41

Hm, egal welche Version ich nehme, es ist ueberall sehr langsam.

AMD Phenom(tm) 9550 Quad-Core Processor (4 CPUs), ~2.2GHz / Vista 64

Wie sieht das denn aus wenn man mal "ein wenig mehr" als 10000 Strings
einfuegt, muss man da was umstellen?

PureBoard

Fast Hashtable

Fast Hashtable

Re: Fast Hashtable