Manipulation de chaines de plus de 64K et une fonction FindLongString étudiée. Le seul manque qu'il reste au FindLongString ici décrit est le dernier paramètre proposé dans FindString standard de PureBasic, qui permet de démarrer la recherche à une position différente du début de chaine.
A noter un truc intéressant, dans le source, une façon d'utiliser la fonction à partir d'une chaine pure, et une autre façon de charger une chaine longue à partir d'un fichier. Ce qui veut dire que de telles fonctions pourraient être généralisées pour traiter indifférement des chaines et des fichiers.
... et on oublie pas de fermer le débogueur pour avoir les tests de performances avec les vrais résultats.
Code : Tout sélectionner
;
; Chaines longues et analyse de chaines.
;
; F.Weil 20040521
;
; Petit tut pour le traitement de chaines longues (>64K). Purebasic autorise de créer des chaines longues, en modifiant la valeur d'allocation mémoire
; par des instructions assembleur.
;
; Toutefois il n'est alors plus possible d'utiliser le jeu de commandes de la familles des chaines pour analyser une chaine longue, car ces commandes
; sont écrites pour traiter des chaines d'une longueur maximale de 64K.
;
; Le présent source montre la manière de modifier l'allocation de longueur de chaine, de remettre cette valeur à la valeur par défaut, puis propose
; d'étudier une fonction équivalente à FindString() mais capable d'analyser des chaines longues.
;
; A des fins pédagogiques, une première fonction FindString est proposée, puis différentes versions d'optimisation sont listées.
;
; L'un des problèmes posés est particulièrement le fait que le traitement de chaines le plus optimisé ne peut se faire bien
; qu'en descendant au niveau assembleur. Ici nous n'aborderons pas ce niveau, mais nous resterons dans une écriture PureBasic.
;
; Toutefois nous allons manipuler les chaines dans des tableaux d'octets pour utiliser ce que nous avons déjà vu précédement, et avoir
; des temps de réponse assez courts.
;
Structure StringBytes
Bytes.b[$1000000]
EndStructure
;
; Ici on utilise un boucle pour scanner les caractères et vérifier pour chaque position pointée si la sous-chaine de longueur égale à la sous-chaine cherchée
; est égale à celle-ci.
;
; La comparaison se fait, pour commencer par quelque chose de simple, en appelant la sous-chaine avec un PekkS(), ce qui n'est pas optimum mais
; cela permet déjà d'étudier la question.
;
; A la première occurence de deux sous-chaines égales, on peut soritr de la procédure avec la valeur courante du ponteur comme valeur retour.
;
; Si à la fin du scan on a rien trouvé, on retourne 0
;
Procedure FindLongString(*String.StringBytes, LenString.l, *StringToFind.StringBytes, LengthStringToFind.l)
For i = 0 To LenString - LengthStringToFind + 1
If *String\Bytes[i] = *StringToFind\Bytes[0]
If PeekS(*String + i, LengthStringToFind) = PeekS(*StringToFind, LengthStringToFind)
ProcedureReturn i + 1
EndIf
EndIf
Next
ProcedureReturn 0
EndProcedure
;
; Cette deuxième version permet l'évitement d'un coûteux PeekS en gérant deux boucles imbriquées.
; Une fois trouvé un premier caractère correspondant entre la chaine et la sous-chaine, on vérifie chaque caractère suivant pour retenir
; l'index si la totalité des caractères correspondent. Si c'est le cas on sort de la procédure en retournant la valeur de l'index.
; Si ce n'est pas le cas on incrémente l'index.
;
Procedure FindLongString1(*String.StringBytes, LenString.l, *StringToFind.StringBytes, LengthStringToFind.l)
For i = 0 To LenString - LengthStringToFind + 1
For j = 0 To LengthStringToFind - 1
If *String\Bytes[i + j] <> *StringToFind\Bytes[j]
Break
EndIf
If j = LengthStringToFind - 1
ProcedureReturn i + 1
EndIf
Next
Next
ProcedureReturn 0
EndProcedure
;
; Pour gagner encore un peu de temps, il faut casser le principe des boucles For / Next pour passer à des boucles While / Wend.
; De cette manière on va pouvoir gérer les pointeurs au plus près.
;
Procedure FindLongString2(*String.StringBytes, LenString.l, *StringToFind.StringBytes, LengthStringToFind.l)
i = 0
While i < LenString - LengthStringToFind + 1
If *String\Bytes[i] = *StringToFind\Bytes[0]
j =0
While j < LengthStringToFind - 1
j + 1
If *String\Bytes[i + j] <> *StringToFind\Bytes[j]
Break
EndIf
Wend
If j = LengthStringToFind - 1
ProcedureReturn i + 1
EndIf
EndIf
i + 1
Wend
ProcedureReturn 0
EndProcedure
;
; Et oui celle-là pour demain ou plus tard !
;
; Procedure ReplaceLongString(*String.StringBytes, *StringToFind.StringBytes, *StringToReplace.StringBytes)
;
; EndProcedure
Procedure ManipulationBufferSize(Bytes)
PBStringBase.l = 0
PBMemoryBase.l = 0
!MOV Eax, dword [PB_StringBase]
!MOV [Esp+4],Eax
!MOV Eax, dword [PB_MemoryBase]
!MOV [Esp+8],Eax
HeapReAlloc_(PBMemoryBase, #GMEM_ZEROINIT, PBStringBase, Bytes)
!MOV dword [PB_StringBase],Eax
Debug "ManipulationBufferSize : max length of string set to : " + Str(Bytes)
ProcedureReturn Bytes
EndProcedure
;
;
;
OpenConsole()
Count.l = 1000000
;
; Utilisation sur des chaines normales
;
Chaine.s = "Voyez le brick géant que j'examine près du wharf"
Cherche.s = "brick"
tz = ElapsedMilliseconds() : For i = 1 To Count : iu = FindString(Chaine, Cherche, 1) : Next : PrintN(Str(ElapsedMilliseconds() - tz) + " " + Str(iu))
tz = ElapsedMilliseconds() : For i = 1 To Count : iu = FindLongString(@Chaine, Len(Chaine), @Cherche, Len(Cherche)) : Next : PrintN(Str(ElapsedMilliseconds() - tz) + " " + Str(iu))
tz = ElapsedMilliseconds() : For i = 1 To Count : iu = FindLongString1(@Chaine, Len(Chaine), @Cherche, Len(Cherche)) : Next : PrintN(Str(ElapsedMilliseconds() - tz) + " " + Str(iu))
tz = ElapsedMilliseconds() : For i = 1 To Count : iu = FindLongString2(@Chaine, Len(Chaine), @Cherche, Len(Cherche)) : Next : PrintN(Str(ElapsedMilliseconds() - tz) + " " + Str(iu))
;
; Création d'un buffer long et chargement d'un fichier en conséquence
;
LongStringLength.l = $1000000 ; 16 MO
ManipulationBufferSize(LongStringLength)
;
; Là chez moi j'ai la bible complète qui fait un peu moins de 5MO.
;
If ReadFile(0, "C:\Recup\Frw\Bible\BibleJNDdoc-Bible.txt")
LengthOfFile = Lof()
Buffer = AllocateMemory(LengthOfFile)
ReadData(Buffer, LengthOfFile)
CloseFile(0)
EndIf
ManipulationBufferSize($10000)
Cherche.s = "oméga"
;
; Lancement de la recherche d'un sous-chaine (celle-ci n'aparaît qu'à la fin du fichier)
;
Count.l = 10
tz = ElapsedMilliseconds() : For i = 1 To Count
iu = FindLongString2(Buffer, LengthOfFile, @Cherche, Len(Cherche))
Next : PrintN(Str(ElapsedMilliseconds() - tz) + " " + Str(iu))
PrintN("Trouvé " + Mid(PeekS(Buffer + iu - 1, Len(Cherche)), 1, Len(Cherche)) + " = " + Cherche + " à la position " + Str(iu))
Cherche.s = "Bible"
;
; Celle là au début
;
tz = ElapsedMilliseconds() : For i = 1 To Count
iu = FindLongString2(Buffer, LengthOfFile, @Cherche, Len(Cherche))
Next : PrintN(Str(ElapsedMilliseconds() - tz) + " " + Str(iu))
PrintN("Trouvé " + Mid(PeekS(Buffer + iu - 1, Len(Cherche)), 1, Len(Cherche)) + " = " + Cherche + " à la position " + Str(iu))
While Inkey() = "" : Wend
CloseConsole()
End
