[C] performance de strcmp

Fermé
tinoeldorados - 10 déc. 2008 à 11:16
kilian Messages postés 8731 Date d'inscription vendredi 19 septembre 2003 Statut Modérateur Dernière intervention 20 août 2016 - 11 déc. 2008 à 17:13
Bonjour,

Je fais de nobreuse boucle de comparaison de chaine et j'ai des problemes de performance.

J'ai charge un texte 4mo dans un char *
je positionne des pointeurs (char *) dedans par coup de

position1 = &texte[i]
position2= &texte[j]

jusqu'a la aucun souci

mais quand je fais des strcmp sur position1 et position2
la fonction dure un temps fou... alors que les phrases sont differentes en moyenne en moins de 3 caracteres

et si dans texte je remplace '\n' poar '\0'
la meme fonction strcmp va beaucoup plus vite ...

comme si STRCMP faisait une copie des chaines avant la comparaison ???

Quelqu'un a t'il une idee

car j'ai besion de mes '\n' dans la suite et je trouve dommage de les substituer 2 fois

8 réponses

kilian Messages postés 8731 Date d'inscription vendredi 19 septembre 2003 Statut Modérateur Dernière intervention 20 août 2016 1 522
10 déc. 2008 à 11:59
Salut,

Imagine cette chaine:

char *s = "Je suis une chaine mais bon ca va encore je suis pas trop grande, ceci dit je pourrais très bien faire Mo et continuer comme ça très longtemps.....";

char *s1 = &s[3] ;
char *s2 = &s[12];

if (!strcmp(s1, s2)) {
    /* N'arrivera jamais, tu es en train de comparer "suis une chaine mais bon ca va encore je suis pas trop grande, ceci dit je pourrais très bien faire Mo et continuer comme ça très longtemps....." 
avec "chaine mais bon ca va encore je suis pas trop grande, ceci dit je pourrais très bien faire Mo et continuer comme ça très longtemps....."


En gros tu es en train de partir du principe que strcmp s'arrête à la fin d'un mot, ou d'une ligne, mais non. Donc ce que tu fais n'a pas de sens.
Selon tes besoins, tu pourrais utiliser strncmp qui permet de limiter la comparaison au delà d'une certaine longueur.
0
kilian Messages postés 8731 Date d'inscription vendredi 19 septembre 2003 Statut Modérateur Dernière intervention 20 août 2016 1 522
10 déc. 2008 à 12:05
Note qu'il me semble que strcmp est implémenté en assembleur dans la glibc, donc performances à gogo: à titre d'exemple, la comparaison de chaine sous x86 se fait en utilisant une seule instruction processeur (cmpsb).

A moins que ce soit gcc qui soit capable de transformer ça si bien en assembleur...sais plus....
0
Il est normal qu'en remplaçant les \n par \0, ça aille plus vite.
En effet, un \0 est une fin de chaîne, donc la comparaison s'arrête.
strcmp (comparaison de chaînes) compare des chaînes ---> donc s'arrête au premier \0 ou à la première différence (et renvoie d'ailleurs cette différence).
0
Char Snipeur Messages postés 9688 Date d'inscription vendredi 23 avril 2004 Statut Contributeur Dernière intervention 2 octobre 2020 1 328
10 déc. 2008 à 17:00
--------------------------------8 7.21.4 Comparison functions
> 1 The sign of a nonzero value returned by the comparison functions
> memcmp, strcmp, and strncmp is determined by the sign of the difference
> between the values of the first pair of characters (both interpreted as
> unsigned char) that differ in the objects being compared.
> -------------------------------->8-----------------------------------
>
> --------------------------------8 7.21.4.2 p3 The strcmp function returns an integer greater than, equal
> to, or less than zero, accordingly as the string pointed to by s1 is
> greater than, equal to, or less than the string pointed to by s2.
> -------------------------------->8-----------------------------------
C'est pas très clair, mais apparemment, strcmp cherche à comparer les longueur de chaîne, d'où l'éventuel longueur.
Mais si ça ne te conviens pas, tu peux toujours faire une fonction personnel qui irai plus vite retournant une valeur dès que deux caractères diffèrent.
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Implémentation de cette fonction sur Linux:
/**
 * strcmp - Compare two strings
 * @cs: One string
 * @ct: Another string
 */
int strcmp (const char *cs, const char *ct)
{
	signed char __res;

	while (1) {
		if ((__res = *cs - *ct++) != 0 || !*cs++)
			break;
	}
	return __res;
}
0
fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 816
10 déc. 2008 à 18:08
Salut,
Non strcmp ne cherche pas à évaluer la longueur.
strcmp c'est une bébète boucle while tant que les caractères sont égaux.
Cdlt
0
Char Snipeur Messages postés 9688 Date d'inscription vendredi 23 avril 2004 Statut Contributeur Dernière intervention 2 octobre 2020 1 328
11 déc. 2008 à 10:09
pourquoi cette lenteur d'exécution alors ?
0
fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 816
11 déc. 2008 à 14:57
Ca c'est une bonne question.
J'aimerais bien quand même voir le code en question. Car sur ma machine, il n'y a, pas de problèmes pour ça.
Si ça se trouve, le problème vient d'ailleurs.

Cdlt
0
kilian Messages postés 8731 Date d'inscription vendredi 19 septembre 2003 Statut Modérateur Dernière intervention 20 août 2016 1 522 > fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022
11 déc. 2008 à 14:59
A priori il fait une comparaison sur deux sous chaines d'un ensemble de 4 Mo. Donc ya qu' à imaginer...
0
fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 816 > kilian Messages postés 8731 Date d'inscription vendredi 19 septembre 2003 Statut Modérateur Dernière intervention 20 août 2016
11 déc. 2008 à 15:11
Souvent l'erreur vient plus de l'utilisation dont on se sert des bibliothèques de des bibliothèques elles-même.
Pour ma part, j'ai fait un test sur ma machine, et il n'y a aucun problème même pour des chaînes de grands formats, voilà pourquoi je demande à voir le code.
Cdlt
0
kilian Messages postés 8731 Date d'inscription vendredi 19 septembre 2003 Statut Modérateur Dernière intervention 20 août 2016 1 522 > fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022
11 déc. 2008 à 15:14
Cdlt toi-même!
0
fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 816 > kilian Messages postés 8731 Date d'inscription vendredi 19 septembre 2003 Statut Modérateur Dernière intervention 20 août 2016
11 déc. 2008 à 15:16
Pas bien d'insulter de Cdlt :p
0
Char Snipeur Messages postés 9688 Date d'inscription vendredi 23 avril 2004 Statut Contributeur Dernière intervention 2 octobre 2020 1 328
11 déc. 2008 à 16:39
pour en revenir au sujet, à moins d'avoir un texte étrange (avec plein de fois les mêmes caractère), et comme on ne passe qu'un pointeur, il n'y a pas de raison que cette fonction soit lente. Sauf copie, ou comparaison de longueur. Ou alors on ne nous dit pas tout sur la chaine à comparer.
Les deux gamins : direction le café, sinon ça va sévir ! ;)
Mais j'aimerai bien qu'on m'explique "Le gâteau est un mensonge!"
0
kilian Messages postés 8731 Date d'inscription vendredi 19 septembre 2003 Statut Modérateur Dernière intervention 20 août 2016 1 522
11 déc. 2008 à 17:13
strcmp parcoure toute les deux chaines pour la comparaison, c'est pour ça. Il ne répond pas qu'un simple oui ou non il répond un entier qui reflète un peu le résultat.

Pour "le gâteau est un mensonge", il faudrait que tu joues au jeu "Portal" ;-)
0