Differenza di prestazioni tra codici simili

di il
21 risposte

Differenza di prestazioni tra codici simili

Ciao, qualcuno saprebbe spiegarmi come mai il secondo blocco di istruzioni del main() per essere eseguito impiega circa il doppio del tempo rispetto a quello impiegato per eseguire il primo blocco?
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

string addition1(const string &s1, const string &s2)
{
    string s3;
    unsigned int n = 0;
    for(unsigned int i = 0; i < s1.size() || i < s2.size(); ++i)
    {
        n /= 10;
        if(i < s1.size())
        {
            n += s1[s1.size() - 1 - i] - '0';
        }
        if(i < s2.size())
        {
            n += s2[s2.size() - 1 - i] - '0';
        }
        s3.push_back(n % 10 + '0');
    }
    if(n >= 10)
    {
        s3.push_back('1');
    }
    reverse(s3.begin(), s3.end());
    return s3;
}

string multiplication1(const string &s1, const string &s2)
{
    string s3 = "0";
    string temp;
    for(unsigned int i = 0; i < s1.size(); ++i)
    {
        temp.resize(0);
        unsigned int n = 0;
        for(unsigned int j = 0; j < s2.size(); ++j)
        {
            n = (s1[s1.size() - 1 - i] - '0') * (s2[s2.size() - 1 - j] - '0') + n / 10;
            temp.push_back(n % 10 + '0');
        }
        if(n >= 10)
        {
            temp.push_back(n / 10 + '0');
        }
        reverse(temp.begin(), temp.end());
        for(unsigned int j = 0; j < i; ++j)
        {
            temp.push_back('0');
        }
        s3 = addition1(s3, temp);
    }
    return s3;
}

vector<unsigned int> addition2(const vector<unsigned int> &v1, const vector<unsigned int> &v2)
{
    vector<unsigned int> v3;
    unsigned int n = 0;
    for(unsigned int i = 0; i < v1.size() || i < v2.size(); ++i)
    {
        n /= 10;
        if(i < v1.size())
        {
            n += v1[i];
        }
        if(i < v2.size())
        {
            n += v2[i];
        }
        v3.push_back(n % 10);
    }
    if(n >= 10)
    {
        v3.push_back(1);
    }
    return v3;
}

vector<unsigned int> multiplication2(const vector<unsigned int> &v1, const vector<unsigned int> &v2)
{
    vector<unsigned int> v3 = {0};
    vector<unsigned int> temp;
    for(unsigned int i = 0; i < v1.size(); ++i)
    {
        temp.resize(0);
        unsigned int n = 0;
        for(unsigned int j = 0; j < i; ++j)
        {
            temp.push_back(0);
        }
        for(unsigned int j = 0; j < v2.size(); ++j)
        {
            n = v1[i] * v2[j] + n / 10;
            temp.push_back(n % 10);
        }
        if(n >= 10)
        {
            temp.push_back(n / 10);
        }
        v3 = addition2(v3, temp);
    }
    return v3;
}

int main()
{
    string a = "12345";
    string b = "1";
    for(unsigned int i = 0; i < 1000; ++i)
    {
        b = multiplication1(a, b);
    }
    cout << b << endl;

    /*
    vector<unsigned int> c = {5, 4, 3, 2, 1};
    vector<unsigned int> d = {1};
    for(unsigned int i = 0; i < 1000; ++i)
    {
        d = multiplication2(c, d);
    }
    for(unsigned int i = 0; i < d.size(); ++i)
    {
        cout << d[d.size() - 1 - i];
    }
    cout << endl;
    */
}
Al di là delle varie ottimizzazioni e dei diversi approcci possibili, mi chiedo come mai tutta questa differenza tra codici tutto sommato equivalenti (anzi, la versione con le stringhe rispetto a quella con i vettori prevede anche qualche passaggio in più)!?

21 Risposte

  • Re: Differenza di prestazioni tra codici simili

    
    temp.push_back(n / 10);
    
    push_back(...)
  • Re: Differenza di prestazioni tra codici simili

    Ho provato anche ad utilizzare dei
    vector<int8_t>
    ma la situazione più o meno rimane la stessa.

    Quindi in che modo la funzione push_back(), presente in entrambe le versioni, influisce su tale differenza di prestazioni?
  • Re: Differenza di prestazioni tra codici simili

    Provato su MSVC e minGW (togliendo tutti gli output), la versione vector va leggermente più veloce. La differenza si fa più marcata portando a 17 il numero degli elementi.
  • Re: Differenza di prestazioni tra codici simili

    Alexv ha scritto:


    Provato su MSVC e minGW (togliendo tutti gli output), la versione vector va leggermente più veloce. La differenza si fa più marcata portando a 17 il numero degli elementi.
    A me con codeblocks succede il contrario:

    - versione con string senza output:
    
    Process returned 0 (0x0)   execution time : 0.774 s
    Press any key to continue.
    
    - versione con vector senza output:
    
    Process returned 0 (0x0)   execution time : 1.223 s
    Press any key to continue.
    
    Come mai?
  • Re: Differenza di prestazioni tra codici simili

    Nippolo ha scritto:


    A me con codeblocks succede il contrario:

    - versione con string senza output:
    
    Process returned 0 (0x0)   execution time : 0.774 s
    Press any key to continue.
    
    - versione con vector senza output:
    
    Process returned 0 (0x0)   execution time : 1.223 s
    Press any key to continue.
    
    Come mai?
    Io il tempo l'ho calcolato così:
    
    #include <chrono>
    
    using namespace std;
    using namespace std::chrono;
    
    
    cout<<"Versione string\n";
        string a = "123456";
        string b = "1";
    
        auto start = high_resolution_clock::now();
        for(unsigned int i = 0; i < 1000; ++i)
        {
            b = multiplication1(a, b);
        }
        auto stop = high_resolution_clock::now();
        auto duration = duration_cast<milliseconds>(stop - start);
    
        cout << "Tempo: " << duration.count() << " ms" << endl;
    
    
        cout<<"Versione vector\n";
        vector<unsigned int> c = {6, 5, 4, 3, 2, 1};
        vector<unsigned int> d = {1};
    
        auto start = high_resolution_clock::now();
        for(unsigned int i = 0; i < 1000; ++i)
        {
            d = multiplication2(c, d);
        }
    
        auto stop = high_resolution_clock::now();
        auto duration = duration_cast<milliseconds>(stop - start);
        
        cout << "Tempo: " << duration.count() << " ms" << endl;
    
    Togliendo tutti gli output nel blocco da misurare. Mi aspettavo che la versione string finisse prima perché per stringhe piccole usa l'allocazione statica, e invece.
  • Re: Differenza di prestazioni tra codici simili

    Utilizzando la libreria chrono come da te indicato ottengo dei risultati in linea con quelli postati in precedenza:
    Versione string
    Tempo: 763 ms
    Versione vector
    Tempo: 1164 ms
    
    Process returned 0 (0x0)   execution time : 1.946 s
    Press any key to continue.
    
    Secondo te com'è possibile? Compilatore o impostazioni di compilazione? Come detto in precedenza uso codeblocks su windows.
  • Re: Differenza di prestazioni tra codici simili

    Anch'io ho usato CB per compilare con mingw su Windows. Però penso che non hai messi gli output fuori dai blocchi da misurare, perché 1 secondo è molto alto. A me si mantengono entrambi sopra i 100 ms con 6 e elementi (un po' meno su MSVC). Però abbiamo tempi diversi fra i due blocchi (a me è più veloce il vector) a parità di compilatori e penso anche di libreria standard, quindi non riesco a trovare una spiegazione. Forse è nell'hardware.
  • Re: Differenza di prestazioni tra codici simili

    Alexv ha scritto:


    Anch'io ho usato CB per compilare con mingw su Windows.
    Non sono molto pratico di queste cose, in ogni caso da riga di comando ottengo:
    C:\Program Files (x86)\CodeBlocks\MinGW\bin>gcc --version
    gcc (tdm-1) 5.1.0
    Copyright (C) 2015 Free Software Foundation, Inc.
    This is free software; see the source for copying conditions.  There is NO
    warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
    

    Alexv ha scritto:


    Però penso che non hai messi gli output fuori dai blocchi da misurare, perché 1 secondo è molto alto
    Purtroppo quello è il tempo senza l'output, ecco il main() che ho lanciato:
    int main()
    {
        cout << "Versione string\n";
        string a = "12345";
        string b = "1";
        auto start1 = high_resolution_clock::now();
        for(unsigned int i = 0; i < 1000; ++i)
        {
            b = multiplication1(a, b);
        }
        auto stop1 = high_resolution_clock::now();
        auto duration1 = duration_cast<milliseconds>(stop1 - start1);
        cout << "Tempo: " << duration1.count() << " ms" << endl;
    
        cout<<"Versione vector\n";
        vector<unsigned int> c = {5, 4, 3, 2, 1};
        vector<unsigned int> d = {1};
        auto start2 = high_resolution_clock::now();
        for(unsigned int i = 0; i < 1000; ++i)
        {
            d = multiplication2(c, d);
        }
        auto stop2 = high_resolution_clock::now();
        auto duration2 = duration_cast<milliseconds>(stop2 - start2);
        cout << "Tempo: " << duration2.count() << " ms" << endl;
    }

    Alexv ha scritto:


    Però abbiamo tempi diversi fra i due blocchi (a me è più veloce il vector) a parità di compilatori e penso anche di libreria standard, quindi non riesco a trovare una spiegazione. Forse è nell'hardware.
    Se può essere utile ho un intel E5700, 4 GB di RAM e Windows 7 a 64bit.
    Come già detto non sono molto pratico di queste cose, in ogni caso mi sembra davvero strano che il blocco con i vector richieda il doppio del tempo rispetto al blocco con le string.
  • Re: Differenza di prestazioni tra codici simili

    Allora...

    Ho installato codeblocks 20.03-MinGW (GCC 8.1.0).

    Ho modificato il codice al fine di rendere le versioni string e vector praticamente equivalenti dal punto di vista algoritmico:
    #include <iostream>
    #include <cstdint>
    #include <chrono>
    #include <string>
    #include <vector>
    
    using namespace std;
    using namespace std::chrono;
    
    string addition1(const string &s1, const string &s2)
    {
        string s3;
        unsigned int n = 0;
        for(unsigned int i = 0; i < s1.size() || i < s2.size(); ++i)
        {
            n /= 10;
            if(i < s1.size())
            {
                n += s1[i] - '0';
            }
            if(i < s2.size())
            {
                n += s2[i] - '0';
            }
            s3.push_back(n % 10 + '0');
        }
        if(n >= 10)
        {
            s3.push_back('1');
        }
        return s3;
    }
    
    string multiplication1(const string &s1, const string &s2)
    {
        string s3;
        string temp;
        for(unsigned int i = 0; i < s1.size(); ++i)
        {
            temp.resize(0);
            unsigned int n = 0;
            for(unsigned int j = 0; j < i; ++j)
            {
                temp.push_back('0');
            }
            for(unsigned int j = 0; j < s2.size(); ++j)
            {
                n = (s1[i] - '0') * (s2[j] - '0') + n / 10;
                temp.push_back(n % 10 + '0');
            }
            if(n >= 10)
            {
                temp.push_back(n / 10 + '0');
            }
            s3 = addition1(s3, temp);
        }
        return s3;
    }
    
    vector<uint8_t> addition2(const vector<uint8_t> &v1, const vector<uint8_t> &v2)
    {
        vector<uint8_t> v3;
        uint8_t n = 0;
        for(unsigned int i = 0; i < v1.size() || i < v2.size(); ++i)
        {
            n /= 10;
            if(i < v1.size())
            {
                n += v1[i];
            }
            if(i < v2.size())
            {
                n += v2[i];
            }
            v3.push_back(n % 10);
        }
        if(n >= 10)
        {
            v3.push_back(1);
        }
        return v3;
    }
    
    vector<uint8_t> multiplication2(const vector<uint8_t> &v1, const vector<uint8_t> &v2)
    {
        vector<uint8_t> v3;
        vector<uint8_t> temp;
        for(unsigned int i = 0; i < v1.size(); ++i)
        {
            temp.resize(0);
            uint8_t n = 0;
            for(unsigned int j = 0; j < i; ++j)
            {
                temp.push_back(0);
            }
            for(unsigned int j = 0; j < v2.size(); ++j)
            {
                n = v1[i] * v2[j] + n / 10;
                temp.push_back(n % 10);
            }
            if(n >= 10)
            {
                temp.push_back(n / 10);
            }
            v3 = addition2(v3, temp);
        }
        return v3;
    }
    
    int main()
    {
        cout << "calcolo di 12345^1000 (versione string): ";
        string a = "54321";
        string b = "1";
        auto start1 = high_resolution_clock::now();
        for(unsigned int i = 0; i < 1000; ++i)
        {
            b = multiplication1(a, b);
        }
        auto stop1 = high_resolution_clock::now();
        auto duration1 = duration_cast<milliseconds>(stop1 - start1);
        cout << duration1.count() << " ms" << endl;
        //-----------------------------------------------------------
        cout << "calcolo di 12345^1000 (versione vector): ";
        vector<uint8_t> c = {5, 4, 3, 2, 1};
        vector<uint8_t> d = {1};
        auto start2 = high_resolution_clock::now();
        for(unsigned int i = 0; i < 1000; ++i)
        {
            d = multiplication2(c, d);
        }
        auto stop2 = high_resolution_clock::now();
        auto duration2 = duration_cast<milliseconds>(stop2 - start2);
        cout << duration2.count() << " ms" << endl;
    }
    Detto ciò, la faccenda diventa ancora più "strana":

    - lanciando il codice appena riportato con l'opzione -std=c++14 ottengo:
    calcolo di 12345^1000 (versione string): 366 ms
    calcolo di 12345^1000 (versione vector): 1090 ms
    
    Process returned 0 (0x0)   execution time : 1.474 s
    Press any key to continue.
    - con l'opzione -std=c++17 ottengo:
    calcolo di 12345^1000 (versione string): 1409 ms
    calcolo di 12345^1000 (versione vector): 1370 ms
    
    Process returned 0 (0x0)   execution time : 2.796 s
    Press any key to continue.
    Non ci sto capendo più nulla!
  • Re: Differenza di prestazioni tra codici simili

    Nemmeno io.
    A me va più veloce il vector a prescindere dallo standard selezionato.
    Il tuo pc è lento
  • Re: Differenza di prestazioni tra codici simili

    Alexv ha scritto:


    Il tuo pc è lento
    Come osi?! Ha appena 12 anni!

    Scherzi a parte, probabilmente come hai detto tu c'entra in qualche modo l'hardware, magari in relazione alla gestione della memoria per i contenitori della STL. In ogni caso la faccenda resta comunque strana...

    Appena ho tempo provo ad implementare il tutto ricorrendo direttamente all'allocazione dinamica della memoria e ti faccio sapere.
  • Re: Differenza di prestazioni tra codici simili

    Avevo anche provato a fare un calcolo sul numero di riallocazioni di temp, e sono uguali nonostante la stringa parta già da 15 byte statici, mentre il vettore da 1.
    
    //Variabili globali
    int string_reallocations = 0;
    int vector_reallocations = 0;
    
    
    string multiplication1(const string &s1, const string &s2)
    {
        string s3;
        string temp;
        
        auto prev_cap = temp.capacity();
        int reallocations = 0;
        
        for(unsigned int i = 0; i < s1.size(); ++i)
        {
            temp.resize(0);
            unsigned int n = 0;
            for(unsigned int j = 0; j < i; ++j)
            {
                temp.push_back('0');
            }
            for(unsigned int j = 0; j < s2.size(); ++j)
            {
                n = (s1[i] - '0') * (s2[j] - '0') + n / 10;
                temp.push_back(n % 10 + '0');
            }
            if(n >= 10)
            {
                temp.push_back(n / 10 + '0');
            }
            
            if (temp.capacity()>prev_cap) ++reallocations;
            
            s3 = addition1(s3, temp);
        }
        string_reallocations = reallocations;
        return s3;
    }
    
    (stessa cosa in multiplication 2), ma con "vector_reallocation".
  • Re: Differenza di prestazioni tra codici simili

    Ciao

    Purtroppo non sono esperto di C++ perché non mi piace più di tanto, per cui l'ho studiato solo anni fa...

    Se ricordo bene, però, c'erano delle differenze sia nell'uso della memoria (uno dei due garantiva l'uso di una memoria contigua e l'altro no) sia nella modalità di utilizzo degli iteratori (le stringhe corte erano più veloci dei vector)

    Può essere che siano queste due cose che cambino le prestazioni?
    Potrebbe essere che in un PC moderno si evidenzino di più i pregi dei vector (quindi memoria contigua) e nel PC più vecchio la questione degli iteratori (quindi stringhe più veloci)

    Non so, la mia è solo un'ipotesi basata sui ricordi che ho del C++...
  • Re: Differenza di prestazioni tra codici simili

    Ma giusto per curiosità: che dovrebbe fare questo codice? Che algoritmo sarebbe?
Devi accedere o registrarti per scrivere nel forum
21 risposte