Tableaux associatifs - table de hachage

Partagez votre expérience de PureBasic avec les autres utilisateurs.
Ollivier
Messages : 4197
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Tableaux associatifs - table de hachage

Message par Ollivier »

La technologie ayant évolué au niveau de la mémoire, nous sommes assurés qu'allouer "à l'aise" 64MB de mémoire vive sous XP/Linux et 128MB sous Vista est possible et "conventionnel" (pas de plantage ou d'utilisation de la mémoire virtuelle sur disque).

Cette taille mémoire correspond à un accès mémoire de 16 millions d'entrées avec 32 ou 64 bits par entrée. Chaque entrée est un pointeur ou un entier nul si une entrée est libre.

Il ne reste plus qu'à obtenir un code 24 bits correspondant au contenu d'une chaîne pour accéder, déclarer, vérifier ou supprimer la déclaration d'une chaîne.

Il existe nombre d'algos à cet effet. Nativement, il y a MD5 et Crc32 qu'il faut remanier à 24 (MD5 étant à 128bits et Crc32 à 32 bits).

Je me suis dit qu'il était bien urbain de tester un algo efficace et plus rapide que ces derniers.

Il est sur le forum anglais aussi, comme ça on fait partager tout le monde (ils sont très stoïques vu le manque de schématique et l'absence apparente de besoin! Mais il y aura bien un illuminé qui joindra les deux bouts entre la subtilité technique et l'utilitaire).

Ce n'est pas parfait.

Mais au moins, ça débroussaille le chemin vers l'utilisation des tables associatives!

Pour donner une syntaxe parlante, on pourrait dire ça:

PeekS(PeekL(CamX + MD24("Chaine d'exemple") ) ) = "Chaine d'exemple"


Code : Tout sélectionner

Procedure.L MD24(St.S)

   Protected Length.I
   Protected Result.L
   Protected Stamp.I
   Protected Dest.I

   Length = Len(St)
   St + "    " ; Allocate 4 bytes
   *Adr = @St
   PokeL(*Adr + Length, 0) ; reset these 4 bytes

   Dest = *Adr + Length - 1
   
   For I = *Adr To Dest Step 4
      Result ! PeekL(I)
   Next I

; last operation   
   Stamp = Result & $FF000000
   Stamp >> 8
   Result ! Stamp
   Stamp >> 8
   Result ! Stamp
   Stamp >> 8
   Result ! Stamp
   Result & $FFFFFF
   ProcedureReturn Result

EndProcedure

Structure CamX ; Structure d'une table d'association
   *Ptr[1 << 24]
EndStructure

   CamX.CamX
erix14
Messages : 480
Inscription : sam. 27/mars/2004 16:44
Contact :

Message par erix14 »

Une autre méthode plus abordable pour les débutants :

Code : Tout sélectionner

Structure TableAssociation
	Key1.S
	Key2.S
	StructureUnion
		ValueL.l
		ValueS.S
	EndStructureUnion
EndStructure
Global NewList MonTab.TableAssociation()
Procedure SetValueL(Key1.S, Key2.S, Value.l)
	AddElement(MonTab())
	MonTab()\Key1 = Key1
	MonTab()\Key2 = Key2
	MonTab()\ValueL = Value
EndProcedure
Procedure SetValueS(Key1.S, Key2.S, Value.S)
	AddElement(MonTab())
	MonTab()\Key1 = Key1
	MonTab()\Key2 = Key2
	MonTab()\ValueS = Value
EndProcedure
Procedure GetValueL(Key1.S, Key2.S)
	ForEach MonTab()
		If MonTab()\Key1 = Key1 And MonTab()\Key2 = Key2
			ProcedureReturn MonTab()\ValueL
		EndIf
	Next
EndProcedure
Procedure.S GetValueS(Key1.S, Key2.S)
	ForEach MonTab()
		If MonTab()\Key1 = Key1 And MonTab()\Key2 = Key2
			ProcedureReturn MonTab()\ValueS
		EndIf
	Next
EndProcedure

For t=1 To 10
	SetValueS("Personne "+Str(t), "Nom", Chr(Random(25)+65)+Chr(Random(25)+97)+Chr(Random(25)+97)+Chr(Random(25)+97))
	SetValueL("Personne "+Str(t), "Age", Random(90)+10)
Next

Debug GetValueS("Personne 3", "Nom") + " " + Str(GetValueL("Personne 3", "Age")) + " ans"
Debug GetValueS("Personne 6", "Nom") + " " + Str(GetValueL("Personne 6", "Age")) + " ans"
Ollivier
Messages : 4197
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: Tableaux associatifs - table de hachage

Message par Ollivier »

C'est devenu nativement si simple maintenant...

C'est un peu tard mais je te remercie pour ton intervention bien plus pédagogique que la mienne.

Ollivier
Répondre