boost :: tokenizer vs boost :: bölme

Question

Her '^' karakterinde bir C++ dizesini bir vektör jetonuna ayrıştırmaya çalışıyorum. Boost :: split yöntemini her zaman kullandım, ancak şimdi performans kritik kod yazıyor ve hangisinin daha iyi performans verdiğini bilmek istiyorum. biri iyi performans ve neden verecekti

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

: Örneğin

?

Teşekkürler.

Answer 1

En iyi seçim birkaç faktöre bağlıdır. Jetonları bir kez taramanız gerekiyorsa, boost :: tokenizer hem çalışma zamanı hem de alan performansında iyi bir seçimdir (jetonun vektörleri giriş verilerine bağlı olarak çok fazla yer kaplayabilir.)

Eğer tokenleri sık sık tarayacaksanız veya verimli rastgele erişime sahip bir vektöre ihtiyacınız varsa, o zaman bir vektöre bölünmüş olan boost ::, daha iyi bir seçenek olabilir.

Örneğin, 'de "A^B^C^...^Z" belirteçleri uzunluğu 1-byte giriş dizesi, boost::split/vector<string> yöntem en az 2 * N-1 bayt tüketecektir. Yol dizeleri çoğu STL uygulamasında saklandığından, bu sayının 8 katından fazla olduğunu anlayabilirsiniz. Bu dizeleri bir vektörde saklamak bellek ve zaman açısından maliyetlidir. = 2.5s ve ~ 620MB

boost ::

• boost :: bölünmüş:
  Ben böyle görünüyordu benim makine ve 10 milyon jeton ile benzer bir desen ufak bir test koştum tokenizer = 0.9 s ve 0MB

sadece yapıyorsanız bir defalık ler Jetonları, sonra açıkça belirteci daha iyidir. Ancak, uygulamanızın ömrü boyunca yeniden kullanmak istediğiniz bir yapıya parçalanıyorsanız, bir belirteçler vektörüne sahip olmak tercih edilebilir.

Vektör rotasına gitmek isterseniz, vector<string> kullanmamanızı öneririm, ancak bunun yerine bir string :: iterators vektörünü öneririm. Sadece bir çift yineleyici içine parçalayın ve referans için büyük dizelerinizi dizgininizde tutun. Örneğin:

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

Bu gelişmiş versiyonu aynı sunucu ve test 1.6s ve 390MB sürer. Ve, bu vektörün tüm bellek yükünün en iyisi, belirteçlerin sayısı ile doğrusaldır - belirteçlerin uzunluğuna herhangi bir şekilde bağlı değildir, oysa her bir jetonu std::vector<string> depolar.

Answer 2

clang++ -O3 -std=c++11 -stdlib=libc++'u kullanarak oldukça farklı sonuçlar buluyorum.

Önce şöyle bir dev dizeye hiçbir satırsonu ile virgülle ayırarak ~ 470K sözlerle bir metin dosyası çıkarılan:

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

Sonra temizlenmiş bir ön büyüklüğünde vektör içine sonuçlarını saklamak çeşitli zamanlanmış testler yaptık

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

: koşular arasında, örneğin, referans için

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

    ... 
} 

, zamanlayıcı sadece bu olduğunu 210

Ayrıca, tek bir iterasyon (vektör yok) da çektim. İşte sonuçlar:

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

Kesin sonuç:: split kullanmak

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 

tokenizersplit daha yavaş çok olan, tek yineleme rakam bile dize kopyasını içermez.

Answer 3

Takviye sürümünüze ve nasıl çalıştığınıza bağlı olabilir.

Boost :: split 1.41.0 kullanarak, binlerce veya yüz binlerce küçük dizeyi (10 jetondan daha az beklenen) işlemek için kullanılan bazı mantıklarda performans sorunu yaşadık. Kodu bir performans analizörü ile çalıştırdığımda, şaşırtıcı bir şekilde% 39'luk bir oranın boost :: split'de harcanmış olduğunu gördük.

Performansı, "her geçişte 10'dan fazla öğe olmayacağımızı biliyoruz, bu nedenle vektörü 10 öğeye önceden ayarladığımızı" gibi malzeme üzerinde etkili olmayan bazı basit "düzeltmeler" denedik.

biz aslında vektör gerek yoktu ve sadece belirteçleri yineleme ve aynı işi başarabileceğimizi yana

, biz :: artırmak için kod değiştirildi tokenize ve kod aynı bölüm çalışma zamanının <% 1'e düştü.