[C++] Differenza di prestazioni con implementazioni simili
Salve, come da titolo vorrei capire come mai i due blocchi nel main() richiedano tempi così elevati e diversi tra di loro per essere eseguiti:
Output compilando con l'opzione [inline]-std=c++14[/inline]:
Output compilando con l'opzione [inline]-std=c++17[/inline]:
In pratica, tralasciando i diversi approcci e le varie ottimizzazioni possibili, e tenendo conto del fatto che le versioni string e vector sono praticamente equivalenti dal punto di vista algoritmico, mi chiedo come mai le prestazioni tra le due versioni siano così diverse tra loro e come mai la situazione cambia ulteriormente al variare dello standard.
Se può essere utile utilizzo codeblocks 20.03 MinGW (GCC 8.1.0).
#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;
}Output compilando con l'opzione [inline]-std=c++14[/inline]:
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.
Output compilando con l'opzione [inline]-std=c++17[/inline]:
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.
In pratica, tralasciando i diversi approcci e le varie ottimizzazioni possibili, e tenendo conto del fatto che le versioni string e vector sono praticamente equivalenti dal punto di vista algoritmico, mi chiedo come mai le prestazioni tra le due versioni siano così diverse tra loro e come mai la situazione cambia ulteriormente al variare dello standard.
Se può essere utile utilizzo codeblocks 20.03 MinGW (GCC 8.1.0).
Risposte
Sì è corretto. Entrambe le funzioni di conversione vanno implementate perché si possa usare questo metodo. Tuttavia la creazione direttamente da numeri interi diventa più semplice. Non mi è chiaro quale dovesse essere il tuo metodo che faceva uso dell'overflow, ma intendevo quello che ti ho poi mandato.
"utente__medio":
[quote="vict85"]prova a compilare e lanciare questa versione: ...
Così su due piedi sembra che restituisca un risultato errato; non so se può entrarci in qualche modo quanto detto in precedenza, ossia che la variabile [inline]v[/inline] nel for più interno possa essere potenzialmente soggetta ad overflow.[/quote]
Ho controllato, il problema non è nell'overflow ma in varie altre parti. Prima di tutto ho sbagliato a inizializzare i vettori e lo swap. Ma anche correggendo quello, ho scritto il codice supponengo che l'array fosse scritto al contrario. Ma non vale la pena correggerlo, ho scritto il codice per capire quanto le allocazioni influissero sulle performance. Sarebbe stato più semplice usare un profiler.
"apatriarca":
@ghira: il calcolo non è importante perché lo scopo era quello di confrontare le performance di due codici che fanno la stessa cosa.
Ok, grazie. Volevo solo controllare perché mi ricordo di aver visto colleghi informatici anni fa che hanno dovuto calcolare la 47millesima potenza di qualcosa e qualcuno l'ha fatto con 47mila moltiplicazioni...
"ghira":
[quote="apatriarca"]@ghira: il calcolo non è importante perché lo scopo era quello di confrontare le performance di due codici che fanno la stessa cosa.
Ok, grazie. Volevo solo controllare perché mi ricordo di aver visto colleghi informatici anni fa che hanno dovuto calcolare la 47millesima potenza di qualcosa e qualcuno l'ha fatto con 47mila moltiplicazioni...[/quote]
Con una libreria di questo tipo [inline]pow[/inline] non è disponibile, e trovo sia anche molto abusato dai principianti (usarlo per calcolare potenze basse è senza senso). Qualcosa come \(x^{1000}\) si può comunque fare con meno moltiplicazioni, o usando https://en.wikipedia.org/wiki/Exponenti ... y_squaring oppure con altri metodi simili.
"vict85":
Qualcosa come \(x^{1000}\) si può comunque fare con meno moltiplicazioni, o usando https://en.wikipedia.org/wiki/Exponenti ... y_squaring oppure con altri metodi simili.
Certamente. Era per questo che chiedevo.
@utente__medio il tuo uso del [inline]resize[/inline] e del [inline]v3[v3.size()][/inline] mi confonde un po'. Se al posto delle parentesi avessi usato la funzione [inline]at[/inline] avresti generato una eccezione. Il codice non fa nulla di sbagliato dal punto di vista della memoria, è solo un uso strano dell'interfaccia vector. Il tuo codice è assolutamente equivalente a questo, più leggibile:
Ho cambiato solo poche righe del tuo codice e riformattato (il mio IDE riformatta automaticamente). Ho anche controllato il risultato stavolta.
Comunque è solo una questione di leggibilità del codice.
vector< uint32_t >
multiplication_10b( const vector< uint32_t >& v1, const vector< uint32_t >& v2 )
{
const vector< uint32_t >& v_1 = v1.size( ) < v2.size( ) ? v1 : v2;
const vector< uint32_t >& v_2 = v_1 == v1 ? v2 : v1;
vector< uint32_t > v3( v_1.size( ) + v_2.size( ), 0 );
uint64_t size = 0;
for ( unsigned int i = 0; i < v_1.size( ); ++i )
{
uint64_t r1 = 0;
uint64_t r2 = 0;
size = i;
for ( unsigned int j = 0; j < v_2.size( ) || r1 || r2; ++j )
{
if ( j < v_2.size( ) )
{
r1 += (uint64_t)v_1[ i ] * v_2[ j ];
}
r2 += v3[ size ] + r1 % 1000000000;
v3[ size++ ] = r2 % 1000000000;
r1 /= 1000000000;
r2 /= 1000000000;
}
}
v3.resize( size );
return v3;
}Ho cambiato solo poche righe del tuo codice e riformattato (il mio IDE riformatta automaticamente). Ho anche controllato il risultato stavolta.
Comunque è solo una questione di leggibilità del codice.
Ecco il codice aggiornato:
- innanzitutto ho scritto le due funzioni from_2_to_10() e from_10_to_2() per convertire il vector da base 2 a base 10 (o forse sarebbe più corretto dire da base 2^32 a base 10^9) e viceversa. In pratica ho implementato una rudimentale divisione intera per poi calcolare i resti;
- poi ho implementato il "costruttore" da stringa in base 2, ossia la funzione from_string_2(), che a sua volta sfrutta la funzione from_10_to_2() e il "costruttore" da stringa in base 10 from_string_10(), il quale divide la stringa a partire da destra in gruppi di 9 cifre (escluso l'ultimo gruppo che avrà una generica lunghezza <=9);
- infine le funzioni print_2() e print_10() stampano i risultati ottenuti dalla moltiplicazione rispettivamente in base 2 e 10.
Il tutto sembra funzionare, ma volevo chiedervi se secondo voi va bene come approccio.
In effetti così è più leggibile, purtroppo a volte la brutta abitudine di risparmiare sulle righe di codice prende il sopravvento!
#include <iostream>
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <string>
#include <vector>
using namespace std;
using namespace std::chrono;
const uint32_t N = 1000000000;
vector<uint32_t> from_2_to_10(vector<uint32_t> v_2)
{
vector<uint32_t> v_10;
do
{
uint64_t r = 0;
unsigned int i = 0;
for(unsigned int j = 0; j < v_2.size(); ++j)
{
r = (r << 32) + v_2[j];
if(i || r / N)
{
v_2[i++] = r / N;
r %= N;
}
}
v_2.resize(i);
v_10.push_back(r);
}
while(v_2.size());
return v_10;
}
vector<uint32_t> from_10_to_2(vector<uint32_t> v_10)
{
vector<uint32_t> v_2;
do
{
uint64_t r = 0;
unsigned int i = 0;
for(unsigned int j = 0; j < v_10.size(); ++j)
{
r = r * N + v_10[j];
if(i || r >> 32)
{
v_10[i++] = r >> 32;
r = (uint32_t)r;
}
}
v_10.resize(i);
v_2.push_back(r);
}
while(v_10.size());
return v_2;
}
vector<uint32_t> from_string_10(const string &s, bool flag = true)
{
vector<uint32_t> v_10;
unsigned int i = 0;
while(i < s.size())
{
unsigned int j_max = v_10.size() ? 9 : s.size() % 9;
v_10.push_back(0);
for(unsigned int j = 0; j < j_max; ++j)
{
v_10.back() = v_10.back() * 10 + (s[i++] - '0');
}
}
if(flag)
{
reverse(v_10.begin(), v_10.end());
}
return v_10;
}
vector<uint32_t> from_string_2(const char *s)
{
return(from_10_to_2(from_string_10(s, false)));
}
vector<uint32_t> multiplication_10(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2;
const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;
vector<uint32_t> v3(w1.size() + w2.size(), 0);
for(unsigned int i = 0; i < w1.size(); ++i)
{
uint64_t r1 = 0;
uint64_t r2 = 0;
v3.resize(i);
for(unsigned int j = 0; j < w2.size() || r1 || r2; ++j)
{
if(j < w2.size())
{
r1 += (uint64_t)w1[i] * w2[j];
}
r2 += v3[v3.size()] + r1 % N;
v3.push_back(r2 % N);
r1 /= N;
r2 /= N;
}
}
return v3;
}
vector<uint32_t> multiplication_2(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2;
const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;
vector<uint32_t> v3(w1.size() + w2.size(), 0);
for(unsigned int i = 0; i < w1.size(); ++i)
{
uint64_t r1 = 0;
uint64_t r2 = 0;
v3.resize(i);
for(unsigned int j = 0; j < w2.size() || r1 || r2; ++j)
{
if(j < w2.size())
{
r1 += (uint64_t)w1[i] * w2[j];
}
r2 += v3[v3.size()] + (uint32_t)r1;
v3.push_back((uint32_t)r2);
r1 >>= 32;
r2 >>= 32;
}
}
return v3;
}
void print_10(const vector<uint32_t> &v_10)
{
for(unsigned int i = 0; i < v_10.size(); ++i)
{
if(i)
{
for(int32_t j = N / 10 - 1; j && j >= v_10[v_10.size() - 1 - i]; j /= 10)
{
cout << "0";
}
}
cout << v_10[v_10.size() - 1 - i];
}
cout << endl;
}
void print_2(vector<uint32_t> v_2)
{
reverse(v_2.begin(), v_2.end());
print_10(from_2_to_10(v_2));
}
int main()
{
cout << "calcolo di 12345^1000 (versione vector ottimizzata base 10): ";
vector<uint32_t> a = from_string_10("43695595240774383441671015625");//12345^7
vector<uint32_t> b = from_string_10("12345");
auto start1 = high_resolution_clock::now();
for(unsigned int i = 0; i < 993; ++i)
{
a = multiplication_10(a, b);
}
auto stop1 = high_resolution_clock::now();
auto duration1 = duration_cast<milliseconds>(stop1 - start1);
cout << duration1.count() << " ms" << endl << endl;
print_10(a);
//-----------------------------------------------------------------------
cout << endl << "calcolo di 12345^1000 (versione vector ottimizzata base 2): ";
vector<uint32_t> c = from_string_2("43695595240774383441671015625");//12345^7
vector<uint32_t> d = from_string_2("12345");
auto start2 = high_resolution_clock::now();
for(unsigned int i = 0; i < 993; ++i)
{
c = multiplication_2(c, d);
}
auto stop2 = high_resolution_clock::now();
auto duration2 = duration_cast<milliseconds>(stop2 - start2);
cout << duration2.count() << " ms" << endl << endl;
print_2(c);
}- innanzitutto ho scritto le due funzioni from_2_to_10() e from_10_to_2() per convertire il vector da base 2 a base 10 (o forse sarebbe più corretto dire da base 2^32 a base 10^9) e viceversa. In pratica ho implementato una rudimentale divisione intera per poi calcolare i resti;
- poi ho implementato il "costruttore" da stringa in base 2, ossia la funzione from_string_2(), che a sua volta sfrutta la funzione from_10_to_2() e il "costruttore" da stringa in base 10 from_string_10(), il quale divide la stringa a partire da destra in gruppi di 9 cifre (escluso l'ultimo gruppo che avrà una generica lunghezza <=9);
- infine le funzioni print_2() e print_10() stampano i risultati ottenuti dalla moltiplicazione rispettivamente in base 2 e 10.
Il tutto sembra funzionare, ma volevo chiedervi se secondo voi va bene come approccio.
"vict85":
Il codice non fa nulla di sbagliato dal punto di vista della memoria, è solo un uso strano dell'interfaccia vector. Il tuo codice è assolutamente equivalente a questo, più leggibile: ...
In effetti così è più leggibile, purtroppo a volte la brutta abitudine di risparmiare sulle righe di codice prende il sopravvento!
Ne approfitto per chiedere altre due cose:
- per quanto riguarda l'addizione ho scritto due versioni, una più concisa e una (in teoria) più efficiente; compilando con il flag -O la versione concisa è leggermente più lenta, mentre compilando con il flag -O3 i risultati si invertono. Queste le due versioni (per semplicità posto la versione in base 10):
Al netto delle prestazioni controintuitive riscontrate compilando con -O3, quale versione mi conviene inserire nella libreria che sto scrivendo?
- per quanto riguarda la sottrazione ho scritto le seguenti funzioni:
L'approccio utilizzato va bene o fareste qualcosa di diverso? E per la "traduzione" da base 10 a base 2 si può fare di meglio?
- per quanto riguarda l'addizione ho scritto due versioni, una più concisa e una (in teoria) più efficiente; compilando con il flag -O la versione concisa è leggermente più lenta, mentre compilando con il flag -O3 i risultati si invertono. Queste le due versioni (per semplicità posto la versione in base 10):
vector<uint32_t> addition_10(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2;
const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;
vector<uint32_t> v3;
v3.reserve(w2.size() + 1);
uint64_t r = 0;
unsigned int i = 0;
for(; i < w1.size() || r; ++i)
{
if(i < w1.size())
{
r += (uint64_t)w1[i] + w2[i];
}
else if(i < w2.size())
{
r += (uint64_t)w2[i];
}
v3.push_back(r % N);
r /= N;
}
for(; i < w2.size(); ++i)
{
v3.push_back(w2[i]);
}
return v3;
}
vector<uint32_t> addition_10b(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2;
const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;
vector<uint32_t> v3;
v3.reserve(w2.size() + 1);
uint64_t r = 0;
for(unsigned int i = 0; i < w2.size() || r; ++i)
{
r += uint64_t(i < w1.size() ? w1[i] : 0) + uint64_t(i < w2.size() ? w2[i] : 0);
v3.push_back(r % N);
r /= N;
}
return v3;
}Al netto delle prestazioni controintuitive riscontrate compilando con -O3, quale versione mi conviene inserire nella libreria che sto scrivendo?
- per quanto riguarda la sottrazione ho scritto le seguenti funzioni:
const uint32_t N = 1000000000;
const uint64_t M = (uint64_t)numeric_limits<uint32_t>::max() + 1;
vector<uint32_t> subtraction_10(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
vector<uint32_t> v3;
v3.reserve(v1.size());
uint64_t r = N;
for(unsigned int i = 0; i < v1.size(); ++i)
{
r = N + v1[i] - (r < N);
if(i < v2.size())
{
r -= v2[i];
}
v3.push_back(r % N);
}
for(unsigned int i = v3.size() - 1; i && !v3[i]; --i)
{
v3.pop_back();
}
return v3;
}
vector<uint32_t> subtraction_2(const vector<uint32_t> &v1, const vector<uint32_t> &v2)
{
vector<uint32_t> v3;
v3.reserve(v1.size());
uint64_t r = M;
for(unsigned int i = 0; i < v1.size(); ++i)
{
r = M + v1[i] - (r < M);
if(i < v2.size())
{
r -= v2[i];
}
v3.push_back((uint32_t)r);
}
for(unsigned int i = v3.size() - 1; i && !v3[i]; --i)
{
v3.pop_back();
}
return v3;
}L'approccio utilizzato va bene o fareste qualcosa di diverso? E per la "traduzione" da base 10 a base 2 si può fare di meglio?
Ho notato che questo codice fa qualcosa che probabilmente non è quello che immagini:
infatti il confronto [inline]w1 == v1[/inline] fa il confronto tra vector e non di puntatori. Per confrontare i puntatori devi scrivere [inline]&w1 == &v1[/inline].
Per capire, guarda
https://godbolt.org/z/8zfx5r1MP
e noterai che che viene chiamata l'uguaglianza di vector, mentre con [inline]&w1 == &v1[/inline] si confrontano due registri.
Per quanto riguarda la sottrazione non vedo alcun sistema per gestire i numeri negativi. Insomma, se \(v_1 < v_2\) ti viene un risultato poco sensato.
Per l'addizione, sei sicuro che le due funzioni diano lo stesso risultato? A occhio mi sembra che la seconda non stia tenendo conto del riporto finale.
const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2; const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;
infatti il confronto [inline]w1 == v1[/inline] fa il confronto tra vector e non di puntatori. Per confrontare i puntatori devi scrivere [inline]&w1 == &v1[/inline].
Per capire, guarda
https://godbolt.org/z/8zfx5r1MP
e noterai che che viene chiamata l'uguaglianza di vector, mentre con [inline]&w1 == &v1[/inline] si confrontano due registri.
Per quanto riguarda la sottrazione non vedo alcun sistema per gestire i numeri negativi. Insomma, se \(v_1 < v_2\) ti viene un risultato poco sensato.
Per l'addizione, sei sicuro che le due funzioni diano lo stesso risultato? A occhio mi sembra che la seconda non stia tenendo conto del riporto finale.
"vict85":
Ho notato che questo codice fa qualcosa che probabilmente non è quello che immagini:
const vector<uint32_t> &w1 = v1.size() < v2.size() ? v1 : v2; const vector<uint32_t> &w2 = w1 == v1 ? v2 : v1;
infatti il confronto [inline]w1 == v1[/inline] fa il confronto tra vector e non di puntatori. Per confrontare i puntatori devi scrivere [inline]&w1 == &v1[/inline].
Per capire, guarda
https://godbolt.org/z/8zfx5r1MP
e noterai che che viene chiamata l'uguaglianza di vector, mentre con [inline]&w1 == &v1[/inline] si confrontano due registri.
Dal punto di vista del risultato non dovrebbero esserci differenze, ma confrontare i vector risulta un inutile rallentamento, infatti il mio intento era quello di confrontare gli indirizzi. Grazie per avermelo fatto notare.
"vict85":
Per quanto riguarda la sottrazione non vedo alcun sistema per gestire i numeri negativi. Insomma, se \(v_1 < v_2\) ti viene un risultato poco sensato.
Queste funzioni le sto utilizzando per implementare una classe [inline]big_int[/inline]. Tale classe possiede due membri, un [inline]vector
"vict85":
Per l'addizione, sei sicuro che le due funzioni diano lo stesso risultato? A occhio mi sembra che la seconda non stia tenendo conto del riporto finale.
Sì, dovrebbero essere equivalenti. Il riporto finale dovrebbe essere assicurato dal [inline]|| r[/inline] presente nella condizione del for.
Vabbè, tralasciando le trascurabili questioni di ottimizzazione che ho sollevato negli ultimi post, ossia dando per concluse le funzioni di addizione, sottrazione e moltiplicazione, non mi resta che implementare la divisione intera.
Questa è la funzione (si tratta più o meno del classico algoritmo insegnato a scuola) che avevo implementato qualche tempo fa nella versione con le stringhe:
Mi rendo conto che non è il massimo e che presenta ampi margini di miglioramento, ma il punto è che questo stesso approccio, se utilizzato nella versione con i vector, in cui al contrario del codice appena postato considero gruppi di più cifre alla volta, temo possa rivelarsi molto meno performante. Il motivo sta nell'individuazione di "q", ossia delle singole cifre (o gruppi di cifre, a seconda della versione) del quoziente; infatti considerando una cifra alla volta, l'intervallo di appartenenza di "q" si riduce a [0;9], mentre considerando più cifre alla volta il suddetto intervallo cresce considerevolmente e quindi la ricerca di "q" richiederà in media molti più tentativi.
Nella speranza di essere stato abbastanza chiaro, volevo chiedervi se siete d'accordo con questa mia preoccupazione.
Questa è la funzione (si tratta più o meno del classico algoritmo insegnato a scuola) che avevo implementato qualche tempo fa nella versione con le stringhe:
int compare_abs(const string &s_1, const string &s_2)
{
if(s_1.size() != s_2.size())
{
return((int)s_1.size() - s_2.size());
}
unsigned int i;
for(i = 0; i < s_1.size() - 1 && s_1[i] == s_2[i]; ++i);
return((int)s_1[i] - s_2[i]);
}
string division(const string &s_1, const string &s_2, const bool flag_quotient)
{
string quotient;
string rest;
unsigned int i;
for(i = 0; compare_abs(rest, s_2) < 0; ++i)
{
rest.push_back(s_1[i]);
}
while(true)
{
unsigned int q;
int relation = compare_abs(rest, s_2);
if(relation <= 0)
{
q = !relation;
if(!relation)
{
rest = "0";
}
}
else
{
unsigned int r = rest[0] - '0';
if(rest.size() > s_2.size())
{
r = r * 10 + rest[1] - '0';
}
q = r / (s_2[0] - '0');
if(q > 9)
{
q = 9;
}
while(q > 1)
{
bool flag = true;
unsigned int a = r;
for(unsigned int j = 0; j < s_2.size(); ++j)
{
unsigned int b = q * (s_2[j] - '0');
if(a < b)
{
--q;
flag = false;
break;
}
if(a - b >= q)
{
break;
}
if(j != s_2.size() - 1)
{
a = (a - b) * 10 + rest[j + 1 + (rest.size() > s_2.size())] - '0';
}
}
if(flag)
{
break;
}
}
rest = subtraction(rest, multiplication({char(q + '0')}, s_2));
}
quotient.push_back(q + '0');
if(i == s_1.size())
{
break;
}
if(rest[0] == '0')
{
rest.resize(0);
}
rest.push_back(s_1[i++]);
}
return(flag_quotient ? quotient : rest);
}Mi rendo conto che non è il massimo e che presenta ampi margini di miglioramento, ma il punto è che questo stesso approccio, se utilizzato nella versione con i vector, in cui al contrario del codice appena postato considero gruppi di più cifre alla volta, temo possa rivelarsi molto meno performante. Il motivo sta nell'individuazione di "q", ossia delle singole cifre (o gruppi di cifre, a seconda della versione) del quoziente; infatti considerando una cifra alla volta, l'intervallo di appartenenza di "q" si riduce a [0;9], mentre considerando più cifre alla volta il suddetto intervallo cresce considerevolmente e quindi la ricerca di "q" richiederà in media molti più tentativi.
Nella speranza di essere stato abbastanza chiaro, volevo chiedervi se siete d'accordo con questa mia preoccupazione.
Provo a riformulare la questione sollevata nel precedente post: dal momento che il classico algoritmo di divisione che viene insegnato a scuola sembra essere molto più veloce considerando una cifra alla volta piuttosto che considerando gruppi di più cifre alla volta così come sto facendo nell'implementazione di questa libreria per i "big int", cosa mi conviene fare?
Prevedo due suddivisioni, una a gruppi di più cifre per +, -, *, e una a gruppi di una sola cifra per /, %?
Oppure mi conviene ricorrere ad un diverso algoritmo di divisione? E nel caso, quale?
Prevedo due suddivisioni, una a gruppi di più cifre per +, -, *, e una a gruppi di una sola cifra per /, %?
Oppure mi conviene ricorrere ad un diverso algoritmo di divisione? E nel caso, quale?
Come ti ho già detto in altre circostanze, devi smettere di pensare di lavorare con più cifre ma piuttosto di lavorare con cifre in una base diversa da dieci. Se una 9 cifre allora stai lavorando in una base uguale a 1000000000. A quel punto tutte le operazione del tuo codice che usano la base 10 diventano operazioni con la nuova base.
"apatriarca":
Come ti ho già detto in altre circostanze, devi smettere di pensare di lavorare con più cifre ma piuttosto di lavorare con cifre in una base diversa da dieci. Se una 9 cifre allora stai lavorando in una base uguale a 1000000000. A quel punto tutte le operazione del tuo codice che usano la base 10 diventano operazioni con la nuova base.
Ok, allora riformulo ancora una volta: il classico algoritmo di divisione insegnato a scuola è, a differenza di quanto accade per addizione, sottrazione e moltiplicazione, molto più veloce in base 10 che in base 10^9.
Cosa mi conviene fare? Utilizzare una base diversa a seconda dell'operazione oppure utilizzare un diverso algoritmo di divisione?
Dal momento che le singole cifre del quoziente possono variare nell'intervallo $[0;b-1]$ (dove $b$ è la base numerica adottata) e che il valore $0$ può essere escluso con un semplice confronto, avrei pensato di effettuare la divisione direttamente in base $2$. A tal proposito facendo qualche ricerca in rete penso che un [inline]vector>[/inline] o un [inline]vector[/inline] potrebbero fare al mio caso.
Che ne pensate, vale la pena lavorarci? Ne verrebbe fuori qualcosa di abbastanza performante? E nel caso con cosa mi converrebbe lavorare? [inline]vector>[/inline], [inline]vector[/inline], [inline]string[/inline] o altro?
P.S.
Quanto è efficiente e come funziona internamente la funzione [inline]bitset::to_ulong()[/inline]?
Che ne pensate, vale la pena lavorarci? Ne verrebbe fuori qualcosa di abbastanza performante? E nel caso con cosa mi converrebbe lavorare? [inline]vector
P.S.
Quanto è efficiente e come funziona internamente la funzione [inline]bitset::to_ulong()[/inline]?
Intanto ho provato ad implementare qualcosa con i bitset restando nell'ambito dei 64 bit:
Sembra funzionare, ma la "traduzione" dell'algoritmo da una divisione tra uint64_t a una divisione tra "big_int" non mi sembra semplicissimo, soprattutto volendo mantenere prestazioni elevate.
Qualsiasi consiglio è ben accetto!
#include <iostream>
#include <bitset>
#include <cstdint>
using namespace std;
const uint8_t N = 64;
bool operator <(const bitset<N> &b1, const bitset<N> &b2)
{
for(int8_t i = N - 1; i >= 0; i--)
{
if(b1[i] != b2[i])
{
return b2[i];
}
}
return false;
}
uint8_t msb(const bitset<N> &b)//most significant bit
{
uint8_t i;
for(i = N - 1; i && !b[i]; --i);
return i;
}
uint64_t division(bitset<N> b1, bitset<N> b2, const bool flag_q = true)
{
bitset<N> q;
uint8_t divisor_msb = msb(b2);
int8_t i = (signed)msb(b1) - divisor_msb;
if(i > 0)
{
b2 <<= i;
}
for(; i >= 0; --i, b2 >>= 1)
{
if(!(b1 < b2))
{
q[i] = true;
for(int8_t j = i; j <= divisor_msb + i; ++j)
{
if(b2[j])
{
for(int8_t k = j; b1[k] = !b1[k]; ++k);
}
}
}
}
return(flag_q ? q.to_ullong() : b1.to_ullong());
}
int main()
{
uint64_t a = 3027239782390037;
uint64_t b = 5146;
cout << division(bitset<N>(a), bitset<N>(b)) << endl;
cout << a / b << endl;
cout << division(bitset<N>(a), bitset<N>(b), false) << endl;
cout << a % b << endl;
}Sembra funzionare, ma la "traduzione" dell'algoritmo da una divisione tra uint64_t a una divisione tra "big_int" non mi sembra semplicissimo, soprattutto volendo mantenere prestazioni elevate.
Qualsiasi consiglio è ben accetto!
Mi sembra sospetto che tu abbia bisogno di usare questo tipo di approccio per fare una divisione di interi. bitset ha altri scopi. Non ho però avuto tempo di guardare il tuo codice. Immagino che tu stia usando un approccio sbagliato per la base \(10^9\).
"vict85":
Mi sembra sospetto che tu abbia bisogno di usare questo tipo di approccio per fare una divisione di interi. bitset ha altri scopi. Non ho però avuto tempo di guardare il tuo codice. Immagino che tu stia usando un approccio sbagliato per la base \( 10^9 \).
Cerco di fare il punto sulla questione della divisione tra "big_int" che ho introdotto negli ultimi post:
- l'algoritmo di divisione che sto utilizzando, tralasciando le varie versioni implementate e le varie ottimizzazioni (si spera) adottate, è quello della classica divisione in colonna che viene insegnata a scuola (la cosiddetta "divisione lunga");
- le singole cifre $q_i$ del quoziente $Q$, a seconda della base $b$ adottata, varieranno nell'intervallo $[0;b-1]$. Una volta assicuratoci con un semplice confronto che $q_i!=0$, possiamo facilmente fissare $q_(i,MAX)$, ossia il massimo valore che quella determinata cifra del quoziente può assumere. Fissato $q_(i,MAX)$, per giungere al $q_i$ effettivo bisognerà ovviamente fare dei "tentativi", e il punto è proprio questo, ossia: maggiore è la base $b$ adottata, maggiori saranno in media i "tentativi" da fare per giungere al valore di $q_i$ corretto. Siete d'accordo con questa cosa, oppure sto dicendo una sciocchezza?
- partendo dalla suddetta osservazione, ho pensato che la cosa migliore sarebbe stata quella di eliminare i "tentativi" effettuando la divisione in base $2$, dove infatti $q_i$, una volta escluso lo $0$ con un semplice confronto, non può che essere $1$. Nel precedente post ho improvvisato una versione con i bitset per interi a 64 bit; nel frattempo credo di essere riuscito ad implementare la divisione binaria anche tra "big_int" ricorrendo a [inline]vector
Il codice sembra funzionare, ma considerazioni e consigli al riguardo sarebbero davvero ben accetti;
- passiamo ora alle note dolenti... ero abbastanza soddisfatto della divisione appena postata, tuttavia confrontandola con la versione postata qui (divisione in base $10$ che fa parte di una vecchia libreria sui "big_int" basata sulle stringhe, che ho implementato tempo fa), ne esce sconfitta, e anche di parecchio! Per esempio nella divisione tra un numero a 4180 cifre ed uno a 556 cifre, la vecchia versione con le stringhe impiega 50ms, mentre questa nuova 110ms (misurando solo l'esecuzione delle funzioni di divisione).
Eppure la funzione appena postata mi sembra abbastanza "compatta", priva di "tentativi" e basata su operazioni "veloci"... secondo voi dove possono celarsi le criticità che la rendono più lenta della vecchia versione basata sulle stringhe?
Per trovare i coefficienti si può usare penso una ricerca binaria. Siccome moltiplicazione e confronto hanno peso \((O(n_b)\) e la ricerca ha un costo \(O(\log_2(b))\) allora il costo è \(O(\log_2(b)n_b)\).D'altra parte \(n_{10^9} = 9^{-1} n_{10}\) e \(\log_2(10^9) = 9\log_2(10)\), quindi mi sembra che il calcolo del coefficiente ha complessità costante al cambio della base. Però il numero di coefficienti dovrebbe essere 9 volte più piccolo, e così anche la sottrazione. Quindi mi aspetterei performance migliori al crescere della base.
"vict85":
Per trovare i coefficienti si può usare penso una ricerca binaria. Siccome moltiplicazione e confronto hanno peso \( (O(n_b) \) e la ricerca ha un costo \( O(\log_2(b)) \) allora il costo è \( O(\log_2(b)n_b) \).D'altra parte \( n_{10^9} = 9^{-1} n_{10} \) e \( \log_2(10^9) = 9\log_2(10) \), quindi mi sembra che il calcolo del coefficiente ha complessità costante al cambio della base. Però il numero di coefficienti dovrebbe essere 9 volte più piccolo, e così anche la sottrazione. Quindi mi aspetterei performance migliori al crescere della base.
Purtroppo so poco o nulla di teoria della complessità computazionale, ma in linea di massima credo di aver capito quello che intendi dire. In ogni caso non so quanto lo scenario generale da te prospettato possa applicarsi nello specifico ai due algoritmi che ho implementato.
Se può essere utile provo a descriverli per sommi capi:
1) nel vecchio algoritmo con le stringhe, opero la classica divisione in base $10$.
Per esempio:
[size=120]$\overbrace{\underbrace{34}_(a_1)\underbrace{5}_(r_3)201}^R8743566:\overbrace{\underbrace{8}_(d_1)7154}^D$[/size]
- se $R
- se $R=D$ allora $q_i=1$ e $R=0$;
- altrimenti (ossia $R>D$) $q_iin[1;q_(i,max)]=[1;a_1//d_1]$ e $R=R-q_i*D$.
Per determinare $q_i$ parto da un valore di primo tentativo pari a $q_(i,T)=q_(i,max)$ a scendere. Per testare $q_(i,T)$ non vado a fare il calcolo per intero verificando che $R<=q_(i,T)*D$, ma avanzo una cifra alla volta.
Cerco di spiegare meglio quello che intendo... detti $b_i=q_(i,T)*d_i$ e $a_i=(a_(i-1)-b_(i-1))*10+r_(i+2)$:
* se $a_i
* se $a_i-b_i>=q_(i,T)$, allora deduco che $q_i=q_(i,T)$.
Riprendendo l'esempio numerico sopra postato per la determinazione di $q_1$ si ha:
# $q_(1,T)=a_1//d_1=34//8=4$ :
## $a_1=34$ e $b_1=q_(1,T)*d_1=4*8=32$, essendo $a_1>b_1$ $\wedge$ $a_1-b_1
## $a_1=34$ e $b_1=q_(1,T)*d_1=3*8=24$, essendo $a_1-b_1>q_(1,T)$ posso concludere che $q_1=3$.
------------------------------------------------------------------------------------
2) nel nuovo algoritmo con i vettori di bool (lo so, nello specifico utilizzo [inline]vector
- se $R
- altrimenti $q_i=1$ e $R=R-D$.
Per esempio:
[size=120]$\overbrace{110100}^R10001010$ $:$ $=>q_1=0$
$\underbrace{111001}_D$[/size]
[size=120]$\overbrace{1101001}^R0001010$ $:$ $=>q_2=1$
$\text{_}\underbrace{111001}_D$[/size]
[size=120]$0\overbrace{1100000}^R001010$ $:$ $=>q_3=1$ $...$
$\text{__}\underbrace{111001}_D$[/size]
$R
Per la sottrazione invece mi limito, partendo da destra, ad invertire, per ogni bit di $R$ in corrispondenza di un $1$ in $D$, i bit di $R$ finché andando verso sinistra non incontro un $1$.
------------------------------------------------------------------------------------
Detto ciò, è vero che il vettore di bool è circa 3,3 volte più lungo della stringa, ma nella versione con le stringhe ci sono varie operazioni con interi che internamente operano comunque su sequenza di più bit, senza dimenticare poi la parte relativa ai "tentativi".
Probabilmente non mi resta che arrendermi all'evidenza, ma nella mia ignoranza trovo questa differenza nelle prestazioni abbastanza controintuitiva.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo