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 ;-) )
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.
C'est vrai. A condition d'avoir boost (ou une autre lib adhoc). Si le programme link déjà avec libboost_regex et qu'on connait Boost.regex, je suis d'accord que ça va largement plus vite à coder.
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.
D'après le post de Mathias Gaunard, boost permet de spécifier en option que le pattern est une string litteral. Je n'ai pas regardé dans le code de Boost.Regex mais je suppose qu'ils spécialisent la stratégie en fonction.
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)
Au pire cas et O(N+M) au mieux.
, KMP ou mon expression rationnelle O(N), et BM O(N/M).
Au meilleur cas je suppose. Enfin, un O(N) est impressionnant. Je regarderai KMP de plus près.
(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.)
D'accord, mon algo tout simple n'est pas un foudre de guerre.
Michael
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.
C'est vrai. A condition d'avoir boost (ou une autre lib adhoc).
Si le programme link déjà avec libboost_regex et qu'on connait
Boost.regex, je suis d'accord que ça va largement plus vite à coder.
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.
D'après le post de Mathias Gaunard, boost permet de spécifier en option
que le pattern est une string litteral. Je n'ai pas regardé dans le code
de Boost.Regex mais je suppose qu'ils spécialisent la stratégie en fonction.
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)
Au pire cas et O(N+M) au mieux.
, KMP ou mon expression
rationnelle O(N), et BM O(N/M).
Au meilleur cas je suppose.
Enfin, un O(N) est impressionnant. Je regarderai KMP de plus près.
(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.)
D'accord, mon algo tout simple n'est pas un foudre de guerre.
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.
C'est vrai. A condition d'avoir boost (ou une autre lib adhoc). Si le programme link déjà avec libboost_regex et qu'on connait Boost.regex, je suis d'accord que ça va largement plus vite à coder.
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.
D'après le post de Mathias Gaunard, boost permet de spécifier en option que le pattern est une string litteral. Je n'ai pas regardé dans le code de Boost.Regex mais je suppose qu'ils spécialisent la stratégie en fonction.
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)
Au pire cas et O(N+M) au mieux.
, KMP ou mon expression rationnelle O(N), et BM O(N/M).
Au meilleur cas je suppose. Enfin, un O(N) est impressionnant. Je regarderai KMP de plus près.
(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.)
D'accord, mon algo tout simple n'est pas un foudre de guerre.
Michael
James Kanze
On Jun 26, 10:25 am, Michael DOUBEZ wrote:
[...]
, KMP ou mon expression rationnelle O(N), et BM O(N/M).
Au meilleur cas je suppose.
KMP génère l'équivalent d'un DFA. C'est donc O(N), une fois le DFA construit. (Et le construire est assez simple, et c'est O(M).) Une expression rationnelle classique se laisse transcrire en DFA aussi, mais la transcription peut prendre un certain temps.
Enfin, un O(N) est impressionnant. Je regarderai KMP de plus près.
BM est encore mieux, c'est O(N/M). Si M n'est pas trop petit, il peut être très, très vite.
-- James Kanze (Gabi Software) 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 26, 10:25 am, Michael DOUBEZ <michael.dou...@free.fr> wrote:
[...]
, KMP ou mon expression
rationnelle O(N), et BM O(N/M).
Au meilleur cas je suppose.
KMP génère l'équivalent d'un DFA. C'est donc O(N), une fois le
DFA construit. (Et le construire est assez simple, et c'est
O(M).) Une expression rationnelle classique se laisse
transcrire en DFA aussi, mais la transcription peut prendre un
certain temps.
Enfin, un O(N) est impressionnant. Je regarderai KMP de plus près.
BM est encore mieux, c'est O(N/M). Si M n'est pas trop petit, il
peut être très, très vite.
--
James Kanze (Gabi Software) 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
, KMP ou mon expression rationnelle O(N), et BM O(N/M).
Au meilleur cas je suppose.
KMP génère l'équivalent d'un DFA. C'est donc O(N), une fois le DFA construit. (Et le construire est assez simple, et c'est O(M).) Une expression rationnelle classique se laisse transcrire en DFA aussi, mais la transcription peut prendre un certain temps.
Enfin, un O(N) est impressionnant. Je regarderai KMP de plus près.
BM est encore mieux, c'est O(N/M). Si M n'est pas trop petit, il peut être très, très vite.
-- James Kanze (Gabi Software) 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
espie
In article , James Kanze wrote:
BM est encore mieux, c'est O(N/M). Si M n'est pas trop petit, il peut être très, très vite.
Dans la realite, BM ne presente que tres peu d'interet... les limitations du materiel font que, de toutes facons, on se tape les acces a la plupart des cases memoire, et comme ce sont ces acces qui dominent le temps de calcul sur la plupart des architectures actuelles...
mais je t'accorde qu'en theorie, c'est un tres bel algo....
In article <1182881058.761929.176000@q75g2000hsh.googlegroups.com>,
James Kanze <james.kanze@gmail.com> wrote:
BM est encore mieux, c'est O(N/M). Si M n'est pas trop petit, il
peut être très, très vite.
Dans la realite, BM ne presente que tres peu d'interet... les limitations
du materiel font que, de toutes facons, on se tape les acces a la plupart
des cases memoire, et comme ce sont ces acces qui dominent le temps de
calcul sur la plupart des architectures actuelles...
mais je t'accorde qu'en theorie, c'est un tres bel algo....
BM est encore mieux, c'est O(N/M). Si M n'est pas trop petit, il peut être très, très vite.
Dans la realite, BM ne presente que tres peu d'interet... les limitations du materiel font que, de toutes facons, on se tape les acces a la plupart des cases memoire, et comme ce sont ces acces qui dominent le temps de calcul sur la plupart des architectures actuelles...
mais je t'accorde qu'en theorie, c'est un tres bel algo....
Sylvain
James Kanze wrote on 26/06/2007 09:10:
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).
j'ai réagi un peu vite à la conclusion "ne pas voir pourquoi se serait plus lent"
j'avais décroché du fil lors des considérations "depuis la fin ou depuis le début" (sachant que KMP commence au début et BM depuis la fin, les 2 sont clairement possibles) et je n'ai que survolé les derniers posts.
mon point était qu'une recherche mono pattern (ie un litéral) est assez "classique" et ne devrait pas donner lieu à un algo (bcp) plus lent que l'existant; je notais qu'une recherche multi-patterns ("extended string" ou expression régulière) peut (selon plein de params dont l'archi., CPU, L1, ...) donner des algos aux perfs bcp plus dissemblables.
mais, en effet, je sens bien comme une erreur d'appréciation dans mon point précédent.
Sylvain.
James Kanze wrote on 26/06/2007 09:10:
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).
j'ai réagi un peu vite à la conclusion "ne pas voir pourquoi se serait
plus lent"
j'avais décroché du fil lors des considérations "depuis la fin ou depuis
le début" (sachant que KMP commence au début et BM depuis la fin, les 2
sont clairement possibles) et je n'ai que survolé les derniers posts.
mon point était qu'une recherche mono pattern (ie un litéral) est assez
"classique" et ne devrait pas donner lieu à un algo (bcp) plus lent que
l'existant; je notais qu'une recherche multi-patterns ("extended string"
ou expression régulière) peut (selon plein de params dont l'archi., CPU,
L1, ...) donner des algos aux perfs bcp plus dissemblables.
mais, en effet, je sens bien comme une erreur d'appréciation dans mon
point précédent.
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).
j'ai réagi un peu vite à la conclusion "ne pas voir pourquoi se serait plus lent"
j'avais décroché du fil lors des considérations "depuis la fin ou depuis le début" (sachant que KMP commence au début et BM depuis la fin, les 2 sont clairement possibles) et je n'ai que survolé les derniers posts.
mon point était qu'une recherche mono pattern (ie un litéral) est assez "classique" et ne devrait pas donner lieu à un algo (bcp) plus lent que l'existant; je notais qu'une recherche multi-patterns ("extended string" ou expression régulière) peut (selon plein de params dont l'archi., CPU, L1, ...) donner des algos aux perfs bcp plus dissemblables.
mais, en effet, je sens bien comme une erreur d'appréciation dans mon point précédent.
Sylvain.
Sylvain
James Kanze wrote on 26/06/2007 20:04:
BM est encore mieux, c'est O(N/M). Si M n'est pas trop petit, il peut être très, très vite.
tes chiffres sont un peu étonnant, soit on n'a pas la même littérature soit Boyer et Moore ont revisité leur algo ?!...
depuis que les expressions régulières non-régulières (c) sont devenues indispensables, une tentative de moteur générique (PCRE: perl compatible regex engine) est sortie, avec notamment des wrappers C++ [1].
l'un de vous a-t-il testé ? (si Boost::regex est basé sur cette lib., ne tapez pas trop fort, j'avoue a priori mon ignorance de Boost).
BM est encore mieux, c'est O(N/M). Si M n'est pas trop petit, il
peut être très, très vite.
tes chiffres sont un peu étonnant, soit on n'a pas la même littérature
soit Boyer et Moore ont revisité leur algo ?!...
depuis que les expressions régulières non-régulières (c) sont devenues
indispensables, une tentative de moteur générique (PCRE: perl compatible
regex engine) est sortie, avec notamment des wrappers C++ [1].
l'un de vous a-t-il testé ?
(si Boost::regex est basé sur cette lib., ne tapez pas trop fort,
j'avoue a priori mon ignorance de Boost).
BM est encore mieux, c'est O(N/M). Si M n'est pas trop petit, il peut être très, très vite.
tes chiffres sont un peu étonnant, soit on n'a pas la même littérature soit Boyer et Moore ont revisité leur algo ?!...
depuis que les expressions régulières non-régulières (c) sont devenues indispensables, une tentative de moteur générique (PCRE: perl compatible regex engine) est sortie, avec notamment des wrappers C++ [1].
l'un de vous a-t-il testé ? (si Boost::regex est basé sur cette lib., ne tapez pas trop fort, j'avoue a priori mon ignorance de Boost).
BM est encore mieux, c'est O(N/M). Si M n'est pas trop petit, il peut être très, très vite.
Dans la realite, BM ne presente que tres peu d'interet... les limitations du materiel font que, de toutes facons, on se tape les acces a la plupart des cases memoire, et comme ce sont ces acces qui dominent le temps de calcul sur la plupart des architectures actuelles...
mais je t'accorde qu'en theorie, c'est un tres bel algo....
Tiens, je n'avais pas pensé à cet aspect-là. La dernière fois que je m'y suis penché, c'était il y a une vingtaine d'années. Et alors, BM a fait une différence notable. Mais effectivement, à l'époque, il n'y avait pas de mémoire cache.
Je pense que même aujourd'hui, on doit y gagner un peu, du fait qu'on passe moins de fois dans la boucle, et qu'on exécute donc moins d'instructions machine. Mais c'est sûr que la différence sera moindre qu'elle ne l'était.
-- James Kanze (GABI Software) 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 26, 9:15 pm, e...@lain.home (Marc Espie) wrote:
In article <1182881058.761929.176...@q75g2000hsh.googlegroups.com>,
James Kanze <james.ka...@gmail.com> wrote:
BM est encore mieux, c'est O(N/M). Si M n'est pas trop petit, il
peut être très, très vite.
Dans la realite, BM ne presente que tres peu d'interet... les limitations
du materiel font que, de toutes facons, on se tape les acces a la plupart
des cases memoire, et comme ce sont ces acces qui dominent le temps de
calcul sur la plupart des architectures actuelles...
mais je t'accorde qu'en theorie, c'est un tres bel algo....
Tiens, je n'avais pas pensé à cet aspect-là. La dernière fois
que je m'y suis penché, c'était il y a une vingtaine d'années.
Et alors, BM a fait une différence notable. Mais effectivement,
à l'époque, il n'y avait pas de mémoire cache.
Je pense que même aujourd'hui, on doit y gagner un peu, du fait
qu'on passe moins de fois dans la boucle, et qu'on exécute donc
moins d'instructions machine. Mais c'est sûr que la différence
sera moindre qu'elle ne l'était.
--
James Kanze (GABI Software) 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
BM est encore mieux, c'est O(N/M). Si M n'est pas trop petit, il peut être très, très vite.
Dans la realite, BM ne presente que tres peu d'interet... les limitations du materiel font que, de toutes facons, on se tape les acces a la plupart des cases memoire, et comme ce sont ces acces qui dominent le temps de calcul sur la plupart des architectures actuelles...
mais je t'accorde qu'en theorie, c'est un tres bel algo....
Tiens, je n'avais pas pensé à cet aspect-là. La dernière fois que je m'y suis penché, c'était il y a une vingtaine d'années. Et alors, BM a fait une différence notable. Mais effectivement, à l'époque, il n'y avait pas de mémoire cache.
Je pense que même aujourd'hui, on doit y gagner un peu, du fait qu'on passe moins de fois dans la boucle, et qu'on exécute donc moins d'instructions machine. Mais c'est sûr que la différence sera moindre qu'elle ne l'était.
-- James Kanze (GABI Software) 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
Mathias Gaunard
depuis que les expressions régulières non-régulières (c) sont devenues indispensables, une tentative de moteur générique (PCRE: perl compatible regex engine) est sortie, avec notamment des wrappers C++ [1].
l'un de vous a-t-il testé ? (si Boost::regex est basé sur cette lib., ne tapez pas trop fort, j'avoue a priori mon ignorance de Boost).
Boost.regex n'est bien sûr pas basé sur PCRE. Ni boost.xpressive d'ailleurs.
Les deux permettant chacun plus que PCRE, surtout xpressive.
depuis que les expressions régulières non-régulières (c) sont devenues
indispensables, une tentative de moteur générique (PCRE: perl compatible
regex engine) est sortie, avec notamment des wrappers C++ [1].
l'un de vous a-t-il testé ?
(si Boost::regex est basé sur cette lib., ne tapez pas trop fort,
j'avoue a priori mon ignorance de Boost).
Boost.regex n'est bien sûr pas basé sur PCRE.
Ni boost.xpressive d'ailleurs.
Les deux permettant chacun plus que PCRE, surtout xpressive.
depuis que les expressions régulières non-régulières (c) sont devenues indispensables, une tentative de moteur générique (PCRE: perl compatible regex engine) est sortie, avec notamment des wrappers C++ [1].
l'un de vous a-t-il testé ? (si Boost::regex est basé sur cette lib., ne tapez pas trop fort, j'avoue a priori mon ignorance de Boost).
Boost.regex n'est bien sûr pas basé sur PCRE. Ni boost.xpressive d'ailleurs.
Les deux permettant chacun plus que PCRE, surtout xpressive.
