Amélioration de la fonction Pos()

Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
- - Dernière réponse : piette
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
- 15 sept. 2015 à 20:04
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/101045-amelioration-de-la-fonction-pos

Afficher la suite 
Rekin85
Messages postés
25
Date d'inscription
dimanche 11 décembre 2011
Statut
Membre
Dernière intervention
17 octobre 2015
-
Content que mon petit tuto sur l'Asm avec Delphi t'ai incité à produire du code performant...
piette
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
> Rekin85
Messages postés
25
Date d'inscription
dimanche 11 décembre 2011
Statut
Membre
Dernière intervention
17 octobre 2015
-
Je tiens a te remercier pour ce tuto bien plus 'performant' que mon code.
Salutations
Bonjour,

J'ai testé ton code qui marche à merveille.
Mais comme je suis nul en ASM je me permets de poser une question à propos de sa vitesse d'exécution :
Quel est le type d'algo à la base du code ? Car dans le cas où il s'agirait d'un algo basique qui compare TOUS les caractères de la SubString à ceux du texte-cible dans TOUTES les positions successives de la SubString il serait possible d'augmenter notablement la vitesse d'exécution en utilisant un algo à la façon Boyer-Moore qui se contente de ne comparer que le Dernier de la SubString à celui du texte-cible et qui avance d'un pas égal à la longueur de la SubString en cas de différence et qui ne compare les autres caractères de la SubString qu'en cas d'égalité avec le dernier caractère de la SubString. En bref, la vitesse d'exécution d'un algo Boyer-Moore augmente en fonction de la longueur de la SubString et de la longueur des zones du texte où cette SubString est absente, tandis qu'un algo basique pédale dans la choucroute à effectuer un nombre considérable de comparaisons inutiles.

A toutes fins utiles, voici une version PChar de StrPos de l'algo Boyer-Moore :

function BMHStrPos(const pTex, pMot: PChar): PChar;
// StrPos à la façon Boyer-Moore-Horspool
var
it, im: Integer; // Indexes sur Texte et Mot
LC, LM: Integer; // Longueur de pTex
iav: Integer; // Indexe d'avancement
pit, pim: PAnsiChar; // Indexes PChar
ok: boolean;
begin
Result := nil; LC := Length(pTex); LM := Length(pMot);
iav := LM;
while iav <= LC do begin
it := iav; im := LM; ok := true;
while ok do begin
pit := pTex + it - 1;
pim := pMot + im - 1;
if pit^ = pim^ then begin
dec(im); dec(it);
end else ok := false;
if im = 0 then begin RESULT := pit; EXIT; end;
end; // while ok ...
inc(iav, LM - im + 1);
end; // while iav <= LC
end;

Je pense qu'en ASM cela devrait donc être plus rapide qu'en PChar.

Cordialement, et A+.
> cs_pseudo3 -
Salut Gilbert
"Je pense qu'en ASM cela devrait donc être plus rapide qu'en PChar."

C'est pas certain; car cette façon de traiter est proche du raisonnement de l'ASM.
> Rekin85 -
Bonjour René,

Tu dis "C'est pas certain; car cette façon de traiter est proche du raisonnement de l'ASM" : le problème c'est que tant qu'on n'a pas essayé on reste dans l'incertitude.

Par contre, si le code de Piette est une traduction ASM de l'algo basique, il est certain qu'une traduction ASM de l'algo Boyer-Morre sera plus rapide que la version ASM de l'algo basique, je pense qu'on est d'accord sur ce point, car il avance à grands pas dans les textes où la SubString est absente.

Cordialement, et à +.