En C++, ¿cuál es la manera más rápida de reemplazar todas las ocurrencias de una subcadena dentro de una cadena con otra cadena?

Question

Estoy buscando la manera más eficiente (en términos de "más rápido") para reemplazar todas las apariciones de una subcadena dentro de una cadena con otra cadena. Todo lo que ocurrió con el hasta ahora es:

std::string StringReplaceAll(const std::string &cstSearch, const std::string &cstReplace, const std::string &cstSubject) 
{ 
    if(cstSearch.length() > cstSubject.length() || cstSearch == cstReplace || cstSubject.empty() || cstSearch.empty() || cstSubject.find(cstSearch) == std::string::npos) 
    { 
     return cstSubject; 
    } 

    std::ostringstream         ossReturn; 
    std::string::const_iterator       ci(cstSubject.cbegin()); 
    const std::string::const_iterator::difference_type ciFindSize(std::distance(cstSearch.cbegin(), cstSearch.cend())); 

    for(std::string::const_iterator ciNow; (ciNow = std::search(ci, cstSubject.cend(), cstSearch.cbegin(), cstSearch.cend())) != cstSubject.cend(); ci = ciNow) 
    { 
     std::copy(ci, ciNow, std::ostreambuf_iterator<char> (ossReturn)); 
     std::copy(cstReplace.cbegin(), cstReplace.cend(), std::ostreambuf_iterator<char> (ossReturn)); 
     std::advance(ciNow, ciFindSize); 
    } 

    std::copy(ci, cstSubject.cend(), std::ostreambuf_iterator<char> (ossReturn)); 

    return ossReturn.str(); 
} 

... y ésta es la forma (!!!) demasiado lento para mis necesidades :-(

Mirando hacia adelante a aprender de ustedes !

Answer 1

en primer lugar, me gustaría usar std::string, en lugar de std::ostringstream, para construir los resultados;. std::ostringstream es para el formato, y no hay formato que hacer aquí Aparte de eso, usted tiene básicamente el algoritmo correcto; utilizando std::search para encontrar donde el n ext reemplazo debe hacerse. Que haría uso de un bucle while para hacer las cosas un poco más legible , lo que da:

std::string 
replaceAll(std::string const& original, 
      std::string const& before, 
      std::string const& after) 
{ 
    std::string retval; 
    std::string::const_iterator end  = original.end(); 
    std::string::const_iterator current = original.begin(); 
    std::string::const_iterator next = 
      std::search(current, end, before.begin(), before.end()); 
    while (next != end) { 
     retval.append(current, next); 
     retval.append(after); 
     current = next + before.size(); 
     next = std::search(current, end, before.begin(), before.end()); 
    } 
    retval.append(current, next); 
    return retval; 
} 

(Tenga en cuenta que el uso de std::string::append será más rápido que el uso de std::copy; la cadena sabe cuántos se debe agregar, y puede cambie el tamaño de la cadena según corresponda.)

Después, sería trivial detectar el caso especial en el que no hay nada que reemplazar y devolver inmediatamente la cadena inicial; Hay que pueden tener algunas mejoras al usar std::string::reserve como . (Si before y after tienen la misma longitud, retval.reserve(original.size()) es una victoria clara. Incluso si no lo hacen, podría ser una victoria. En cuanto a contar por primera vez el número de sustituciones, entonces calcular exactamente el tamaño final, Don No lo sé. Tendrás que medir con tus casos de uso reales para averiguarlo.)

Answer 2

Pregunté sobre esto mismo al http://hardforum.com/showthread.php?t=979477 años atrás.

No recuerdo todo muy bien, pero el siguiente código en el comentario era #31 y yo creo que fue más rápido que mis otros intentos (pero no más rápido que el ejemplo metered_string MikeBlas'):

#include <iostream> 
#include <string> 
#include <algorithm> 
#include <iterator> 
#include <sstream> 

using namespace std; 

inline string replaceAll(const string& s, const string& f, const string& r) { 
    if (s.empty() || f.empty() || f == r || f.size() > s.size() || s.find(f) == string::npos) { 
     return s; 
    } 
    ostringstream build_it; 
    typedef string::const_iterator iter; 
    iter i(s.begin()); 
    const iter::difference_type f_size(distance(f.begin(), f.end())); 
    for (iter pos; (pos = search(i , s.end(), f.begin(), f.end())) != s.end();) { 
     copy(i, pos, ostreambuf_iterator<char>(build_it)); 
     copy(r.begin(), r.end(), ostreambuf_iterator<char>(build_it)); 
     advance(pos, f_size); 
     i = pos; 
    } 
    copy(i, s.end(), ostreambuf_iterator<char>(build_it)); 
    return build_it.str(); 
} 

int main() { 
    const string source(20971520, 'a'); 
    const string test(replaceAll(source, "a", "4")); 
} 

Vea el hilo para más ejemplos y mucha discusión.

Si mal no recuerdo, fue muy fácil hacer las cosas más rápido que boost_all.

Aquí hay una versión más clara C++ 0x:

#include <string> 
#include <algorithm> 
#include <iterator> 
#include <sstream> 
#include <ostream> 
using namespace std; 

string replace_all_copy(const string& s, const string& f, const string& r) { 
    if (s.empty() || f.empty() || f == r || f.size() > s.size()) { 
     return s; 
    } 
    ostringstream buffer; 
    auto start = s.cbegin(); 
    while (true) { 
     const auto end = search(start , s.cend(), f.cbegin(), f.cend()); 
     copy(start, end, ostreambuf_iterator<char>(buffer)); 
     if (end == s.cend()) { 
      break; 
     } 
     copy(r.cbegin(), r.cend(), ostreambuf_iterator<char>(buffer)); 
     start = end + f.size(); 
    } 
    return buffer.str(); 
} 

int main() { 
    const string s(20971520, 'a'); 
    const string result = replace_all_copy(s, "a", "4"); 
} 

// g++ -Wall -Wextra replace_all_copy.cc -o replace_all_copy -O3 -s -std=c++0x 

Answer 3

prueba este.

template<class T> inline void Replace(T& str, const T& str1, const T& str2) 
{ 
    const T::size_type str2Size(str2.size()); 
    const T::size_type str1Size(str1.size()); 

    T::size_type n = 0; 
    while (T::npos != (n = str.find(str1, n))) { 
     str.replace(n, str1Size, str2); 
     n += str2Size; 
    } 
} 

std::string val(L"abcabcabc"); 
Replace(val, L"abc", L"d"); 

Answer 4

creo std :: búsqueda utiliza un algoritmo trivial, al menos the reference estados de la complejidad de un algoritmo de coincidencia de cadenas naiive. Si lo reemplaza por una implementación de Boyer-Moore, podrá ver aumentos de rendimiento significativos.

Aparte de eso, usted depende en gran medida de las buenas optimizaciones del compilador.Al devolver la cadena en lugar de pasar un resultado de cadena *, provoca una copia innecesaria del resultado. Sin embargo, los compiladores pueden ayudarlo allí. Pero solo para asegurarse de que puede intentar pasar un puntero al resultado como argumento y anexarlo a esa cadena. Sin embargo, el intercambio de std :: search por una implementación de un algoritmo no trivial (boyer-moore como se mencionó anteriormente o knuth-morris-pratt) debería tener un impacto que es mayor en varios órdenes de magnitud en comparación con el ajuste del mecanismo de retorno.

Answer 5

Propongo un paso de optimización: haga un pase preliminar para verificar si hay algo que reemplazar en absoluto. Si no hay nada que reemplazar, solo regrese y evite asignar memoria y copiar.

Answer 6

Me pareció que éste sea más rápido:

typedef std::string String; 

String replaceStringAll(String str, const String& old, const String& new_s) { 
    if(!old.empty()){ 
     size_t pos = str.find(old); 
     while ((pos = str.find(old, pos)) != String::npos) { 
      str=str.replace(pos, old.length(), new_s); 
      pos += new_s.length(); 
     } 
    } 
    return str; 
} 

Una comparación con James kanzes replaceAll función:

replaceAll  : 28552 
replaceStringAll: 33518 
replaceAll  : 64541 
replaceStringAll: 14158 
replaceAll  : 20164 
replaceStringAll: 13651 
replaceAll  : 11099 
replaceStringAll: 5650 
replaceAll  : 23775 
replaceStringAll: 10821 
replaceAll  : 10261 
replaceStringAll: 5125 
replaceAll  : 10283 
replaceStringAll: 5374 
replaceAll  : 9993 
replaceStringAll: 5664 
replaceAll  : 10035 
replaceStringAll: 5246 
replaceAll  : 8570 
replaceStringAll: 4381 

están referidos en nanosegundos con std::chrono::high_resolution_clock