c++ - पायथन से सी++ में एक स्ट्रिंग धीमी गति क्यों विभाजित कर रहा है?




python string (6)

आप गलत धारणा कर रहे हैं कि आपके चुने हुए सी ++ कार्यान्वयन पायथन की तुलना में तेज़ी से तेज़ है। पायथन में स्ट्रिंग हैंडलिंग अत्यधिक अनुकूलित है। अधिक प्रश्न के लिए यह प्रश्न देखें: std :: स्ट्रिंग ऑपरेशंस खराब प्रदर्शन क्यों करते हैं?

मैं थोड़ी सी गति प्राप्त करने और अपने जंगली सी ++ कौशल को तेज करने के प्रयास में पाइथन से सी ++ में कुछ कोड बदलने की कोशिश कर रहा हूं। कल मैं चौंक गया था जब सी ++ की तुलना में पाइथन में स्टडीन से पढ़ने वाली लाइनों का एक निष्पक्ष कार्यान्वयन बहुत तेज था (इसे देखें)। आज, मुझे अंत में पता चला कि कैसे सी ++ में एक स्ट्रिंग को विभाजित करने के साथ डिलिमिटर विलय (समान अर्थशास्त्र से पायथन के विभाजन ()), और अब मैं डीजा वी का अनुभव कर रहा हूं! मेरा सी ++ कोड काम करने में काफी समय लगता है (यद्यपि कल के पाठ के मामले में, परिमाण का क्रम नहीं था)।

पायथन कोड:

#!/usr/bin/env python
from __future__ import print_function                                            
import time
import sys

count = 0
start_time = time.time()
dummy = None

for line in sys.stdin:
    dummy = line.split()
    count += 1

delta_sec = int(time.time() - start_time)
print("Python: Saw {0} lines in {1} seconds. ".format(count, delta_sec), end='')
if delta_sec > 0:
    lps = int(count/delta_sec)
    print("  Crunch Speed: {0}".format(lps))
else:
    print('')

सी ++ कोड:

#include <iostream>                                                              
#include <string>
#include <sstream>
#include <time.h>
#include <vector>

using namespace std;

void split1(vector<string> &tokens, const string &str,
        const string &delimiters = " ") {
    // Skip delimiters at beginning
    string::size_type lastPos = str.find_first_not_of(delimiters, 0);

    // Find first non-delimiter
    string::size_type pos = str.find_first_of(delimiters, lastPos);

    while (string::npos != pos || string::npos != lastPos) {
        // Found a token, add it to the vector
        tokens.push_back(str.substr(lastPos, pos - lastPos));
        // Skip delimiters
        lastPos = str.find_first_not_of(delimiters, pos);
        // Find next non-delimiter
        pos = str.find_first_of(delimiters, lastPos);
    }
}

void split2(vector<string> &tokens, const string &str, char delim=' ') {
    stringstream ss(str); //convert string to stream
    string item;
    while(getline(ss, item, delim)) {
        tokens.push_back(item); //add token to vector
    }
}

int main() {
    string input_line;
    vector<string> spline;
    long count = 0;
    int sec, lps;
    time_t start = time(NULL);

    cin.sync_with_stdio(false); //disable synchronous IO

    while(cin) {
        getline(cin, input_line);
        spline.clear(); //empty the vector for the next line to parse

        //I'm trying one of the two implementations, per compilation, obviously:
//        split1(spline, input_line);  
        split2(spline, input_line);

        count++;
    };

    count--; //subtract for final over-read
    sec = (int) time(NULL) - start;
    cerr << "C++   : Saw " << count << " lines in " << sec << " seconds." ;
    if (sec > 0) {
        lps = count / sec;
        cerr << "  Crunch speed: " << lps << endl;
    } else
        cerr << endl;
    return 0;

//compiled with: g++ -Wall -O3 -o split1 split_1.cpp

ध्यान दें कि मैंने दो अलग-अलग विभाजन कार्यान्वयन की कोशिश की। एक (split1) टोकन की खोज के लिए स्ट्रिंग विधियों का उपयोग करता है और कई टोकन मर्ज करने के साथ-साथ कई टोकन को संभालने में सक्षम होता है (यह here से आता here )। दूसरा (स्प्लिट 2) एक स्ट्रीम के रूप में स्ट्रिंग को पढ़ने के लिए गेटलाइन का उपयोग करता है, डिलीमीटरों को मर्ज नहीं करता है, और केवल एक ही डिलीमीटर चरित्र का समर्थन करता है (जिसे स्ट्रिंग स्प्लिटिंग प्रश्नों के उत्तर में कई स्टैक ओवरव्लो उपयोगकर्ताओं द्वारा पोस्ट किया गया था)।

मैंने विभिन्न आदेशों में यह कई बार भाग लिया। मेरी टेस्ट मशीन एक मैकबुक प्रो (2011, 8 जीबी, क्वाड कोर) है, यह नहीं कि यह काफी मायने रखती है। मैं एक 20 एम लाइन टेक्स्ट फ़ाइल के साथ परीक्षण कर रहा हूं जिसमें तीन स्पेस-सेपर कॉलम हैं जो प्रत्येक समान दिखते हैं: "foo.bar 127.0.0.1 home.foo.bar"

परिणाम:

$ /usr/bin/time cat test_lines_double | ./split.py
       15.61 real         0.01 user         0.38 sys
Python: Saw 20000000 lines in 15 seconds.   Crunch Speed: 1333333
$ /usr/bin/time cat test_lines_double | ./split1
       23.50 real         0.01 user         0.46 sys
C++   : Saw 20000000 lines in 23 seconds.  Crunch speed: 869565
$ /usr/bin/time cat test_lines_double | ./split2
       44.69 real         0.02 user         0.62 sys
C++   : Saw 20000000 lines in 45 seconds.  Crunch speed: 444444

मैं क्या गलत कर रहा हूं? सी ++ में स्ट्रिंग स्प्लिटिंग करने का कोई बेहतर तरीका है जो बाह्य पुस्तकालयों (यानी कोई बढ़ावा नहीं) पर भरोसा नहीं करता है, डिलीमीटर (जैसे पायथन के विभाजन) के विलय अनुक्रमों का समर्थन करता है, धागा सुरक्षित है (इसलिए कोई स्ट्रोक नहीं), और जिसका प्रदर्शन कम से कम है अजगर के बराबर पर?

1 / आंशिक समाधान संपादित करें ?:

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

for line in sys.stdin:
    dummy = []
    dummy += line.split()
    count += 1

पायथन का प्रदर्शन अब विभाजन 1 सी ++ कार्यान्वयन के समान है।

/usr/bin/time cat test_lines_double | ./split5.py
       22.61 real         0.01 user         0.40 sys
Python: Saw 20000000 lines in 22 seconds.   Crunch Speed: 909090

मैं अभी भी हैरान हूं कि, यदि पाइथन स्ट्रिंग प्रोसेसिंग के लिए इतना अनुकूल है (मैट जॉइनर के सुझाव के अनुसार), कि ये सी ++ कार्यान्वयन तेजी से नहीं होंगे। अगर किसी के पास सी ++ का उपयोग करके इसे और अधिक इष्टतम तरीके से करने के तरीके के बारे में विचार है, तो कृपया अपना कोड साझा करें। (मुझे लगता है कि मेरा अगला कदम शुद्ध सी में इसे लागू करने की कोशिश करेगा, हालांकि मैं सी में अपनी समग्र परियोजना को दोबारा लागू करने के लिए प्रोग्रामर उत्पादकता से व्यापार नहीं कर रहा हूं, इसलिए यह केवल स्ट्रिंग स्प्लिटिंग गति के लिए एक प्रयोग होगा।)

मदद के लिए आप सबका शुक्रिया।

अंतिम संपादन / समाधान:

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

$ /usr/bin/time cat test_lines_double | ./split6
       15.09 real         0.01 user         0.45 sys
C++   : Saw 20000000 lines in 15 seconds.  Crunch speed: 1333333

मेरा एकमात्र छोटा शेष गपशप इस मामले में प्रदर्शन करने के लिए सी ++ प्राप्त करने के लिए आवश्यक कोड की मात्रा के संबंध में है।

इस मुद्दे और कल के स्टडिन लाइन रीडिंग इश्यू (उपरोक्त लिंक) से यहां दिए गए पाठों में से एक यह है कि किसी को हमेशा भाषाओं के रिश्तेदार "डिफ़ॉल्ट" प्रदर्शन के बारे में निष्पक्ष धारणाएं करने के बजाय बेंचमार्क करना चाहिए। मैं शिक्षा की सराहना करता हूं।

आपके सुझावों के लिए सभी को फिर से धन्यवाद!


एक अनुमान के रूप में, पायथन स्ट्रिंग्स संदर्भित अपरिवर्तनीय तार हैं, ताकि पायथन कोड में चार तारों की प्रतिलिपि बनाई जा सके, जबकि सी ++ std::string एक परिवर्तनीय मान प्रकार है, और इसे सबसे छोटे अवसर पर कॉपी किया गया है।

यदि लक्ष्य तेजी से विभाजित होता है, तो कोई निरंतर समय सबस्ट्रिंग ऑपरेशंस का उपयोग करेगा, जिसका मतलब केवल मूल स्ट्रिंग के हिस्सों का जिक्र करना है, जैसे कि पायथन (और जावा, और सी # ...) में।

सी ++ std::string क्लास में एक रिडीमिंग सुविधा है, हालांकि: यह मानक है , ताकि इसका उपयोग स्ट्रिंग को सुरक्षित रूप से और पोर्टेबल रूप से पारित करने के लिए किया जा सके जहां दक्षता मुख्य विचार नहीं है। लेकिन पर्याप्त चैट। कोड - और मेरी मशीन पर यह पाइथन से बिल्कुल तेज है, क्योंकि पाइथन की स्ट्रिंग हैंडलिंग सी में लागू की गई है जो सी ++ (वह वह) का सबसेट है:

#include <iostream>                                                              
#include <string>
#include <sstream>
#include <time.h>
#include <vector>

using namespace std;

class StringRef
{
private:
    char const*     begin_;
    int             size_;

public:
    int size() const { return size_; }
    char const* begin() const { return begin_; }
    char const* end() const { return begin_ + size_; }

    StringRef( char const* const begin, int const size )
        : begin_( begin )
        , size_( size )
    {}
};

vector<StringRef> split3( string const& str, char delimiter = ' ' )
{
    vector<StringRef>   result;

    enum State { inSpace, inToken };

    State state = inSpace;
    char const*     pTokenBegin = 0;    // Init to satisfy compiler.
    for( auto it = str.begin(); it != str.end(); ++it )
    {
        State const newState = (*it == delimiter? inSpace : inToken);
        if( newState != state )
        {
            switch( newState )
            {
            case inSpace:
                result.push_back( StringRef( pTokenBegin, &*it - pTokenBegin ) );
                break;
            case inToken:
                pTokenBegin = &*it;
            }
        }
        state = newState;
    }
    if( state == inToken )
    {
        result.push_back( StringRef( pTokenBegin, &*str.end() - pTokenBegin ) );
    }
    return result;
}

int main() {
    string input_line;
    vector<string> spline;
    long count = 0;
    int sec, lps;
    time_t start = time(NULL);

    cin.sync_with_stdio(false); //disable synchronous IO

    while(cin) {
        getline(cin, input_line);
        //spline.clear(); //empty the vector for the next line to parse

        //I'm trying one of the two implementations, per compilation, obviously:
//        split1(spline, input_line);  
        //split2(spline, input_line);

        vector<StringRef> const v = split3( input_line );
        count++;
    };

    count--; //subtract for final over-read
    sec = (int) time(NULL) - start;
    cerr << "C++   : Saw " << count << " lines in " << sec << " seconds." ;
    if (sec > 0) {
        lps = count / sec;
        cerr << "  Crunch speed: " << lps << endl;
    } else
        cerr << endl;
    return 0;
}

//compiled with: g++ -Wall -O3 -o split1 split_1.cpp -std=c++0x

अस्वीकरण: मुझे उम्मीद है कि कोई भी बग नहीं है। मैंने कार्यक्षमता का परीक्षण नहीं किया है, लेकिन केवल गति की जांच की है। लेकिन मुझे लगता है, भले ही कोई बग या दो हो, फिर भी सुधार करने से गति को काफी प्रभावित नहीं होगा।


मुझे संदेह है कि यह push_back () फ़ंक्शन कॉल की प्रक्रिया के दौरान std::vector आकार बदलने के तरीके के कारण है। यदि आप वाक्यों के लिए पर्याप्त स्थान आरक्षित करने के लिए std::list या std::vector::reserve() का उपयोग करने का प्रयास करते हैं, तो आपको एक बेहतर प्रदर्शन प्राप्त करना चाहिए। या आप split1 () के लिए नीचे दोनों की तरह संयोजन का उपयोग कर सकते हैं:

void split1(vector<string> &tokens, const string &str,
        const string &delimiters = " ") {
    // Skip delimiters at beginning
    string::size_type lastPos = str.find_first_not_of(delimiters, 0);

    // Find first non-delimiter
    string::size_type pos = str.find_first_of(delimiters, lastPos);
    list<string> token_list;

    while (string::npos != pos || string::npos != lastPos) {
        // Found a token, add it to the list
        token_list.push_back(str.substr(lastPos, pos - lastPos));
        // Skip delimiters
        lastPos = str.find_first_not_of(delimiters, pos);
        // Find next non-delimiter
        pos = str.find_first_of(delimiters, lastPos);
    }
    tokens.assign(token_list.begin(), token_list.end());
}

संपादित करें : मुझे लगता है कि दूसरी स्पष्ट बात यह है कि पाइथन परिवर्तनीय dummy हर बार असाइन की जाती है लेकिन संशोधित नहीं होती है। तो यह सी ++ के खिलाफ उचित तुलना नहीं है। आपको अपने पायथन कोड को dummy = [] होने के लिए संशोधित करने का प्रयास करना चाहिए और फिर इसे dummy += line.split() । क्या आप इसके बाद रनटाइम की रिपोर्ट कर सकते हैं?

EDIT2 : इसे और अधिक निष्पक्ष बनाने के लिए आप C ++ कोड में जबकि लूप को संशोधित कर सकते हैं:

    while(cin) {
        getline(cin, input_line);
        std::vector<string> spline; // create a new vector

        //I'm trying one of the two implementations, per compilation, obviously:
//        split1(spline, input_line);  
        split2(spline, input_line);

        count++;
    };

मुझे संदेह है कि यह पायथन में sys.stdin पर बफरिंग से संबंधित है, लेकिन सी ++ कार्यान्वयन में कोई बफरिंग नहीं है।

बफर आकार को बदलने के तरीके के विवरण के लिए इस पोस्ट को देखें, फिर तुलना को फिर से प्रयास करें: sys.stdin के लिए छोटे बफर आकार को सेट करना?


यदि आप split1 कार्यान्वयन लेते हैं और हस्ताक्षर बदलते हैं तो split2 के अधिक बारीकी से मेल खाते हैं, इसे बदलकर:

void split1(vector<string> &tokens, const string &str, const string &delimiters = " ")

इसके लिए:

void split1(vector<string> &tokens, const string &str, const char delimiters = ' ')

आप split1 और split2 के बीच एक और नाटकीय अंतर प्राप्त करते हैं, और एक बेहतर तुलना:

split1  C++   : Saw 10000000 lines in 41 seconds.  Crunch speed: 243902
split2  C++   : Saw 10000000 lines in 144 seconds.  Crunch speed: 69444
split1' C++   : Saw 10000000 lines in 33 seconds.  Crunch speed: 303030

void split5(vector<string> &tokens, const string &str, char delim=' ') {

    enum { do_token, do_delim } state = do_delim;
    int idx = 0, tok_start = 0;
    for (string::const_iterator it = str.begin() ; ; ++it, ++idx) {
        switch (state) {
            case do_token:
                if (it == str.end()) {
                    tokens.push_back (str.substr(tok_start, idx-tok_start));
                    return;
                }
                else if (*it == delim) {
                    state = do_delim;
                    tokens.push_back (str.substr(tok_start, idx-tok_start));
                }
                break;

            case do_delim:
                if (it == str.end()) {
                    return;
                }
                if (*it != delim) {
                    state = do_token;
                    tok_start = idx;
                }
                break;
        }
    }
}






benchmarking