Solution + rapide pour autoriser seulem ent certains caracteres

memset(isCharacterValid, 0, sizeof(isCharacterValid));
for (p = s1; p < s1_end; p++)
isCharacterValid[*p] = true;

[...]

Quitte à économiser des bouts de chandelle, il faudrait voir si ce code
est vraiment plus efficace dans la majorité des cas utilisés. J'imagine
que le plus souvent la chaîne s1 doit être assez petite, or ton memset
effectue une boucle avec 256 écritures en mémoire et 256 tests de fin
de boucle : cela peut être plus long que de passer en revue le ou les
caractères de s1 pour chaque caractère de s2 -- et ce encore plus si
le test de présence réussit dès le premier caractère de s2 !

C'est plus vraiment des bouts de chandelle là, c'est des cierges entiers.
Bon, pour en avoir le coeur net une fois de plus, j'ai écrit le code :

Je le ferai tourner 1 000 000 de fois sur les chaines suivantes :
char* stringRecherche = "Une petite chaine de test";
char* valides = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ ";

note au passage que j'avais mis le code de strcspn dans mon code précédent,
donc voici les fonctions que j'ai testées :

// CODE DE PHP
size_t php(char *s1, char *s2, char *s1_end, char *s2_end)
{
register const char *p = s1, *spanp;
register char c = *p;

cont:
for (spanp = s2; p != s1_end && spanp != s2_end;) {
if (*spanp++ == c) {
c = *(++p);
goto cont;
}
}
return (p - s1);
}

// MON CODE PROPOSE PRECEDEMMENT
size_t moi(char *s1, char *s2, char *s1_end, char *s2_end)
{
bool isCharacterValid[256];
char* p;

memset(isCharacterValid, 0, sizeof(isCharacterValid));
for (p = s2; p < s2_end; p++)
isCharacterValid[*p] = true;

for (p = s1; p < s1_end && isCharacterValid[*p]; p++)
{ }

return p - s1;
}

// ESSAIE DE GAGNER DU TEMPS SUR MEMSET
// utilise un tableau de 32 caracteres (256 bits) au lieu de 256 caracteres
size_t moi2(char *s1, char *s2, char *s1_end, char *s2_end)
{
char isCharacterValid[32];
char* p;

memset(isCharacterValid, 0, sizeof(isCharacterValid));
for (p = s2; p < s2_end; p++)
isCharacterValid[*p / 8] |= (1 << (*p % 8));

for (p = s1; p < s1_end && (isCharacterValid[*p / 8] & (1 << (*p % 8)));
p++)
{ }

return p - s1;
}

// UTILISE UN TABLEAU PROPRE GLOBAL
// Conséquence : valable uniquement en multi thread
size_t moi3(char *s1, char *s2, char *s1_end, char *s2_end)
{
static bool isCharacterValid[256] = { false };
char* p;

for (p = s2; p < s2_end; p++)
isCharacterValid[*p] = true;

for (p = s1; p < s1_end && isCharacterValid[*p]; p++)
{ }

size_t res = p - s1;

for (p = s2; p < s2_end; p++)
isCharacterValid[*p] = false;

return res;
}

Resultats :
php: 2.002, 1.742, 1.752
moi: 0.350, 0.360, 0.360
moi2: 0.971, 0.951, 0.951
moi3: 0.290, 0.290, 0.290

Bon, peut être que la chaine recherchée est trop longue (28 caracteres). Je
refais un test avec seulement 10 caracteres ("Une petite")
php: 0.851, 0.871, 0.831
moi: 0.320, 0.320, 0.320
moi2: 0.851, 0.841, 0.841
moi3: 0.310, 0.290, 0.300

Bon, peut être que la chaine avec les caracteres possibles est trop longue,
je refais un test avec seulement 5 caracteres ("eintu ", chaine cherchée
"une nuit") et 10 millions d'iterations
php: 1.882, 2.053, 1.979
moi: 2.033, 2.033, 2.043
moi2: 1.953, 1.953, 1.963
moi3: 0.531, 0.541, 0.541

Qu'est ce qu'on voit ? memset ca torche, donc le cout de l'initialisation du
tableau de 256 caracteres (soit 64 mots sur une machine 32 bits) est
négligeable par rapport au reste de la fonction. Dans le premier cas (chaine
cherchée 28 caracteres, jeu autorisée 53 caracteres), "moi" est environ 5
fois plus rapide, dans le second plus de 2.5 fois. On atteint l'équilibre
pour des cas un peu dégénérés ("eintu", "une nuit": php est plus rapide,
"eintu", "une nuite": moi est plus rapide). Remarque que dans tous les
tests, moi3 (qui n'est pas multithread, donc difficilement comparable au
deux autres) est plus rapide.

Je sais pas combien de temps on gagnerait coté PHP (vu qu'il y a un gros
overhead à parser le code, décoder les variables et tout), mais c'est clair
que dans l'énorme majorité des cas, ma fonction serait plus rapide (2.5 fois
plus rapide pour vérifier qu'un numéro à 16 chiffres (genre carte bleu) est
composé uniquement de chiffres, 1.5 fois plus rapide pour vérifier qu'un
numéro à 10 chiffres (numéro de tel) est composé uniquement de chiffres).
C'est quoi les cas d'utilisation de cette fonction qui font qu'elle n'est
pas horriblement lente ?

--
Vincent

Le 12-05-2006, Vincent Lascaux <nospam@nospam.org> a écrit :

Qu'est ce qu'on voit ? memset ca torche, donc le cout de l'initialisation du
tableau de 256 caracteres (soit 64 mots sur une machine 32 bits) est
négligeable par rapport au reste de la fonction. Dans le premier cas (chaine
cherchée 28 caracteres, jeu autorisée 53 caracteres), "moi" est environ 5
fois plus rapide, dans le second plus de 2.5 fois. On atteint l'équilibre
pour des cas un peu dégénérés ("eintu", "une nuit": php est plus rapide,
"eintu", "une nuite": moi est plus rapide). Remarque que dans tous les
tests, moi3 (qui n'est pas multithread, donc difficilement comparable au
deux autres) est plus rapide.

Pas suivi le début, mais as-tu essayé avec des caractères utf-8 ?

--
Thomas Harding

Pas suivi le début, mais as-tu essayé avec des caractères utf-8 ?

strspn et strcspn ne fonctionnent pas avec des caracteres utf-8.
Si on veut ca, ca devient un brin plus chaud de conserver un algo rapide :
il faudrait alors un buffer de 2MB au lieu de 256 octets. Dans ce cas on
peut soit utiliser un arbre binaire de recherche (ou trier la chaine de
caracteres acceptables et faire une recherche dichotomique plutot que
linéaire) pour être en O((l1+l2)*log(l2)) ou utiliser une table de
hachage... Du coup, on serait surement moins performant sur des petites
chaines... à voir...

Il y a des équivalents de strspn et strcspn pour l'utf-8 en php ?

--
Vincent