boost :: tokenizer vs boost :: split

Question

Estoy tratando de analizar una cadena de C++ en cada carácter '^' en un vector tokens. Siempre he usado el método boost :: split, pero ahora estoy escribiendo código de rendimiento crítico y me gustaría saber cuál ofrece un mejor rendimiento.

Por ejemplo:

string message = "A^B^C^D"; 
vector<string> tokens; 
boost::split(tokens, message, boost::is_any_of("^")); 

vs

boost::char_separator<char> sep("^"); 
boost::tokenizer<boost::char_separator<char> > tokens(text, sep); 

Cuál sería dar un mejor rendimiento y por qué?

Gracias.

Answer 1

La mejor opción depende de algunos factores. Si solo necesita escanear los tokens una vez, el boost :: tokenizer es una buena opción tanto en tiempo de ejecución como en rendimiento de espacio (esos vectores de tokens pueden ocupar mucho espacio, dependiendo de los datos de entrada).

Si va a escanear los tokens a menudo, o necesita un vector con acceso aleatorio eficiente, entonces el boost :: dividir en un vector puede ser la mejor opción.

Por ejemplo, en su "A^B^C^...^Z" cadena de entrada donde las fichas son de 1 byte de longitud, el método boost::split/vector<string> consumirá al menos 2 * N-1 bytes. Con la forma en que se almacenan las cadenas en la mayoría de las implementaciones de STL, puede calcular que lleva más de 8x. Almacenar estas cadenas en un vector es costoso en términos de memoria y tiempo.

me hizo una prueba rápida en mi máquina y un patrón similar con 10 millones de fichas tenido este aspecto:

• impulso :: dividida = 2.5s y ~ 620MB
• impulso :: tokenizer = 0,9 segundos y 0 MB

Si acaba de hacer una sola vez s lata de los tokens, entonces claramente el tokenizer es mejor. Pero, si está destruyendo una estructura que desea volver a utilizar durante la vida de su aplicación, puede ser preferible tener un vector de tokens.

Si quiere ir por la ruta del vector, entonces le recomendaría no usar un vector<string>, sino un vector de cadena :: iteradores en su lugar. Solo haz trizas un par de iteradores y mantente cerca de tu gran cadena de tokens para referencia. Por ejemplo:

using namespace std; 
vector<pair<string::const_iterator,string::const_iterator> > tokens; 
boost::split(tokens, s, boost::is_any_of("^")); 
for(auto beg=tokens.begin(); beg!=tokens.end();++beg){ 
    cout << string(beg->first,beg->second) << endl; 
} 

Esta versión mejorada toma 1.6s y 390MB en el mismo servidor y prueba. Y, lo mejor de todo, la sobrecarga de memoria de este vector es lineal con el número de tokens, no depende de ninguna manera de la longitud de los tokens, mientras que un std::vector<string> almacena cada token.

Answer 2

Encuentro resultados bastante diferentes usando clang++ -O3 -std=c++11 -stdlib=libc++.

Primero extrae un archivo de texto con ~ palabras 470K separadas por comas, sin saltos de línea en una cadena gigante, así:

path const inputPath("input.txt"); 

filebuf buf; 
buf.open(inputPath.string(),ios::in); 
if (!buf.is_open()) 
    return cerr << "can't open" << endl, 1; 

string str(filesystem::file_size(inputPath),'\0'); 
buf.sgetn(&str[0], str.size()); 
buf.close(); 

Entonces me encontré con varias pruebas cronometradas almacenar los resultados en un vector de pre-tamaño aclarado entre las corridas, por ejemplo,

void vectorStorage(string const& str) 
{ 
    static size_t const expectedSize = 471785; 

    vector<string> contents; 
    contents.reserve(expectedSize+1); 

    ... 

    { 
     timed _("split is_any_of"); 
     split(contents, str, is_any_of(",")); 
    } 
    if (expectedSize != contents.size()) throw runtime_error("bad size"); 
    contents.clear(); 

    ... 
} 

Como referencia, el temporizador es sólo esto:

struct timed 
{ 
    ~timed() 
    { 
     auto duration = chrono::duration_cast<chrono::duration<double, ratio<1,1000>>>(chrono::high_resolution_clock::now() - start_); 

     cout << setw(40) << right << name_ << ": " << duration.count() << " ms" << endl; 
    } 

    timed(std::string name="") : 
     name_(name) 
    {} 


    chrono::high_resolution_clock::time_point const start_ = chrono::high_resolution_clock::now(); 
    string const name_; 
}; 

También cronometré una única iteración (sin vector). Aquí están los resultados:

Vector: 
           hand-coded: 54.8777 ms 
         split is_any_of: 67.7232 ms 
        split is_from_range: 49.0215 ms 
           tokenizer: 119.37 ms 
One iteration: 
           tokenizer: 97.2867 ms 
          split iterator: 26.5444 ms 
      split iterator back_inserter: 57.7194 ms 
       split iterator char copy: 34.8381 ms 

El señalizador es mucho más lenta de split, la figura de una sola iteración ni siquiera incluye la copia de cadena:

{ 
    string word; 
    word.reserve(128); 

    timed _("tokenizer"); 
    boost::char_separator<char> sep(","); 
    boost::tokenizer<boost::char_separator<char> > tokens(str, sep); 

    for (auto range : tokens) 
    {} 
} 

{ 
    string word; 

    timed _("split iterator"); 
    for (auto it = make_split_iterator(str, token_finder(is_from_range(',', ','))); 
     it != decltype(it)(); ++it) 
    { 
     word = move(copy_range<string>(*it)); 
    } 
} 

conclusión inequívoca: utilizar split.

Answer 3

Puede depender de su versión de refuerzo y cómo es la funcionalidad.

Tuvimos un problema de rendimiento en una lógica que usaba boost :: split 1.41.0 para manejar miles o cientos de miles de cadenas más pequeñas (se esperaban menos de 10 tokens). Cuando ejecuté el código a través de un analizador de rendimiento, descubrí que se gastaba un sorprendente 39% de tiempo en boost :: split.

Hemos intentado algunas "soluciones" simples que no afectaron materialmente el rendimiento como "sabemos que no tendremos más de 10 elementos en cada pase, así que preestablezca el vector en 10 elementos".

Dado que en realidad no necesitamos el vector y podríamos simplemente iterar los tokens y realizar el mismo trabajo, cambiamos el código para boost :: tokenize y la misma sección de código cayó a < 1% de tiempo de ejecución.