PureBasic

Forums PureBasic - Français
http://forums.purebasic.com/french/

Map et concaténation de strings

http://forums.purebasic.com/french/viewtopic.php?t=16426

Page 1 sur 1

Map et concaténation de strings

Publié : lun. 02/janv./2017 20:23
par Fig

Code : Tout sélectionner

NewMap Test.i(100000)

timer1=ElapsedMilliseconds()
For i=0 To 100
  For j=0 To 1000
    Test(Str(i)+"/"+Str(j))=255
  Next j 
Next i
timer1=ElapsedMilliseconds()-timer1

timer2=ElapsedMilliseconds()
For i=0 To 100
  For j=0 To 1000
    Test(Str(1000))=255
  Next j 
Next i
timer2=ElapsedMilliseconds()-timer2

timer3=ElapsedMilliseconds()
key.s="key"
For i=0 To 100
  For j=0 To 1000
    Test(key)=255
  Next j 
Next i
timer3=ElapsedMilliseconds()-timer3

MessageRequester("Vitesse","concatanation i/j "+Str(timer1)+" ms"+Chr(13)+"str(number) "+Str(timer2)+" ms"+Chr(13)+"string variable "+Str(timer3)+" ms")
Ordre d'idée:
concatenation : 20ms
str(number) : 4ms
string variable : 2ms

Quelqu'un a t'il une astuce (rapide) pour utiliser un nombre comme clé de map ? (deux nombres, en fait, des coordonnées)
J'ai écrit une hashtable moi-même mais la vitesse n'est pas au rendez vous (autour de 8ms) et j'ai la flemme d'optimiser en assembleur surtout que ça exsite déja en pb...
Toute idée est la bienvenue. :wink:

Re: Map et concaténation de strings

Publié : lun. 02/janv./2017 22:45
par falsam
Fig a écrit :Quelqu'un a t'il une astuce (rapide) pour utiliser un nombre comme clé de map ? (deux nombres, en fait, des coordonnées)
J'aurais une clé formatée de cette maniére latitude|longitude

Code : Tout sélectionner

Define NewMap dummy()

dummy("10|1") = 3
dummy("11|20") = 5

Debug dummy("10|1")

Re: Map et concaténation de strings

Publié : mar. 03/janv./2017 1:48
par Fig
Salut Falsam... Oui c'est ce que j'ai fait dans le code au dessus.

Code : Tout sélectionner

Test(Str(i)+"/"+Str(j))=255
L'ennui, disais-je, c'est que la concaténation est extremement lente, au point que c'est ce qui prend le plus de temps dans ma boucle de pathfinding, un comble !!

Bon j'ai réécrit une implémentation de Map, faute de mieux...
Mais c'est bien dommage que Fred ne nous permette pas d'utiliser des nombres comme des strings pour la clé des Map. :?
J'espere que ca va changer car c'est vraiment une broutille et ca peut être très utile !

Re: Map et concaténation de strings

Publié : sam. 07/janv./2017 19:40
par Ollivier
Un appel de personnalisation possible serait pratique :

Code : Tout sélectionner

NewMap MyKey.MYKEY(@MyId(), *Arg)
C'est le choix du zéro terminal qui rend la tâche d'optimisation ardue en natif.

Re: Map et concaténation de strings

Publié : dim. 08/janv./2017 8:35
par Fred
Ton test est biaisé car le 3e cas insère toujours la même clef ("key") donc la map ne grossit pas et c'est normal que ce soit bien plus rapide. Le 2e cas insere une clef plus petite ("1000" au lieu de "100/1000") donc c'est aussi plus rapide. La concatenation n'est pas si lente que ca au final :)

Re: Map et concaténation de strings

Publié : mer. 11/janv./2017 18:08
par Fig
Effectivement.

Bon, pas grave j'ai tout refait et c'est plus rapide comme ça, c'était un bon exercice.
Je vais essayer de l'améliorer encore avec un stockage cache-friendly...

Re: Map et concaténation de strings

Publié : mer. 11/janv./2017 22:36
par falsam
Ptite question de noob : Pourquoi pas un tableau à deux dimensions ?

Re: Map et concaténation de strings

Publié : jeu. 12/janv./2017 7:43
par Fig
En prenant une architecture 32bits (4 octets par valeurs).

Un array de 1000x1000 c'est 1 000 000 x4 = 4 000 000 d'octets.
Pour un pathfinding tu vas explorer en moyenne (en fonction de la complexité du trajet) 4000 noeuds (admettons).
ça fait 4000x4 = 16 000 octets.

Ca fait un gros gâchis de mémoire vive mais ça serait acceptable si je n'utilisais qu'une seule carte.
Chaque agent utilise une carte personnelle pour sauvegarder ses pathfinding précédents (c'est un pathfinding coopératif en voila la raison)
Donc mettons que tu as 512 agents en tout ça fait (4 000 000- 16 000) x 512 = de mémoire gâchée en moyenne. (c'est juste pas possible que ça tienne en mémoire vive je pense)

A contrario, une hashtable prend à vide n slots (mettons qu'on la fixe à 2000).
En comptant sa structure de 3 "mots" (valeur fixe, mais arbitraire pour la démonstration) par éléments, on va dire 2000 x 4 x 3 = 24 000 octets.
On utilise X,Y comme clés, la table s'agrandit ou se rétrécit en fonction du nombre de nœuds nécessaire: Peu de gaspillage du coup.

Re: Map et concaténation de strings

Publié : ven. 13/janv./2017 16:04
par falsam
J'ai essayé de voir ce que ça donnait avec une base de donnée SQLite en mémoire : C'est plus lent à la création. Je poste quand même le code

Code : Tout sélectionner

EnableExplicit

Enumeration
  #Database  
EndEnumeration

Define.s ReqSql
Define.i key0, key1, timer0, value

;- Création de la base de données en mémoire
UseSQLiteDatabase()
OpenDatabase(#DataBase, ":memory:", "", "")

;Creation de la table de test
ReqSql = "CREATE TABLE something ("
ReqSql + "column1 INTEGER NOT NULL,"   
ReqSql + "column2 INTEGER NOT NULL," 
ReqSql + "column3 TEXT"
ReqSql + ");"
DatabaseUpdate(#DataBase, ReqSql)   
Debug DatabaseError()

;Insertion de 100 000 enregistrements
timer0 = ElapsedMilliseconds()
For key0 = 0 To 100
  For key1 = 0 To 1000
    value + 1
    ReqSql = "INSERT INTO something VALUES('" + key0 + "','" + key1 + "', 'value" + Value +"')"   
    DatabaseUpdate(#Database, ReqSql)
  Next
Next
timer0 = ElapsedMilliseconds() - timer0
Debug "Durée : " + timer0

;Recherche de la clé 80 26
ReqSql = "SELECT * FROM something WHERE column1 = 80 and column2 = 26" 
DatabaseQuery(#Database, ReqSql)
Debug DatabaseError()

While NextDatabaseRow(#Database)            
  Debug GetDatabaseString(#Database, 0) + " " + GetDatabaseString(#Database, 1) + " " + GetDatabaseString(#Database, 2) + " " + GetDatabaseString(#Database, 4)  
Wend

Re: Map et concaténation de strings

Publié : dim. 15/janv./2017 13:46
par microdevweb
Voici une manière de faire en utilisant les 32 bits d'un long comme ceci
Les 16 bits de poids fort pour les X
Les 16 bits de poids faibles pour les Y

Code : Tout sélectionner

Global NewMap myList.l()
Procedure.l GetLong(X.w,Y.w)
  ;*************************************************************************
  ; Process:
  ;         Stocke dans un long (32 bits) 2 short (16 bits)
  ; Input :
  ;         X un word sera stocké dans les bits de poids fort
  ;         y un word sera stocké dans les bits de poids faible
  ; Output:
  ;         La valeur du long
  ;************************************************************************
  Protected ValRet.l
  ValRet=Val("%"+RSet(Bin(X,#PB_Long),16,"0")+RSet(Bin(Y,#PB_Long),16,"0"))
  ProcedureReturn ValRet
EndProcedure
Procedure.w GetWord(values.l,Hidht.b=#True)
  ;*************************************************************************
  ; Process:
  ;         Retour un short (16 bits)
  ; Input :
  ;         Values un long 
  ;         Hight --> #true retourne les 16 bits de poids fort
  ;               --> #False retourne les 16 bits de poids faible
  ; Output:
  ;         La valeur du word (16 bits)
  ;************************************************************************
  Protected ValRet.w
  If(Hidht)
    ValRet=values>>16
  Else
    ValRet=values&%00000000000000001111111111111111
  EndIf
  ProcedureReturn ValRet
EndProcedure
; Ajout de quelques valeurs
Define X.w,Y.w
X=512
Y=24
AddMapElement(myList(),Str(GetLong(X,Y)))
myList()=GetLong(X,Y)
X=1024
Y=32
AddMapElement(myList(),Str(GetLong(X,Y)))
myList()=GetLong(X,Y)
X=354
Y=70
AddMapElement(myList(),Str(GetLong(X,Y)))
myList()=GetLong(X,Y)
; Recherche d'une valeur
FindMapElement(myList(),Str(GetLong(1024,32)))
; Affichage de X
Debug "X = "+Str(GetWord(myList()))
; Affichage de Y
Debug "Y = "+Str(GetWord(myList(),#False))

; Recherche d'une valeur
FindMapElement(myList(),Str(GetLong(512,24)))
; Affichage de X
Debug "X = "+Str(GetWord(myList()))
; Affichage de Y
Debug "Y = "+Str(GetWord(myList(),#False))

Re: Map et concaténation de strings

Publié : mar. 17/janv./2017 8:38
par Fig
Merci Microdev.
Merci Falsam d'avoir eu la curiosité de regarder, j'aurais dit que c'était plus lent que ça en fait.

Sinon voila la vitesse que j'obtiens maintenant avec une table à clusters. (si je n'ai pas fait d'erreur...)
Dites moi ce que ça donne chez vous.
Image

Dll librairie hashtable

Code : Tout sélectionner

Structure hash
  Val1.i
  Val2.i
  Val3.i
  Val4.i
  Val5.i
  key_unique.i
EndStructure


ProcedureDLL SuperiorPower2(number.i)
  !MOV ebx,[p.v_number]
  !BSR ecx,ebx
  !MOV eax,1
  !SAL eax,cl
  !cmp eax,ebx
  !Je _suite
  !SAL eax,1
  !_suite:
  ProcedureReturn
EndProcedure


;0 à c1max-1 cad pour c1max=10 0-9
ProcedureDLL createTable2(nbS.i,nbli.i,keym.i)
  *mem=0
  Global nbSlot.i=SuperiorPower2(nbS)
  Global datas.i=SuperiorPower2(SizeOf(hash))
  Global keymax.i=keym
  Global ligne.i=nbli
  Global size_cluster.i=ligne*datas+SizeOf(*mem)+SizeOf(*mem) ;488
  Global key_unique.i
  FreeMemory(AllocateMemory(SizeOf(*mem)))
  ;create memory space for nbslots simple chained lists
  *mem=AllocateMemory(nbSlot*size_cluster)
  ProcedureReturn *mem
EndProcedure

ProcedureDLL insertTable2(*mem,keyX.i,keyY.i,Val1.i,Val2.i,Val3.i,Val4.i,Val5.i,key_unique.i)
 
  !MOV    eax,dword [p.v_keyX] ;1
  !MOV    ebx,dword [p.v_keyY] ;2
  !MUL    dword [v_keymax] ;1x10000
  !Add    eax,ebx ;eax= 10000+2

  !MOV    dword [p.v_key_unique],eax ;clé complete
  ;compression du hash en adresse
  !XOr    edx,edx
  !DIV    dword [v_nbSlot] ;1002 modulo 8 = 2
  !IMUL   edx,dword [v_size_cluster] ;2x 488 = 976
  !ADD    edx,dword [p.p_mem] ;976 + adresse de base
  !MOV    ebp,edx
  !MOV  ebx,dword [p.v_key_unique]
  
  !_Repea2:
  !mov edx,ebp ;on sauve l'adresse de début du cluster dans edx
  !Mov ecx,dword [edx] ;charge le nombre de ligne utilisée
  !Add ebp,8
  !CMP Ecx,0 ;si il y a 0 ligne dans le cluster on insere un element à la place courante
  !JE _suite3
  
  !_Repea3:
  !CMP  ebx,dword [ebp+20] ;compare les 2 clées, insere un element à la place courante, et sort
  !JE _suite5
 
  !Add ebp,dword [v_datas] ;on passe à la ligne suivante 
  !Dec Ecx
  !JNZ _Repea3 
  
  ;on a pas trouvé la clé
  !Mov ecx,dword [edx] ;charge le nombre de ligne utilisée dans le cluster courant
  !MOV eax,dword [v_ligne]
  !CMP ecx,eax ;si cluster est plein on passe au cluster suivant
  !JNE _suite3 ;sinon on ecrit la ligne et on sort
    
  !MOV ebp,dword [edx+4] ;charge l'adresse du cluster suivant
  !JMP _Repea2


  !_suite3:
  ;On ajoute 1 au compteur de ligne du cluster
  !Inc dword [edx]
  !_suite5:
  !MOV EAX,dword [v_ligne]
  !CMP EAX,dword [edx] ;si egale 15, on créé un nouveau cluster
  !JNE _suite4
  
  ;crée un nouveau cluster
  !Push edx
  !PUSH   dword [v_size_cluster]
  !CALL  _PB_AllocateMemory@4
  !pop edx
  !MOV dword [edx+4],eax ;sauve l'adresse du nouveau cluster dans le cluster précédent
  
  !_suite4:
  !lea esi,dword [p.v_Val1]
  !MOV ecx,6
  !lea edi,dword [ebp]
  !REP MOVSD
  
  !mov eax,ebp
  ProcedureReturn
EndProcedure

ProcedureDLL search2(*mem,keyX.i,keyY.i)
  !MOV    eax,dword [p.v_keyX] ;1
  !MOV    ebx,dword [p.v_keyY] ;2
  !MUL    dword [v_keymax] ;1x10000
  !Add    eax,ebx ;eax= 10000+2

  !MOV    esi,eax ;clé complete
  ;compression du hash en adresse
  !XOr    edx,edx
  !DIV    dword [v_nbSlot] ;1002 modulo 8 = 2
  !IMUL   edx,dword [v_size_cluster] ;2x 488 = 976
  !ADD    edx,dword [p.p_mem] ;976 + adresse de base
  !MOV    ebp,edx
  !MOV    ebx,esi ;clé complete
 
  !_Repea4:
  !mov edx,ebp ;on sauve l'adresse de début du cluster dans edx
  !Mov ecx,dword [edx] ;charge le nombre de ligne utilisée
  !Add ebp,8
  !CMP Ecx,0 ;si il y a 0 ligne dans le cluster on sort
  !JE _fin66
  
  !_Repea5:
  !CMP  ebx,dword [ebp+20] ;compare les 2 clées si on la trouve, on sort
  !JE _suite6
 
  !Add ebp,dword [v_datas] ;on passe à la ligne suivante
  !Dec Ecx
  !JNZ _Repea5
  
  ;on a pas trouvé la clé
  !MOV ebp,dword [edx+4] ;charge l'adresse du cluster suivant
  !cmp ebp,0
  !JNE _Repea4
  
  !_fin66:
  !xor eax,eax
  ProcedureReturn
  !_suite6:
  !mov eax,ebp
  ProcedureReturn
EndProcedure

ProcedureDLL delete2(*mem,keyX.i,keyY.i)
  !MOV    eax,dword [p.v_keyX] ;1
  !MOV    ebx,dword [p.v_keyY] ;2
  !MUL    dword [v_keymax] ;1x10000
  !Add    eax,ebx ;eax= 10000+2

  !MOV esi,eax
  ;compression du hash en adresse
  !XOr    edx,edx
  !DIV    dword [v_nbSlot] ;1002 modulo 8 = 2
  !IMUL   edx,dword [v_size_cluster] ;2x 488 = 976
  !ADD    edx,dword [p.p_mem] ;976 + adresse de base
  !MOV    ebp,edx
  !MOV  ebx,esi
  
  !_Repea8:
  !mov edx,ebp ;on sauve l'adresse de début du cluster dans edx
  !Mov ecx,dword [edx] ;charge le nombre de ligne utilisée
  !Add ebp,8
  !CMP Ecx,0 ;si il y a 0 ligne dans le cluster on sort
  !JE _suite7
  
  !_Repea10:
  !CMP  ebx,dword [ebp+20] ;compare les 2 clées si on la trouve, on sort
  !JE _suite8
 
  !Add ebp,dword [v_datas] ;on passe à la ligne suivante
  !Dec Ecx
  !JNZ _Repea10
  
  ;on a pas trouvé la clé
  !MOV ebp,dword [edx+4] ;charge l'adresse du cluster suivant
  !cmp ebp,0
  !JNE _Repea8
  
  !_suite7:
  !xor eax,eax
  ProcedureReturn
  
  !_suite8:
  !MOV ebx,dword [edx+4];charge l'adresse du cluster suivant
  !CMP ebx,0 
  !JE _suite9 ;si le cluster est le dernier
  !mov ecx,edx ;sauve l'ancienne valeur
  !mov edx,dword [edx+4]
  !JMP _suite8 ;passe au suivant
  
  ;dernier cluster
  !_suite9:
  !mov ebx,dword [edx];charge le nombre de ligne
  !cmp ebx,0
  !JNE _suite10
  ;efface le cluster
  !push ecx
  
  !Push edx
  !CALL  _PB_FreeMemory@4
  
  !pop edx
  !MOV dword [edx+4],0 ;met à 0 l'adresse du rochain cluster puisqu'il n'existe plus
  !_suite10:
  
  
  
  !Dec dword [edx] ;nombre de ligne -1
  !Mov eax,dword [edx] ;charge le nombre de ligne utilisée
  !push edx
  !Mul dword [v_datas] ;on multiplie par la longueur de la ligne
  !pop edx
  
  !lea esi,dword [edx+eax+8] ;origine
  !MOV edi,ebp ;destination

  !MOV ecx,6
  !REP MOVSD
  
  
  !Mov eax,ebp
  ProcedureReturn 
EndProcedure

ProcedureDLL displayTable2(*mem)

  Debug " "
  For i=0 To nbslot-1 ;next slot
    *index=i*size_cluster+*mem
    j=0
   Repeat
      Debug "Cluster :"+Str(i)+"+"+Str(j)

    Debug Hex(PeekI(*index))+ " "+Hex(PeekI(*index+4))
    *index1.hash=*index+8
    
    For k=0 To ligne-1
      
      Debug Hex(*index1)+" "+Hex(*index1\Val1)+" "+Hex(*index1\Val2)+" "+Hex(*index1\Val3)+" "+Hex(*index1\Val5)+" "+Hex(*index1\key_unique)
      *index1+datas ;next element

    Next k
    Debug " "
    *index=PeekI(*index+4):j+1
  Until *index=0
  
  Next i


EndProcedure


;  *tab=createtable2(10,15,10)
; For i=1 To 10
;   For j=1 To 10
;     inserttable2(*tab,Random(10),Random(10),1,2,3,4,5,6)
;   Next j
; Next i
; insertTable2(*tab,12,13,10,10,10,10,10,10)
; delete2(*tab,2,3)
;     displayTable2(*tab)
;     *a.hash=search2(*tab,12,13)
;     Debug *a\Val1
Programme de test qui créé 100 000 éléments et les efface ensuite.

Code : Tout sélectionner

Import "librairie hashtable.lib"
  insertTable2(*mem,keyX.i,keyY.i,val1.i,val2.i,val3.i,val4.i,val5.i,key_unique.i)
  createTable2(nbS.i,nbli.i,keym.i)
  search2(*mem,keyX.i,keyY.i)
  delete2(*mem,keyX.i,keyY.i)
EndImport

Structure hash
  Val1.i ;*index+0  ebp+8
  Val2.i ;+4   ebp+12
  Val3.i ;+8   ebp+16
  Val4.i ;+12  ebp+20
  Val5.i   ;+16  ebp+28
  key_unique.i      ;+20  ebp+24
EndStructure

Dim A.i(1000)
Dim B.i(1000)
For i=1 To 1000:A(i)=Random(1000):B(i)=Random(1000):Next i


;********Cluster*********
*tab2=createtable2(1000,15,1000)
timer2=ElapsedMilliseconds()
For i=1 To 100
  For j=1 To 1000
    inserttable2(*tab2,A(i),B(j),1,2,3,4,5,6)
  Next j
Next i
For i=1 To 100
  For j=1 To 1000
    delete2(*tab2,A(i),B(j))
  Next j
Next i
timer2=ElapsedMilliseconds()-timer2

;*********PB maps***********
NewMap tab.hash(1000)
timer3=ElapsedMilliseconds()
For i=1 To 100
  For j=1 To 1000
    AddMapElement(tab(),Str(A(i))+"/"+Str(B(j)))
    tab()\Val1=1
    tab()\Val2=2  
    tab()\Val3=3
    tab()\Val4=4
    tab()\Val5=5
    tab()\key_unique=6
  Next j
Next i
For i=1 To 100
  For j=1 To 1000
DeleteMapElement(tab(),Str(A(i))+"/"+Str(B(j)))
  Next j
Next i
timer3=ElapsedMilliseconds()-timer3

MessageRequester("vitesse","Hashtable cluster : "+Str(timer2)+" ms"+Chr(13)+"PureBasic Map : "+Str(timer3)+" ms")
Fuseau horaire sur UTC+01:00
Page 1 sur 1

Développé par phpBB® Forum Software © phpBB Limited

Traduction française officielle © Qiaeru