बढ़ावा :: टोकननाइज़र बनाम बढ़ावा :: विभाजन

Question

मैं प्रत्येक '^' चरित्र पर एक वेक्टर टोकन में एक सी ++ स्ट्रिंग को पार्स करने की कोशिश कर रहा हूं। मैंने हमेशा बूस्ट :: स्प्लिट विधि का उपयोग किया है, लेकिन अब मैं प्रदर्शन महत्वपूर्ण कोड लिख रहा हूं और जानना चाहता हूं कि कौन सा बेहतर प्रदर्शन देता है।

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

बनाम

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

कौन सा बेहतर प्रदर्शन और क्यों देना होगा:

उदाहरण के लिए

?

धन्यवाद।

Answer 1

सबसे अच्छा विकल्प कुछ कारकों पर निर्भर करता है। यदि आपको केवल टोकन को स्कैन करने की आवश्यकता है, तो बूस्ट :: टोकनेज़र रनटाइम और स्पेस प्रदर्शन दोनों में एक अच्छा विकल्प है (टोकन के वेक्टर इनपुट डेटा के आधार पर बहुत अधिक जगह ले सकते हैं।)

यदि आप अक्सर टोकन स्कैन करने जा रहे हैं, या कुशल यादृच्छिक पहुंच वाले वेक्टर की आवश्यकता है, तो बूस्ट :: वेक्टर में विभाजित बेहतर विकल्प हो सकता है।

उदाहरण के लिए, अपने में 'ए^बी^सी^...^Z "इनपुट स्ट्रिंग जहां टोकन लंबाई में 1-बाइट कर रहे हैं, boost::split/vector<string> विधि कम से कम 2 * एन -1 बाइट्स की खपत होगी। अधिकांश एसटीएल कार्यान्वयन में तारों को संग्रहीत करने के तरीके के साथ आप इसे 8x से अधिक लेते हुए समझ सकते हैं। एक वेक्टर में इन तारों को संग्रहीत करना स्मृति और समय के मामले में महंगा है।

मैं अपने मशीन और 10 लाख टोकन के साथ एक समान पैटर्न पर एक त्वरित परीक्षण भागा इस तरह देखा:

• बढ़ावा :: विभाजन = 2.5S और ~ 620MB
• बढ़ावा :: tokenizer = 0.9s और 0MB

तुम सिर्फ कर रहे हैं एक बार की रों टोकन के कर सकते हैं, तो स्पष्ट रूप से टोकननाइज़र बेहतर है। लेकिन, यदि आप किसी ऐसे ढांचे में घुसपैठ कर रहे हैं जिसे आप अपने आवेदन के जीवनकाल के दौरान पुन: उपयोग करना चाहते हैं, तो टोकन का वेक्टर होना पसंद किया जा सकता है।

यदि आप वेक्टर मार्ग जाना चाहते हैं, तो मैं vector<string> का उपयोग न करने की अनुशंसा करता हूं, लेकिन इसके बजाय स्ट्रिंग :: iterators का वेक्टर। बस इटेटरेटर की एक जोड़ी में फेंक दिया और संदर्भ के लिए टोकन की अपनी बड़ी स्ट्रिंग को चारों ओर रखें। उदाहरण के लिए:

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

इस उन्नत संस्करण एक ही सर्वर और परीक्षण पर 1.6s और 390MB लेता है। और, इस वेक्टर के सभी मेमोरी ओवरहेड में से सबसे अच्छा टोकन की संख्या के साथ रैखिक है - टोकन की लंबाई पर किसी भी तरह से निर्भर नहीं है, जबकि std::vector<string> प्रत्येक टोकन स्टोर करता है।

Answer 2

मुझे clang++ -O3 -std=c++11 -stdlib=libc++ का उपयोग करके अलग-अलग परिणाम मिलते हैं।

सबसे पहले मैं ~ 470k एक विशाल स्ट्रिंग में कोई नई-पंक्तियों के साथ अल्पविराम के द्वारा अलग शब्दों के साथ एक पाठ फ़ाइल निकाले, तो जैसे:

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

तब मैं विभिन्न समय को मंजूरी दे दी एक पूर्व आकार वेक्टर में परिणाम भंडारण परीक्षण भाग गया

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

: रन के बीच, उदाहरण के लिए,

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

    ... 
} 

संदर्भ के लिए, टाइमर सिर्फ इस है 210

मैंने एक एकल पुनरावृत्ति (कोई वेक्टर) भी देखा। यहाँ परिणाम हैं:

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

सुस्पष्ट निष्कर्ष: split का उपयोग

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 

tokenizer तो धीमीsplit की तुलना में ज्यादा है, एक यात्रा आंकड़ा भी स्ट्रिंग प्रतिलिपि शामिल नहीं है।

Answer 3

यह आपके बढ़ावा के संस्करण और आप कार्यक्षमता के आधार पर निर्भर हो सकता है।

हमारे पास कुछ तर्कों में एक प्रदर्शन समस्या थी जो हजारों या सैकड़ों हजारों छोटे तारों (10 टोकन से कम की उम्मीद) को संभालने के लिए बूस्ट :: स्प्लिट 1.41.0 का उपयोग कर रहा था। जब मैंने एक प्रदर्शन विश्लेषक के माध्यम से कोड चलाया तो हमने पाया कि बूस्ट :: स्प्लिट में एक आश्चर्यजनक 39% राशि खर्च की गई थी।

हमने कुछ सरल "फिक्सेस" की कोशिश की जो निष्पादन को प्रभावित नहीं करते थे "हम जानते हैं कि हमारे पास प्रत्येक पास 10 से अधिक आइटम नहीं हैं, इसलिए वेक्टर को 10 आइटम पर प्रीसेट करें"।

चूंकि हमें वास्तव में वेक्टर की आवश्यकता नहीं थी और केवल टोकन को फिर से सक्रिय कर सकते थे और उसी नौकरी को पूरा कर सकते थे, हमने कोड को टोकननाइज़ करने के लिए कोड बदल दिया और कोड का एक ही भाग < रनटाइम का 1% तक गिर गया।