Je veux remplacer , dans un string, une chaîne par une autre. Je
recherche la solution la plus simple et la plus claire (pas
spécialement la plus optimisée).
Pour l'instant je fais comme ceci :
------------------------------------------------------------
int pos = str.length();
while ((pos = str.rfind(from,pos)) != string::npos) {
str.replace( pos // position
,from.length() // taille
,to // Chaine de remplacement
);
}
------------------------------------------------------------
Voyez-vous une façon plus simple et plus courte de faire ?
(c'est pour montrer à mon CP que C++ est un language simple et
performant ;-) )
je lis ça comme une fonction recevant une /const string&/ et me retournant celle-ci modifiée dans un /string&/ c'est précisément les confusions qu'il ne me paraissait pas utile d'introduire.
Erreur de ma part: string& replace(string& str, const pair<const string,const string>& fromto);
Le const_cast<> serait un comportement indéfini.
Michael
Michael DOUBEZ wrote on 22/06/2007 08:57:
[snip]
certes, mais transmettre la chaîne opérande est (supportablement mais
inutilement) lourd, se rappeler l'ordre de 2 params est déjà dur,
alors 3 ! ;)
je lis ça comme une fonction recevant une /const string&/ et me
retournant celle-ci modifiée dans un /string&/ c'est précisément les
confusions qu'il ne me paraissait pas utile d'introduire.
Erreur de ma part:
string& replace(string& str, const pair<const string,const string>& fromto);
je lis ça comme une fonction recevant une /const string&/ et me retournant celle-ci modifiée dans un /string&/ c'est précisément les confusions qu'il ne me paraissait pas utile d'introduire.
Erreur de ma part: string& replace(string& str, const pair<const string,const string>& fromto);
Le const_cast<> serait un comportement indéfini.
Michael
Michael DOUBEZ
Michael DOUBEZ wrote on 22/06/2007 08:57:
[snip]
certes, mais transmettre la chaîne opérande est (supportablement mais inutilement) lourd, se rappeler l'ordre de 2 params est déjà dur, alors 3 ! ;)
je lis ça comme une fonction recevant une /const string&/ et me retournant celle-ci modifiée dans un /string&/ c'est précisément les confusions qu'il ne me paraissait pas utile d'introduire.
Erreur de ma part: string& replace(string& str, const pair<const string,const string>& fromto);
Le const_cast<> serait un comportement indéfini.
Ou bien la version fonctionnelle: string replace(const string& str, const pair<const string,const string>& fromto);
Je trouve quand même injuste que le langage limite l'utilisation des variable temporaire aux paramètres de type const. Ca force une utilisation fonctionnelle du C++.
Je suppose qu'il y a une raison à cela.
Michael
Michael DOUBEZ wrote on 22/06/2007 08:57:
[snip]
certes, mais transmettre la chaîne opérande est (supportablement
mais inutilement) lourd, se rappeler l'ordre de 2 params est déjà
dur, alors 3 ! ;)
je lis ça comme une fonction recevant une /const string&/ et me
retournant celle-ci modifiée dans un /string&/ c'est précisément les
confusions qu'il ne me paraissait pas utile d'introduire.
Erreur de ma part:
string& replace(string& str, const pair<const string,const string>&
fromto);
Le const_cast<> serait un comportement indéfini.
Ou bien la version fonctionnelle:
string replace(const string& str, const pair<const string,const string>&
fromto);
Je trouve quand même injuste que le langage limite l'utilisation des
variable temporaire aux paramètres de type const. Ca force une
utilisation fonctionnelle du C++.
je lis ça comme une fonction recevant une /const string&/ et me retournant celle-ci modifiée dans un /string&/ c'est précisément les confusions qu'il ne me paraissait pas utile d'introduire.
Erreur de ma part: string& replace(string& str, const pair<const string,const string>& fromto);
Le const_cast<> serait un comportement indéfini.
Ou bien la version fonctionnelle: string replace(const string& str, const pair<const string,const string>& fromto);
Je trouve quand même injuste que le langage limite l'utilisation des variable temporaire aux paramètres de type const. Ca force une utilisation fonctionnelle du C++.
Je suppose qu'il y a une raison à cela.
Michael
Jean-Marc Bourguet
Michael DOUBEZ writes:
Je trouve quand même injuste que le langage limite l'utilisation des variable temporaire aux paramètres de type const. Ca force une utilisation fonctionnelle du C++.
Je suppose que tu veux dire qu'on ne peut pas binder une rvalue a une reference non const. On peut binder une temporaire a une reference non const, si on reussi a en avoir une vision non rvalue (le plus simple est d'appeler un membre qui renvoie une reference vers *this).
Note que quand on passe une rvalue a une reference non constante, on introduit un temporaire (et donc l'appel a un constructeur de copie meme s'il peut etre supprime)
Je suppose qu'il y a une raison à cela.
Je crois que c'est plutot un effet de bord d'un modele un peu complique quand interviennent les notions de lvalue, rvalue referant a des objets et rvalue ne referant pas a des objets. L'interdiction est tres sensee pour les rvalue "non objet", moins pour les rvalue "objet".
A noter que C0X introduit des rvalue references qui permettent aussi d'autres choses (en autre de donner une semantique de deplacement a certaines operations, ce qu'autoriser simplement le passage de rvalue "objet" a des references non constante n'aurait pas permis).
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
Michael DOUBEZ <michael.doubez@free.fr> writes:
Je trouve quand même injuste que le langage limite l'utilisation des
variable temporaire aux paramètres de type const. Ca force une
utilisation fonctionnelle du C++.
Je suppose que tu veux dire qu'on ne peut pas binder une rvalue a une
reference non const. On peut binder une temporaire a une reference non
const, si on reussi a en avoir une vision non rvalue (le plus simple est
d'appeler un membre qui renvoie une reference vers *this).
Note que quand on passe une rvalue a une reference non constante, on
introduit un temporaire (et donc l'appel a un constructeur de copie meme
s'il peut etre supprime)
Je suppose qu'il y a une raison à cela.
Je crois que c'est plutot un effet de bord d'un modele un peu complique
quand interviennent les notions de lvalue, rvalue referant a des objets et
rvalue ne referant pas a des objets. L'interdiction est tres sensee pour
les rvalue "non objet", moins pour les rvalue "objet".
A noter que C0X introduit des rvalue references qui permettent aussi
d'autres choses (en autre de donner une semantique de deplacement a
certaines operations, ce qu'autoriser simplement le passage de rvalue
"objet" a des references non constante n'aurait pas permis).
A+
--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Je trouve quand même injuste que le langage limite l'utilisation des variable temporaire aux paramètres de type const. Ca force une utilisation fonctionnelle du C++.
Je suppose que tu veux dire qu'on ne peut pas binder une rvalue a une reference non const. On peut binder une temporaire a une reference non const, si on reussi a en avoir une vision non rvalue (le plus simple est d'appeler un membre qui renvoie une reference vers *this).
Note que quand on passe une rvalue a une reference non constante, on introduit un temporaire (et donc l'appel a un constructeur de copie meme s'il peut etre supprime)
Je suppose qu'il y a une raison à cela.
Je crois que c'est plutot un effet de bord d'un modele un peu complique quand interviennent les notions de lvalue, rvalue referant a des objets et rvalue ne referant pas a des objets. L'interdiction est tres sensee pour les rvalue "non objet", moins pour les rvalue "objet".
A noter que C0X introduit des rvalue references qui permettent aussi d'autres choses (en autre de donner une semantique de deplacement a certaines operations, ce qu'autoriser simplement le passage de rvalue "objet" a des references non constante n'aurait pas permis).
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
Michael DOUBEZ
Michael DOUBEZ writes:
Je trouve quand même injuste que le langage limite l'utilisation des variable temporaire aux paramètres de type const. Ca force une utilisation fonctionnelle du C++.
Je suppose que tu veux dire qu'on ne peut pas binder une rvalue a une reference non const.
Oui. Je parle des reference const/non const.
On peut binder une temporaire a une reference non const, si on reussi a en avoir une vision non rvalue (le plus simple est d'appeler un membre qui renvoie une reference vers *this).
Interessant.
Je n'y avais pas pensé mais on peut utiliser un template du type suivant:
puis appeler void mutating(temp& t); avec mutating(to_lvalue<temp>(temp(10)));
Note que quand on passe une rvalue a une reference non constante, on introduit un temporaire (et donc l'appel a un constructeur de copie meme s'il peut etre supprime)
Ca doit être dépendant du compilateur. Un exemple simple n'a pas appelé l'opérateur de recopie sous gcc avec le template ci-dessus.
Je suppose qu'il y a une raison à cela.
Je crois que c'est plutot un effet de bord d'un modele un peu complique quand interviennent les notions de lvalue, rvalue referant a des objets et rvalue ne referant pas a des objets. L'interdiction est tres sensee pour les rvalue "non objet", moins pour les rvalue "objet".
Pour les rvalues "non objet", je comprends pourquoi cela serait inutile et même cela pourrait amener des bugs difficilement détectables. Mais je ne comprends pas pourquoi cela a été interdit.
A noter que C0X introduit des rvalue references qui permettent aussi d'autres choses (en autre de donner une semantique de deplacement a certaines operations, ce qu'autoriser simplement le passage de rvalue "objet" a des references non constante n'aurait pas permis).
Je ne comprends pas. C0x autorise-t-il les rvalues reference ou y a-t-il une sémantique particulière ?
Michael
Michael DOUBEZ <michael.doubez@free.fr> writes:
Je trouve quand même injuste que le langage limite l'utilisation des
variable temporaire aux paramètres de type const. Ca force une
utilisation fonctionnelle du C++.
Je suppose que tu veux dire qu'on ne peut pas binder une rvalue a une
reference non const.
Oui. Je parle des reference const/non const.
On peut binder une temporaire a une reference non
const, si on reussi a en avoir une vision non rvalue (le plus simple est
d'appeler un membre qui renvoie une reference vers *this).
Interessant.
Je n'y avais pas pensé mais on peut utiliser un template du type suivant:
puis appeler
void mutating(temp& t);
avec
mutating(to_lvalue<temp>(temp(10)));
Note que quand on passe une rvalue a une reference non constante, on
introduit un temporaire (et donc l'appel a un constructeur de copie meme
s'il peut etre supprime)
Ca doit être dépendant du compilateur. Un exemple simple n'a pas appelé
l'opérateur de recopie sous gcc avec le template ci-dessus.
Je suppose qu'il y a une raison à cela.
Je crois que c'est plutot un effet de bord d'un modele un peu complique
quand interviennent les notions de lvalue, rvalue referant a des objets et
rvalue ne referant pas a des objets. L'interdiction est tres sensee pour
les rvalue "non objet", moins pour les rvalue "objet".
Pour les rvalues "non objet", je comprends pourquoi cela serait inutile
et même cela pourrait amener des bugs difficilement détectables. Mais je
ne comprends pas pourquoi cela a été interdit.
A noter que C0X introduit des rvalue references qui permettent aussi
d'autres choses (en autre de donner une semantique de deplacement a
certaines operations, ce qu'autoriser simplement le passage de rvalue
"objet" a des references non constante n'aurait pas permis).
Je ne comprends pas. C0x autorise-t-il les rvalues reference ou y a-t-il
une sémantique particulière ?
Je trouve quand même injuste que le langage limite l'utilisation des variable temporaire aux paramètres de type const. Ca force une utilisation fonctionnelle du C++.
Je suppose que tu veux dire qu'on ne peut pas binder une rvalue a une reference non const.
Oui. Je parle des reference const/non const.
On peut binder une temporaire a une reference non const, si on reussi a en avoir une vision non rvalue (le plus simple est d'appeler un membre qui renvoie une reference vers *this).
Interessant.
Je n'y avais pas pensé mais on peut utiliser un template du type suivant:
puis appeler void mutating(temp& t); avec mutating(to_lvalue<temp>(temp(10)));
Note que quand on passe une rvalue a une reference non constante, on introduit un temporaire (et donc l'appel a un constructeur de copie meme s'il peut etre supprime)
Ca doit être dépendant du compilateur. Un exemple simple n'a pas appelé l'opérateur de recopie sous gcc avec le template ci-dessus.
Je suppose qu'il y a une raison à cela.
Je crois que c'est plutot un effet de bord d'un modele un peu complique quand interviennent les notions de lvalue, rvalue referant a des objets et rvalue ne referant pas a des objets. L'interdiction est tres sensee pour les rvalue "non objet", moins pour les rvalue "objet".
Pour les rvalues "non objet", je comprends pourquoi cela serait inutile et même cela pourrait amener des bugs difficilement détectables. Mais je ne comprends pas pourquoi cela a été interdit.
A noter que C0X introduit des rvalue references qui permettent aussi d'autres choses (en autre de donner une semantique de deplacement a certaines operations, ce qu'autoriser simplement le passage de rvalue "objet" a des references non constante n'aurait pas permis).
Je ne comprends pas. C0x autorise-t-il les rvalues reference ou y a-t-il une sémantique particulière ?
Michael
Jean-Marc Bourguet
Michael DOUBEZ writes:
Note que quand on passe une rvalue a une reference non constante, on introduit un temporaire (et donc l'appel a un constructeur de copie meme s'il peut etre supprime)
Ca doit être dépendant du compilateur. Un exemple simple n'a pas appelé l'opérateur de recopie sous gcc avec le template ci-dessus.
C'est un des cas ou le compilateur peut supprimer le constructeur de copie. Mais il doit toujours etre accessible (ce que g++ oubliait de verifier avant 3.4).
Je suppose qu'il y a une raison à cela. Je crois que c'est plutot un effet de bord d'un modele un peu complique
quand interviennent les notions de lvalue, rvalue referant a des objets et rvalue ne referant pas a des objets. L'interdiction est tres sensee pour les rvalue "non objet", moins pour les rvalue "objet".
Pour les rvalues "non objet", je comprends pourquoi cela serait inutile et même cela pourrait amener des bugs difficilement détectables. Mais je ne comprends pas pourquoi cela a été interdit.
etait valide au debut (x est d'abord converti en int et devient une rvalue).
A noter que C0X introduit des rvalue references qui permettent aussi d'autres choses (en autre de donner une semantique de deplacement a certaines operations, ce qu'autoriser simplement le passage de rvalue "objet" a des references non constante n'aurait pas permis).
Je ne comprends pas. C0x autorise-t-il les rvalues reference ou y a-t-il une sémantique particulière ?
C0X introduit des "rvalue references" (notees avec && plutot que &) qui peuvent etre bindee a des rvalues meme quand elles ne sont pas const. Avec des regles de surcharge qui vont bien.
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
Michael DOUBEZ <michael.doubez@free.fr> writes:
Note que quand on passe une rvalue a une reference non constante, on
introduit un temporaire (et donc l'appel a un constructeur de copie
meme s'il peut etre supprime)
Ca doit être dépendant du compilateur. Un exemple simple n'a pas appelé
l'opérateur de recopie sous gcc avec le template ci-dessus.
C'est un des cas ou le compilateur peut supprimer le constructeur de copie.
Mais il doit toujours etre accessible (ce que g++ oubliait de verifier
avant 3.4).
Je suppose qu'il y a une raison à cela.
Je crois que c'est plutot un effet de bord d'un modele un peu complique
quand interviennent les notions de lvalue, rvalue referant a des objets et
rvalue ne referant pas a des objets. L'interdiction est tres sensee pour
les rvalue "non objet", moins pour les rvalue "objet".
Pour les rvalues "non objet", je comprends pourquoi cela serait inutile et
même cela pourrait amener des bugs difficilement détectables. Mais je ne
comprends pas pourquoi cela a été interdit.
etait valide au debut (x est d'abord converti en int et devient une rvalue).
A noter que C0X introduit des rvalue references qui permettent aussi
d'autres choses (en autre de donner une semantique de deplacement a
certaines operations, ce qu'autoriser simplement le passage de rvalue
"objet" a des references non constante n'aurait pas permis).
Je ne comprends pas. C0x autorise-t-il les rvalues reference ou y a-t-il
une sémantique particulière ?
C0X introduit des "rvalue references" (notees avec && plutot que &) qui
peuvent etre bindee a des rvalues meme quand elles ne sont pas const. Avec
des regles de surcharge qui vont bien.
A+
--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Note que quand on passe une rvalue a une reference non constante, on introduit un temporaire (et donc l'appel a un constructeur de copie meme s'il peut etre supprime)
Ca doit être dépendant du compilateur. Un exemple simple n'a pas appelé l'opérateur de recopie sous gcc avec le template ci-dessus.
C'est un des cas ou le compilateur peut supprimer le constructeur de copie. Mais il doit toujours etre accessible (ce que g++ oubliait de verifier avant 3.4).
Je suppose qu'il y a une raison à cela. Je crois que c'est plutot un effet de bord d'un modele un peu complique
quand interviennent les notions de lvalue, rvalue referant a des objets et rvalue ne referant pas a des objets. L'interdiction est tres sensee pour les rvalue "non objet", moins pour les rvalue "objet".
Pour les rvalues "non objet", je comprends pourquoi cela serait inutile et même cela pourrait amener des bugs difficilement détectables. Mais je ne comprends pas pourquoi cela a été interdit.
etait valide au debut (x est d'abord converti en int et devient une rvalue).
A noter que C0X introduit des rvalue references qui permettent aussi d'autres choses (en autre de donner une semantique de deplacement a certaines operations, ce qu'autoriser simplement le passage de rvalue "objet" a des references non constante n'aurait pas permis).
Je ne comprends pas. C0x autorise-t-il les rvalues reference ou y a-t-il une sémantique particulière ?
C0X introduit des "rvalue references" (notees avec && plutot que &) qui peuvent etre bindee a des rvalues meme quand elles ne sont pas const. Avec des regles de surcharge qui vont bien.
A+
-- Jean-Marc FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html Site de usenet-fr: http://www.usenet-fr.news.eu.org
Mathias Gaunard
Une fois la fonction générique écrite, la différence n'est pas flagrante:
Au niveau performance, quelque peu, si.
//avec regex //en priant que fromstr n'ai pas de caractères spéciaux boost::regex e(string("(")+fromstr+")");
L'informatique n'est pas affaire de religion. Utilise plutôt boost::regex_constants::literal en second argument.
Une fois la fonction générique écrite, la différence n'est pas flagrante:
Au niveau performance, quelque peu, si.
//avec regex
//en priant que fromstr n'ai pas de caractères spéciaux
boost::regex e(string("(")+fromstr+")");
L'informatique n'est pas affaire de religion.
Utilise plutôt boost::regex_constants::literal en second argument.
Une fois la fonction générique écrite, la différence n'est pas flagrante:
Au niveau performance, quelque peu, si.
//avec regex //en priant que fromstr n'ai pas de caractères spéciaux boost::regex e(string("(")+fromstr+")");
L'informatique n'est pas affaire de religion. Utilise plutôt boost::regex_constants::literal en second argument.
Michael DOUBEZ
Une fois la fonction générique écrite, la différence n'est pas flagrante:
Au niveau performance, quelque peu, si.
Au niveau du nombre de ligne de code non.
Pour les performances, je n'ai pas fait de bench mais je ne vois pas pourquoi l'algorithme que j'ai donné serait plus lent. AMA, à la fin de la journée, une recherche dans une string est une comparaison des éléments qui la compose.
//avec regex //en priant que fromstr n'ai pas de caractères spéciaux boost::regex e(string("(")+fromstr+")");
L'informatique n'est pas affaire de religion. Utilise plutôt boost::regex_constants::literal en second argument.
OK, je regarderai regex_constants et laisserai les poupées vaudou au placard.
Michael
Une fois la fonction générique écrite, la différence n'est pas flagrante:
Au niveau performance, quelque peu, si.
Au niveau du nombre de ligne de code non.
Pour les performances, je n'ai pas fait de bench mais je ne vois pas
pourquoi l'algorithme que j'ai donné serait plus lent. AMA, à la fin de
la journée, une recherche dans une string est une comparaison des
éléments qui la compose.
//avec regex
//en priant que fromstr n'ai pas de caractères spéciaux
boost::regex e(string("(")+fromstr+")");
L'informatique n'est pas affaire de religion.
Utilise plutôt boost::regex_constants::literal en second argument.
OK, je regarderai regex_constants et laisserai les poupées vaudou au
placard.
Une fois la fonction générique écrite, la différence n'est pas flagrante:
Au niveau performance, quelque peu, si.
Au niveau du nombre de ligne de code non.
Pour les performances, je n'ai pas fait de bench mais je ne vois pas pourquoi l'algorithme que j'ai donné serait plus lent. AMA, à la fin de la journée, une recherche dans une string est une comparaison des éléments qui la compose.
//avec regex //en priant que fromstr n'ai pas de caractères spéciaux boost::regex e(string("(")+fromstr+")");
L'informatique n'est pas affaire de religion. Utilise plutôt boost::regex_constants::literal en second argument.
OK, je regarderai regex_constants et laisserai les poupées vaudou au placard.
Michael
Sylvain
Michael DOUBEZ wrote on 25/06/2007 08:56:
Pour les performances, je n'ai pas fait de bench mais je ne vois pas pourquoi l'algorithme que j'ai donné serait plus lent. AMA, à la fin de la journée, une recherche dans une string est une comparaison des éléments qui la compose.
pour une recherche mono-pattern, il apparait en effet qu'il faudrait faire des efforts pour inventer un algo plus lent que la moyenne; pour une recherche simultanée de plusierus patterns, les diffs de perfs peuvent être plus significatives.
Sylvain.
Michael DOUBEZ wrote on 25/06/2007 08:56:
Pour les performances, je n'ai pas fait de bench mais je ne vois pas
pourquoi l'algorithme que j'ai donné serait plus lent. AMA, à la fin de
la journée, une recherche dans une string est une comparaison des
éléments qui la compose.
pour une recherche mono-pattern, il apparait en effet qu'il faudrait
faire des efforts pour inventer un algo plus lent que la moyenne; pour
une recherche simultanée de plusierus patterns, les diffs de perfs
peuvent être plus significatives.
Pour les performances, je n'ai pas fait de bench mais je ne vois pas pourquoi l'algorithme que j'ai donné serait plus lent. AMA, à la fin de la journée, une recherche dans une string est une comparaison des éléments qui la compose.
pour une recherche mono-pattern, il apparait en effet qu'il faudrait faire des efforts pour inventer un algo plus lent que la moyenne; pour une recherche simultanée de plusierus patterns, les diffs de perfs peuvent être plus significatives.
Sylvain.
James Kanze
On Jun 25, 8:56 am, Michael DOUBEZ wrote:
Une fois la fonction générique écrite, la différence n'est pas flagrante:
Au niveau performance, quelque peu, si.
Au niveau du nombre de ligne de code non.
Au niveau du nombre de lignes de code que tu as écrit, en effet. Utiliser Boost::regex profite de l'existant ; toi, non.
Pour les performances, je n'ai pas fait de bench mais je ne vois pas pourquoi l'algorithme que j'ai donné serait plus lent.
Peut-être parce qu'il est. Je ne sais pas par rapport à Boost::regex---le fait qu'il supporte des extensions (comme "(...)1") fait probablement qu'il ne peut pas se servir d'une DFA. En revanche, le fait qu'il sert à beaucoup fait qu'on pourrait y investir beaucoup plus d'efforts, disons pour faire une implémentation adaptive, qui utilise BM si la chaîne est fixe, par exemple.
AMA, à la fin de la journée, une recherche dans une string est une comparaison des éléments qui la compose.
Si on veut faire lentement, oui. Sinon, KMP utilise un DFA ; si on n'implémente que des expressions rationnelles pûres, un DFA marche aussi. (Dans ma propre implémentation des expressions rationnelles, j'utilise un DFA créé de façon paresseuse.) Et s'il s'agit de ne chercher que d'une chaîne, sans expression, BM permet de faire encore mieux. En gros, si N est la longueur de l'espace où on cherche, et M la longueur de la chaîne qu'on cherche, ton algorithme est O(N*M), KMP ou mon expression rationnelle O(N), et BM O(N/M). (Je ne connais pas d'analyse des expressions régulières étendues, à la Boost, mais je crois qu'on doit pouvoir les implémenter en O(N) aussi, avec néaumoins une facteur constante nettement plus élevée que pour le DFA d'une expression rationnelle pure, et peut-être des écarts vers O(N*M) quand on essaie des matchs pour "1", etc.)
-- James Kanze (GABI Software, from CAI) email: Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
On Jun 25, 8:56 am, Michael DOUBEZ <michael.dou...@free.fr> wrote:
Une fois la fonction générique écrite, la différence n'est
pas flagrante:
Au niveau performance, quelque peu, si.
Au niveau du nombre de ligne de code non.
Au niveau du nombre de lignes de code que tu as écrit, en effet.
Utiliser Boost::regex profite de l'existant ; toi, non.
Pour les performances, je n'ai pas fait de bench mais je ne vois pas
pourquoi l'algorithme que j'ai donné serait plus lent.
Peut-être parce qu'il est. Je ne sais pas par rapport à
Boost::regex---le fait qu'il supporte des extensions (comme
"(...)1") fait probablement qu'il ne peut pas se servir d'une
DFA. En revanche, le fait qu'il sert à beaucoup fait qu'on
pourrait y investir beaucoup plus d'efforts, disons pour faire
une implémentation adaptive, qui utilise BM si la chaîne est
fixe, par exemple.
AMA, à la fin de la journée, une recherche dans une string est
une comparaison des éléments qui la compose.
Si on veut faire lentement, oui. Sinon, KMP utilise un DFA ; si
on n'implémente que des expressions rationnelles pûres, un DFA
marche aussi. (Dans ma propre implémentation des expressions
rationnelles, j'utilise un DFA créé de façon paresseuse.) Et
s'il s'agit de ne chercher que d'une chaîne, sans expression, BM
permet de faire encore mieux. En gros, si N est la longueur de
l'espace où on cherche, et M la longueur de la chaîne qu'on
cherche, ton algorithme est O(N*M), KMP ou mon expression
rationnelle O(N), et BM O(N/M). (Je ne connais pas d'analyse
des expressions régulières étendues, à la Boost, mais je crois
qu'on doit pouvoir les implémenter en O(N) aussi, avec néaumoins
une facteur constante nettement plus élevée que pour le DFA
d'une expression rationnelle pure, et peut-être des écarts vers
O(N*M) quand on essaie des matchs pour "1", etc.)
--
James Kanze (GABI Software, from CAI) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Une fois la fonction générique écrite, la différence n'est pas flagrante:
Au niveau performance, quelque peu, si.
Au niveau du nombre de ligne de code non.
Au niveau du nombre de lignes de code que tu as écrit, en effet. Utiliser Boost::regex profite de l'existant ; toi, non.
Pour les performances, je n'ai pas fait de bench mais je ne vois pas pourquoi l'algorithme que j'ai donné serait plus lent.
Peut-être parce qu'il est. Je ne sais pas par rapport à Boost::regex---le fait qu'il supporte des extensions (comme "(...)1") fait probablement qu'il ne peut pas se servir d'une DFA. En revanche, le fait qu'il sert à beaucoup fait qu'on pourrait y investir beaucoup plus d'efforts, disons pour faire une implémentation adaptive, qui utilise BM si la chaîne est fixe, par exemple.
AMA, à la fin de la journée, une recherche dans une string est une comparaison des éléments qui la compose.
Si on veut faire lentement, oui. Sinon, KMP utilise un DFA ; si on n'implémente que des expressions rationnelles pûres, un DFA marche aussi. (Dans ma propre implémentation des expressions rationnelles, j'utilise un DFA créé de façon paresseuse.) Et s'il s'agit de ne chercher que d'une chaîne, sans expression, BM permet de faire encore mieux. En gros, si N est la longueur de l'espace où on cherche, et M la longueur de la chaîne qu'on cherche, ton algorithme est O(N*M), KMP ou mon expression rationnelle O(N), et BM O(N/M). (Je ne connais pas d'analyse des expressions régulières étendues, à la Boost, mais je crois qu'on doit pouvoir les implémenter en O(N) aussi, avec néaumoins une facteur constante nettement plus élevée que pour le DFA d'une expression rationnelle pure, et peut-être des écarts vers O(N*M) quand on essaie des matchs pour "1", etc.)
-- James Kanze (GABI Software, from CAI) email: Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
James Kanze
On Jun 25, 7:34 pm, Sylvain wrote:
Michael DOUBEZ wrote on 25/06/2007 08:56:
Pour les performances, je n'ai pas fait de bench mais je ne vois pas pourquoi l'algorithme que j'ai donné serait plus lent. AMA, à la fi n de la journée, une recherche dans une string est une comparaison des éléments qui la compose.
pour une recherche mono-pattern, il apparait en effet qu'il faudrait faire des efforts pour inventer un algo plus lent que la moyenne; pour une recherche simultanée de plusierus patterns, les diffs de perfs peuvent être plus significatives.
Je ne suis pas sûr d'avoir saisi les nuances de ce que tu as écrit. Son algorithme est O(N*M). Pour une recherche mono-pattern, on sait faire O(N/M), et pour des expressions rationnelles classiques (sans certaines extensions comme "1"), on sait faire O(N).
-- James Kanze (GABI Software, from CAI) email: Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
On Jun 25, 7:34 pm, Sylvain <noS...@mail.net> wrote:
Michael DOUBEZ wrote on 25/06/2007 08:56:
Pour les performances, je n'ai pas fait de bench mais je ne vois pas
pourquoi l'algorithme que j'ai donné serait plus lent. AMA, à la fi n de
la journée, une recherche dans une string est une comparaison des
éléments qui la compose.
pour une recherche mono-pattern, il apparait en effet qu'il faudrait
faire des efforts pour inventer un algo plus lent que la moyenne; pour
une recherche simultanée de plusierus patterns, les diffs de perfs
peuvent être plus significatives.
Je ne suis pas sûr d'avoir saisi les nuances de ce que tu as
écrit. Son algorithme est O(N*M). Pour une recherche
mono-pattern, on sait faire O(N/M), et pour des expressions
rationnelles classiques (sans certaines extensions comme "1"),
on sait faire O(N).
--
James Kanze (GABI Software, from CAI) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Pour les performances, je n'ai pas fait de bench mais je ne vois pas pourquoi l'algorithme que j'ai donné serait plus lent. AMA, à la fi n de la journée, une recherche dans une string est une comparaison des éléments qui la compose.
pour une recherche mono-pattern, il apparait en effet qu'il faudrait faire des efforts pour inventer un algo plus lent que la moyenne; pour une recherche simultanée de plusierus patterns, les diffs de perfs peuvent être plus significatives.
Je ne suis pas sûr d'avoir saisi les nuances de ce que tu as écrit. Son algorithme est O(N*M). Pour une recherche mono-pattern, on sait faire O(N/M), et pour des expressions rationnelles classiques (sans certaines extensions comme "1"), on sait faire O(N).
-- James Kanze (GABI Software, from CAI) email: Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
