boost :: tokenizer vs boost :: split

Question

Sto cercando di analizzare una stringa C++ su ogni carattere '^' in un token vettoriale. Ho sempre usato il metodo boost :: split, ma ora sto scrivendo codice critico delle prestazioni e vorrei sapere quale offre prestazioni migliori.

Ad esempio:

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); 

quale sarebbe offrire prestazioni migliori e perché?

Grazie.

Answer 1

La scelta migliore dipende da alcuni fattori. Se hai solo bisogno di scansionare i token una volta, allora boost :: tokenizer è una buona scelta sia in runtime che in spazio (i vettori di token possono occupare molto spazio, a seconda dei dati di input).

Se hai intenzione di scansionare i token spesso, o hai bisogno di un vettore con un accesso casuale efficiente, allora il boost :: split in un vettore potrebbe essere l'opzione migliore.

Ad esempio, in "A^B^C^...^Z" stringa di input in cui i token sono 1 byte in lunghezza, il metodo boost::split/vector<string> consumerà almeno 2 * N-1 byte. Con il modo in cui le stringhe vengono archiviate nella maggior parte delle implementazioni STL, è possibile calcolarlo prendendo più di 8 volte quel valore. Memorizzare queste stringhe in un vettore è costoso in termini di memoria e tempo.

ho fatto un rapido test sulla mia macchina e un modello simile con 10 milioni di gettoni guardato come questo:

• boost :: split = 2.5s e ~ 620MB
• boost :: tokenizer = 0.9s e 0MB

Se stai solo facendo una sola volta s può delle pedine, quindi chiaramente il tokenizer è migliore. Tuttavia, se stai distruggendo una struttura che desideri riutilizzare durante il ciclo di vita dell'applicazione, è preferibile disporre di un vettore di token.

Se si desidera utilizzare il percorso vettoriale, si consiglia di non utilizzare un vector<string>, ma un vettore di string :: iterators. Basta distruggere un paio di iteratori e mantenere la tua grande stringa di token come riferimento. Per esempio:

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; 
} 

Questa versione migliorata prende 1.6s e 390MB sullo stesso server e di prova. E, meglio di tutti i sovraccarichi di memoria di questo vettore è lineare con il numero di token - non dipende in alcun modo dalla lunghezza dei token, mentre uno std::vector<string> memorizza ciascun token.

Answer 2

Trovo risultati piuttosto diversi utilizzando clang++ -O3 -std=c++11 -stdlib=libc++.

In primo luogo ho estratto un file di testo con ~ parole 470K separate da virgole, senza ritorni a capo in una stringa gigante, in questo modo:

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(); 

Poi ho eseguito vari test cronometrati memorizzare i risultati in un vettore di pre-sized eliminato tra le esecuzioni, per esempio,

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(); 

    ... 
} 

per riferimento, il timer è proprio questo:

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_; 
}; 

Ho anche eseguito il clock di una singola iterazione (nessun vettore). Ecco i risultati:

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 

Il tokenizzatore è tanto più lento rispetto split, la figura di un iterazione non include anche la copia stringa:

{ 
    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)); 
    } 
} 

conclusione univoca: utilizzare split.

Answer 3

Potrebbe dipendere dalla versione di boost e dalla modalità di utilizzo.

Abbiamo riscontrato un problema di prestazioni in alcune logiche che utilizzavano boost :: split 1.41.0 per gestire migliaia o centinaia di migliaia di stringhe più piccole (previste meno di 10 token). Quando ho eseguito il codice tramite un analizzatore di prestazioni, abbiamo riscontrato che una sorprendente quantità di tempo pari al 39% è stata spesa in boost :: split.

Abbiamo provato alcune semplici "correzioni" che non hanno influenzato materialmente le prestazioni del tipo "sappiamo che non abbiamo più di 10 elementi per ogni passaggio, quindi preimpostare il vettore su 10 elementi".

Dato che in realtà non avevamo bisogno del vettore e potevamo semplicemente iterare i token e realizzare lo stesso lavoro, abbiamo modificato il codice per boost :: tokenize e la stessa sezione di codice rilasciata a < 1% di runtime.