String teilen



  • cooky451 schrieb:

    CStoll schrieb:

    @cookie: Was soll denn diese hässliche C-Lösung hier bringen?

    Nachdem er ja eh schon .c_str() genutzt hat, war mir das const char* jetzt auch recht.

    Na gut, aber warum dann nicht gleich noch strtok() reinbringen 😃
    Btw, ich wollte nicht unbedingt eine schnelle Lösung, sondern eine elegante. Und da ich aktuell gar nicht mehr mit C++ arbeite, hätte ich im produktiven Einsatz vermutlich sowas geschrieben:

    Function: Arnold
      Description: Split a Semicolon-seperated List into its components
      Return Type:
        Number:
      Parameters:
        String: pIn
        Receive Number: paOut[*]
      Static Variables:
      Local Variables:
        Number: count
        Number: index
        String: aData[*]
      Actions
        Set count = SalStrTokenize( pIn, '', ';', aData )
        Set index = 0
        While index<count
          Set paOut[index] = SalStrToNumber( aData[i] )
          Set index = index+1
        Return count
    

    PS @Michael: Nein, die Lösung finde ich nicht als gemogelt 😃



  • Ich komm auf Faktor 6. Deshalb würd ich gern mal sehen, was cooky falsch macht.



  • Michael E. schrieb:

    cooky451 schrieb:

    (Deine Lösung braucht auf meinem System z.B. ~25 mal so lange wie meine.)

    Das glaub ich dir nicht so recht. Wie sieht dein Testprogramm aus?

    http://ideone.com/xQ7Ni
    Wobei der Unterschied bei mir noch größer ist, da sind's ~5000 zu ~200 ms.

    Interessant wäre es noch wie groß der Unterschied bei einem einzigen langen String ist, allerdings habe ich da nicht viel Hoffnung.



  • CStoll schrieb:

    Function: Arnold
      Description: Split a Semicolon-seperated List into its components
      Return Type:
        Number:
      Parameters:
        String: pIn
        Receive Number: paOut[*]
      Static Variables:
      Local Variables:
        Number: count
        Number: index
        String: aData[*]
      Actions
        Set count = SalStrTokenize( pIn, '', ';', aData )
        Set index = 0
        While index<count
          Set paOut[index] = SalStrToNumber( aData[i] )
          Set index = index+1
        Return count
    

    Wie nennt sich das CStoll?



  • cooky451 schrieb:

    Michael E. schrieb:

    cooky451 schrieb:

    (Deine Lösung braucht auf meinem System z.B. ~25 mal so lange wie meine.)

    Das glaub ich dir nicht so recht. Wie sieht dein Testprogramm aus?

    http://ideone.com/xQ7Ni
    Wobei der Unterschied bei mir noch größer ist, da sind's ~5000 zu ~200 ms.

    Interessant wäre es noch wie groß der Unterschied bei einem einzigen langen String ist, allerdings habe ich da nicht viel Hoffnung.

    Das Problem bei deinem Test ist, dass der Stringstream bei vielen kurzen Strings viel zu oft Speicher allozieren muss.
    Deine C Lösung alloziert keinen Speicher und muss nichts kopieren.

    Mit nem langwen String sollte der Unterschied stark schrumpfen.



  • cooky451 schrieb:

    Interessant wäre es noch wie groß der Unterschied bei einem einzigen langen String ist, allerdings habe ich da nicht viel Hoffnung.

    Natürlich. die Konstruktion des stringstreams verbrennt dir sicherlich 90% der Rechenzeit.



  • kurzefrage schrieb:

    Wie nennt sich das CStoll?

    Die Sprache nennt sich SAL (Scalable Application Language).

    @otze/cookie/...: Eventuell wäre es mal eine Idee, das ganze mit einem std::strstream zu testen (der arbeitet mit nackten char-Zeigern und kann afair auch direkt auf extern bereitgestelltem Speicher hantieren).



  • otze schrieb:

    cooky451 schrieb:

    Interessant wäre es noch wie groß der Unterschied bei einem einzigen langen String ist, allerdings habe ich da nicht viel Hoffnung.

    Natürlich. die Konstruktion des stringstreams verbrennt dir sicherlich 90% der Rechenzeit.

    Habe mal nen neuen Test gemacht mit:

    void arnold(const char *s, std::vector<int>& output)
    {
      const char *p = s - 1;
      s += std::strlen(s);
      while (p < s)
        output.push_back(std::strtol(p + 1, const_cast<char**>(&p), 10));
    }
    
    void arnold(const std::string& s, std::vector<int>& out)
    {
      std::stringstream str(s);
      int val;
      while(str>>val)
      {
        str.get();//zum Verarbeiten des Trennzeichens
        out.push_back(val);
      }
    }
    
    int main()
    {
      std::string input;
      std::ifstream is("test2.txt");
      is >> input;
      std::vector<int> output;
    
      std::clock_t t = std::clock();
      //for (int i = 0; i < 500000; ++i)
        arnold(input.c_str(), output);
      std::cout << clock() - t << std::endl;
    
      output.clear();
    
      t = clock();
      //for (int i = 0; i < 500000; ++i)
        arnold(input, output);
      std::cout << clock() - t << std::endl;
    
      getchar();
    }
    

    Datei wurde erstellt mit:

    int main()
    {
      std::ofstream of("test2.txt");
      std::srand(std::time(0));
      for (int i = 0; i < 500000; ++i)
        of << std::rand() << ';';
    }
    

    Ergebnis:
    1. 38 ms
    2. 623 ms

    Also das überzeugt mich jetzt immer noch nicht so direkt..



  • Ganz so dramatisch sind die Unterschiede bei mir nicht. Du benchst da nicht etwa im Debug-Modus, oder? Wie dem auch sei, stringstream ist auch bei mir langsamer, etwa um den faktor 3,5 (mit gcc 4.6.1 und -O3). Allerdings kann ich die C-Version mit Boost.Spirit ausstechen. Folgendes:

    #include <cstring>
    #include <ctime>
    #include <fstream>
    #include <iostream>
    #include <sstream>
    #include <string>
    #include <vector>
    
    #include <boost/spirit/include/qi.hpp>
    
    void arnold(const char *s, std::vector<int>& output)
    {
      const char *p = s - 1;
      s += std::strlen(s);
      while (p < s)
        output.push_back(std::strtol(p + 1, const_cast<char**>(&p), 10));
    }
    
    void arnold(const std::string& s, std::vector<int>& out)
    {
      std::istringstream str(s);
      int val;
      while(str>>val)
      {
        str.get();//zum Verarbeiten des Trennzeichens
        out.push_back(val);
      }
    }
    
    template<typename iter_t>
    void arnold(iter_t s, iter_t e, std::vector<int>&out) {
      using namespace boost::spirit::qi;
      phrase_parse(s, e, int_ % ';', space, out);
    }
    
    int main()
    {
      std::string input;
      std::ifstream is("test2.txt");
      std::time_t t;
      is >> input;
    
      {
        std::vector<int> output;
        t = std::clock();
        arnold(input.c_str(), output);
        std::cout << double(std::clock() - t) / CLOCKS_PER_SEC << std::endl;
      }
    
      {
        std::vector<int> output;
        t = std::clock();
        arnold(input, output);
        std::cout << double(std::clock() - t) / CLOCKS_PER_SEC << std::endl;
      }
    
      {
        std::vector<int> output;
        t = std::clock();
        arnold(input.begin(), input.end(), output);
        std::cout << double(std::clock() - t) / CLOCKS_PER_SEC << std::endl;
      }
    
      {
        std::vector<int> output;
        t = std::clock();
        char const *p = input.c_str();
    
        arnold(p, p + input.size(), output);
        std::cout << double(std::clock() - t) / CLOCKS_PER_SEC << std::endl;
      }
    }
    

    liefert bei einer Datei mit 5 Millionen Zufallswerten, die durch

    (for i in $(seq 5000000); do echo -n $RANDOM\; ; done) > test2.txt
    

    erstellt wurde, das Ergebnis

    0.21
    0.72
    0.13
    0.12
    

    Compiler wieder gcc 4.6.1 mit -O3.



  • Hm.. nutze normalerweise Visual Studio 2010. (Release Build latürnlich.) Schon komisch, mit MinGW/G++ bekommen ich ca. deine Ergebnisse.


Anmelden zum Antworten