Remplacement de chaine, Aparte

[ampholyte]

Hello,

Donc deja, je vais etre un peu sec mais:
preferer le C par rapport au C++ n est absolument pas justifie ici.
Qu il s agisse de gestion memoire ou de gestion de rapidite.

Si vous faites allusion aux char*, rien n empeche de gerer des char* en C++, encore faudrait-il justifier l overhead d un sizeof et le comportement de string.

Maintenant comme vous semblez a tout prix vouloir faire du C, pourquoi pas, mais evitons ces arguments ou alors comparons apres que des solutions comparables aient ete proposees.

C'est vrai que tu proposais une solution en C++, en même temps si cela fonctionne en C, l'implémentation en C++ ne devrait pas poser plus de problème que cela. Je suis plus à l'aise en C qu'en C++ soit dit en passant (d'où mon choix).

Enfin vous ne semblez pas vous preoccupez de l assignation d une telle structure, et de la modification de la premiere chaine...

Code: Tout sélectionner

mystring s("blabla");
mystring s2=s.replace("a","b");
//s2 reutilise la chaine utilisee par s.
s.inplaceReplace("aeff","feeee");
//s2 n est pas impacte par la modification de s


J ai pas dit que c est necessare, mais c est une question a se poser, ce genre de cas (ou la premiere chaine est modifiee) peut il arriver, si oui comment le gerer pour ne pas impacter les chaines qui se basent sur la premiere...

Personnellement je ne trouve pas que cela change grand chose. Au lieu de faire un realloc, on déclare un nouveau char* puis un calloc que l'on concatène au fur et à mesure ce qui rend les choses beaucoup plus simples.

Par ailleurs lorsque l'on parle de remplacer, implicitement cela signifie qu'on modifie la chaine principale, ce qui me semble être le cas le plus difficile.

[fatal_error]

Par ailleurs lorsque l'on parle de remplacer, implicitement cela signifie qu'on modifie la chaine principale, ce qui me semble être le cas le plus difficile.

normalement non. On ne doit pas modifier la chaine principale du moins, l utilisateur ne doit pas s en rendre compte. (cf mutable en C++). Dans la plupart des langages de programmation:
php str_replace
javascript replace
c++ replace
...
l objet/chaine qui propose la methode replace n est pas change. Par contre la chaine retournee, elle, est changee.

[Dlzlogic]

l objet/chaine qui propose la methode replace n est pas change. Par contre la chaine retournee, elle, est changee.

Je ne comprend pas ce que tu veux dire, si une chaine contient des mots remplacés, elle est changée quelque soit le langage.
La seule nuance qu'il pourrait y avoir, c'est si l'ancienne chaine existe toujours ou pas, et l'emplacement, mais dans tous les cas, l'utilisateur ne se rend compte de rien.
Par ailleurs, le C++, c'est du C avec des notion d'objet, de classe etc. en plus.
En d'autres termes, on peut écrire en C et le compiler en C++ (mais pas l'inverse).

[ampholyte]

normalement non. On ne doit pas modifier la chaine principale du moins, l utilisateur ne doit pas s en rendre compte. (cf mutable en C++). Dans la plupart des langages de programmation:
php str_replace
javascript replace
c++ replace
...
l objet/chaine qui propose la methode replace n est pas change. Par contre la chaine retournee, elle, est changee.

Bon en supposant que l'on ne touche pas à la chaine voici le prototype :

Code: Tout sélectionner

char *search_and_replace(const char *buffer, const char *search, const char *replace);

1) On récupère la taille de buffer => strlen => buffer_sz
On récupère la taille de search => strlen => search_sz
On récupère la taille de replace => strlen => replace_sz

2) On compte le nombre d'occurence search dans buffer => strstr => N occurences

3) On calcule la taille de la nouvelle chaine à construire => new_buffer_sz = buffer_sz - N * (search_sz - repllace_sz)

4) On alloue un char * de la taille new_buffer_sz + 1 ('\0') avec un calloc.

5) On boucle strstr et on concatène => strcat

On renvoit la nouvelle chaine (qu'il faudra free dans la suite).

[fatal_error]

je vais developper un peu parce que j'ai l'impression que tout le monde passe à côté.

Maintenant, qu'est-ce qu'on voit: on voit qu'on a alloué autant d'espace que de
patterns trouvés.
Enfin vous ne semblez pas vous preoccupez de l assignation d une telle structure, et de la modification de la premiere chaine...

On voudrait éviter de rallouer à chaque fois les caractères pour zzzz...., bref les sous chaines non touchées! et tant qu'à faire idem pour les sous-chaines remplacées!

//s2 reutilise la chaine utilisee par s.
s.inplaceReplace("aeff","feeee");
//s2 n est pas impacte par la modification de s

Ampholyte>
oui ta méthode marche, mais elle a deux inconvénients:
1 - tu alloues autant de fois que de remplacements ce qui est clairement pas le but des le premier poste
2 - tu alloues également toutes les séquences non matchées (idem qui sont pas à remplacer)

Grossièrement, ce que je sous entends, c'est quelque chose dans le style:

(L'implémentation peut évidemment être faite différemment, la gestion mémoire également.)

Code: Tout sélectionner

//defines a string
struct Range{
   char* beg;
   char* end;
}
struct mystring{
   mystring(char* data){_s=data;}
   mystring* replace(char* pattern, char* value){
      mystring* replaced = (mystring*)malloc(sizeof(mystring));
      //allocate replaced->_orderedString big enough..
      char* begin=data;
      while(matched=strstr(_s, pattern)){
         //create the orderedString
         replaced->_orderedString[i++] = range(begin, matched);
         begin=matched+strlen(pattern);
      }
      replaced->_replaceValue=value;
      return replaced;
   }
   const char*getEquivalentString(){
      size_t totalSize = 0;
      char* result;
      //allocate the string result big enough
      //and concatenate each string stored in orderedString
      for(int i=0; i < orderedStringSize; ++i){
         result=strncat(result, orderedString[i], orderedString[i].end - orderedString[i].beg);
         result=strcat(result, _replaceValue);//only now we replace the matching
      }
   return result;
   }



   char* _s;
   /* only used for mystring which has been created by replace call */
   Range _orderedString[];
   size_t orderedStringSize;
   char* _replaceValue;
}


L'idée c'est que tant que l'utilisateur n'essaie pas d'accéder aux internal de mystring, idem qu'il utilise des mystring, il va grossièrement manipuler toujours la première chaine passée en paramètre.

Ici ya plein de problèmes: si le premier mystring est modifié, le second aussi alors qu'on veut pas..
le premier mystring a pas besoin de orderedString[]...
si on fait un replace sur le second mystring, il faut pas utiliser _s, mais l'équivalent qu'on a storé dans _orderedString, etc...

[joel76]

Bonjour

Je me suis amusé à faire un test avec mon algo et le replace de C++ il n'y a pas photo : dans un fichier
de 100 000 lignes de "blabla truc blablabla machin blabla", je remplace les "blabla" par des "gnagnagna".
Pour simplement le traitement de la chaîne je passe de 0,02s en C à 52,12 s en C++.
les algos :
En C++ (on peut sans doute faire beaucoup mieux, je ne conais pas le C++)

Code: Tout sélectionner

string my_replace(string src)
{
    string::size_type pos = 0;
    while ( (pos = src.find(in, pos)) != string::npos )
   {
      src.replace( pos, in.size(), out );
      pos++;
    }
   return src;
}


en C (c'est celui que j'avais proposé avec quelques améliorations, en tenant compte des remarques d' ampholyte)

Code: Tout sélectionner

char *replace(char *buf)
{
   int i = 0;
   int len, new_len;
   int state = 0;
   int start, k;
   int nb = 0;
   char c;
   char in_src = 0;
   char *ret;
   size_t len_src = strlen(src);
   size_t len_but = strlen(but);

   while(c = buf[i])
   {
      switch (state)
      {
      case 0 :
         if (c == src[in_src])
         {
            state = 1;
            start = i;
            in_src++;
         }
         break;
      case 1 :
         if (c != src[in_src])
         {
            // on a trouvé le mot
            if (src[in_src] == 0)
            {
               buf[start] = -1;
               nb++;
            }
            state = 0;
            in_src = 0;
         }
         else
            in_src++;
      }
      i++;
   }
   if (state == 1 && src[in_src] == 0)
   {
      buf[start] = -1;
      nb++;
   }
   
   // calcule de la longeur de la nouvelle chaine
   len = i;
   new_len = len + nb * (len_but - len_src)+1;


   if ((ret = calloc(new_len, sizeof(char))) == NULL)
   {
      puts("pb malloc");
      return ret;
   }
   for (i = k = 0; buf[i] != 0; i++, k++)
   {
      if (buf[i] == -1)
      {
         strcpy(&ret[k], but);
         buf[i] = src[0];
         i += len_src-1;
         k += len_but-1;
      }
      else
         ret[k] = buf[i];
   }
   ret[k] = 0;
   return ret;
}

[fatal_error]

C'est pas tellement comparable parce que :
on sait pas c'est quoi ton appel à la fonction,
c'est même pas les mêmes algorithmes,
on connait pas tes options de compilation.

par exemple avec le code suivant en O3, g++ 4.6

Code: Tout sélectionner

#include
#include
#include "Timer.hpp"
std::string replace(
    const std::string& in,
    const std::string &iPattern,
    const std::string &iReplace){
  std::vector v;
 
  for(size_t ind=0;ind!=std::string::npos;ind=in.find(iPattern,ind)){
    v.push_back(ind++);
  }
  size_t pos=0;
  size_t endPos=0;
  std::string replaced;
  size_t totalLength=in.size()+v.size()*(iReplace.size()-iPattern.size());
  replaced.reserve(totalLength);
  for(size_t i=0;i<v.size(); ++i){
    endPos=v[i];
    std::string s = in.substr(pos, endPos-pos);
    pos=endPos+iPattern.size();
    replaced+=s;
    replaced+=iReplace;
  }
//  std::cout<<"length="<<replaced.size()<<"|"<<totalLength<<std::endl;
  return replaced;
}
int main()
{
  Timer timer;
  std::string s("blabla truc blablabla machin blabla");
  timer.tic();
  for(size_t i=0;i<100000;++i){
    replace(s,"blabla","gnagnagna");
  }
  timer.toc("end");
  return 0;
}



je mets 0.101s
(je dis pas que c'est mieux qu'en C, je dis juste que 52s, faut pas déconner :we: et qu'aussi il faudrait peut etre comparer à algorithme équivalent..)

Toujours est-il que se confronter au problème de la mémoire reste peut-être plus intéressant!

[Dlzlogic]

Bonsoir, juste un petit commentaire.
Le but du C++ évolué est de faciliter le travail du programmeur, au dépend de tout ce qu'on veut.
Les tests comparatifs en matière d'exécution entre le C et le C++ sont toujours sans appel. Le problème n'est pas de savoir si c'est "mieux en C" mais de savoir ce qu'on cherche, la facilité de programmation (après un long apprentissage) ou l'efficacité du binaire résultat.

[fatal_error]

Code: Tout sélectionner

J'avais juste envie de prouver que mon code C était meilleur que la basique boucle utilisant le find et le replace de C++

ben oui et non.
Si tu parles en terme de rapidité, ouais, peut-être. Encore que je mets 0.05s...

Code: Tout sélectionner

int main()
{
  Timer timer;
  std::ifstream in("/home/BOBMORAN/workspace/c++/perfReplace/tests/data/fileToReplace.txt");
  std::string s((std::istreambuf_iterator(in)), std::istreambuf_iterator());
  timer.tic();
  replace(s,"blabla","gnagnagna");
  timer.toc("end");
  return 0;
}

bref je crois que ces petits centiemes, ils sont plutot gagnés sur l'algorithmie et la gestion des données que le langage...

[joel76]

@fatal_error >> Avec Visual 2010, j'ai testé ton code C++ et j'ai une erreur en mode debug.

Exception non gérée à 0x7581c41f dans cplusplus_str_replace.exe*:
Exception Microsoft C++*: std::bad_alloc à l'emplacement mémoire 0x003ee290..

Code: Tout sélectionner

std::string replace(
    const std::string& in,
    const std::string &iPattern,
    const std::string &iReplace)
{
  std::vector v;
 
  for(size_t ind=0;ind!=std::string::npos;ind=in.find(iPattern,ind))
  {
    v.push_back(ind++);
  }
  std::cout<< "passed " << v.size() << endl;
  size_t pos=0;
  size_t endPos=0;
  std::string replaced;
  size_t totalLength=in.size()+v.size()*(iReplace.size()-iPattern.size()) +1 ;
  replaced.reserve(totalLength);
  std::cout<< "passed " << totalLength << endl;
  for(size_t i=0;i<v.size(); ++i)
  {
    endPos=v[i];
    std::string s = in.substr(pos, endPos-pos);
    pos=endPos+iPattern.size();
    replaced+=s;
    replaced+=iReplace;
  }
  std::cout<<"length="<<replaced.size()<<"|"<<totalLength<<std::endl;
  return replaced;
}

Elle se produit dans la deuxième boucle for(size_t ...

[fatal_error]

oui c'est parce que j'ai pas avancé l'index de iPatternSize...

Code: Tout sélectionner

  for(size_t ind=0;ind!=std::string::npos;ind=in.find(iPattern,ind)){
    v.push_back(ind);
    ind+=iPattern.size();
  }

mais ca valait pas le coup de poster le code pour ce détail :]

edit: pdt que jy suis, avec une construction de string en moins...

Code: Tout sélectionner

std::string replace(
    const std::string& in,
    const std::string &iPattern,
    const std::string &iReplace){
  std::vector v;
  v.reserve(in.size()/2);
  size_t patternLength=iPattern.size();
  for(size_t ind=0;ind!=std::string::npos;ind=in.find(iPattern,ind)){
    v.push_back(ind);
    ind+=patternLength;
  }
  size_t pos=0;
  size_t endPos=0;
  size_t vSize=v.size();
  std::string replaced;
  size_t totalLength=in.size()+vSize*(iReplace.size()-patternLength);
  replaced.reserve(totalLength);
  for(size_t i=0;i<vSize; ++i){
    endPos=v[i];
    replaced.append(&in[pos], endPos-pos).append(iReplace);
    pos=endPos+patternLength;
  }
  return replaced;
}


0.025s

[joel76]

OK maintenant, sur ma machine en mode release, on est 0,011s pour mon code et 0,019s pour ton code. C'est donc équivalent.

Par contre, si je passe à une chaîne 100 fois plus longue, je retrouve la même erreur de bad_alloc.

[fatal_error]

j intuite fortement que lerreur vient de v.reserve(in.size()/2);
1 700 000 avant == 1M7
x100 = 170M
=>allocation sur espace contigu de 85M...*sizeof(size_t) bytes

mais bon chui pas chez moi et de toute facon ca n a pas grand interet!

[fatal_error]

pour revenir au poste de 18h44,
je m'en sors avec un smart pointeur, quelqu'un a t il trouvé autre chose?

[fatal_error]

c'est bien beau, mais ca ne fait pas avancer le sujet :hum: .
Comme toutes tes interventions dans cette discussion :/

[Dlzlogic]

c'est bien beau, mais ca ne fait pas avancer le sujet :hum: .
Comme toutes tes interventions dans cette discussion :/

Tu veux que je t'écrive un fonction qui fait des remplacements, dis-le tout simplement.
Ou alors, il faut préciser le sujet, si il s'agit d'autre-chose.
La fonction de Joel, ma parait très bien, mais naturellement, on peut tours chercher à optimiser.
On pourrait par exemple créer une liste chainée.

[joel76]

Je ne suis pas sur que les listes chaînées soient une bonne solution, elles nécessitent des appels mémoire qui seront pénalisant en temps d'exécution.

[Dlzlogic]

Je ne suis pas sur que les listes chaînées soient une bonne solution, elles nécessitent des appels mémoire qui seront pénalisant en temps d'exécution.

Mais c'est tout à fait possible, mais comme on cherche des propositions, j'en fais.
En fait j'ai pas compris où on en est, quel est le sujet. D'après ce que j'ai vu, ta solution est bonne.
De toute façon, si on veut améliorer, il faut faire des essais, une liste chainée permettrait de ne faire qu'un seul passage.
Petit complément, la tournure (relationnelle) de ce topic ne me donne pas vraiment envie de m'investir.