vict85 ha scritto:Sbagli, e anche di molto. Il tuo codice è ben poco performante ed è dominato dalle allocazioni di memoria. Per capire quanto sia pessimo...
Ho già ripetuto più volte che il codice postato all'inizio era solo un mezzo per chiedere lumi circa le performance "controintuitive" riscontrate tra vector e string; in ogni caso penso sia inutile che io perda tempo a fare inutili precisazioni e che sia meglio postare direttamente il codice ottimizzato:
- Codice:
#include <iostream>
#include <chrono>
#include <cstdint>
#include <vector>
using namespace std;
using namespace std::chrono;
vector<uint32_t> multiplication_10(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);
for(unsigned int i = 0; i < v_1.size(); ++i)
{
uint64_t r1 = 0;
uint64_t r2 = 0;
v3.resize(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[v3.size()] + r1 % 1000000000;
v3.push_back(r2 % 1000000000);
r1 /= 1000000000;
r2 /= 1000000000;
}
}
return v3;
}
void print_10(const vector<uint32_t> &v)
{
for(unsigned int i = 0; i < v.size(); ++i)
{
if(i)
{
for(int32_t j = 99999999; j && j >= v[v.size() - 1 - i]; j /= 10)
{
cout << "0";
}
}
cout << v[v.size() - 1 - i];
}
cout << endl;
}
int main()
{
cout << "calcolo di 12345^1000 (versione vector ottimizzata base 10): ";
vector<uint32_t> a = {12345};
vector<uint32_t> b = {1};
auto start1 = high_resolution_clock::now();
for(unsigned int i = 0; i < 1000; ++i)
{
b = multiplication_10(a, b);
}
auto stop1 = high_resolution_clock::now();
auto duration1 = duration_cast<milliseconds>(stop1 - start1);
cout << duration1.count() << " ms" << endl;
print_10(b);
}
Output:
Testo nascosto, fai click qui per vederlo
- Codice:
calcolo di 12345^1000 (versione vector ottimizzata base 10): 2 ms
30980916979571261678037792640547069821046036601263871423172603964432880446620608
46921638204797951863536177399422240269688598440386160524113311366171137540029427
91772720296320086301939317723959165750831660314625504906217694965268441368838284
91469899680820312066142708028389393562630538115386600687343726225365416760557989
41423155494189268546531047348336572287590039126299044550768543719716900090002922
31442640702405997349818652846007594672121952993600612240375288011172203296667256
96103967654224628215610071281098978353840302864126825283500458106807878522509659
21789617648423284361266990316368590121427804100038121975738472719701414718604485
59701917501364026826498681300417013008430237787456258392796158010957510644217069
98341913428129617946641478177778534617429438982842385866806060632693349145018235
12239084719922296603840279509341320330116129246617953872657843763736914650433910
69947270507908425989612108500884562232290869386787877493097701502859303071373757
98655553418051305869563741235177332696717875374591544971368987407514335651644993
48432070402708303140803815093836661660356285937395020277788919864363825187404391
66973596854885177857972177954369036272112372120342169211179441034974532201077985
02955733113425832358515283713193528314018013484978895836581392051714102432880542
73520458521176241545142042871027819038633452778882009889151826115545711661170538
36747195908282969788810091869993349713112267938558757495744359548488837018005043
40690662067911606624152430636860695557307662212093813837874302080738361232336551
74575751749331919935735057962393028640196663750515631155647068114586019547125009
66722593376174534528998418559797925572480799490873627279344223127796375553240572
15862646352988229249067464618561571347927535747106152891191398219533463769254976
60439255056416164625808728071677859168160485698031944035324637075340851589197234
49415021308596978472922475070959635686086272975863164803202569864125951706329194
84682164033661640489555929737222661905985234140148505838990396502711735660674750
18401069005143388746198994486546761245453653960305361484058030629364813564938166
77996142347736230549290495923638437033343172179181801753570878708654257297687835
26965343706996729232760606845658227256991400912979153167112235978039183655623558
98974562226281554721134128093680325493342116410019082065191222152604701943612903
09012247981704105777443919500572258770469577053059340743175489359094192490153869
68801837378836637000835706292471984808215940621442162785226511155294831484513417
52199992248704863885652427271790306569255537274573369763448958846105089050305523
89745067153053340339925663961641409046696655149031934108909967069140051370963337
42293240129209862323592579138243170317263223252880934191859024800749271249770266
97005663041724543518495369422176498807371766396344183276476753948925774528804843
05655939076362259220197812625222643643191577117100739643427218343227279208350495
80217315761848037089866403378986967045064502829656583826962255738198354622836756
35667056382976855279913816549680982420288449166338344372060236443053987567633619
13498399705896830636029425918669043084740115869198785908560762760382332445251211
23130345477189333775791288130929475816834573933825566780851556546207567350921324
84252238947178033958197247843877788771142111236322569477645881902111263631757196
58176061228259719565346549780300325616948182208870465891192349276710668441048641
29975170039721209641075115717792256013191312063969737958364103235501978884662125
34511083901139702691409815298297037003389820841696983552075032727515727567122502
94394271855766758729580875496156304085099464372152797873952740789997020284489294
85834734357491174993595291833627475607319515601968664863128650348891298074261373
11630439976466542171620548090996899637416145616614625955318606438025388953080883
19814146640625180562801649749164640860829007177519736517996763714855878556975798
53551247141335832576720350019360024777873472945177760531417791020722451271496295
35007942765141973975166467388687997634230267335326011501002931165248908784123116
24139545280293494422725269869365974996851368188630938826921834561289870180189609
527587890625
Process returned 0 (0x0) execution time : 0.118 s
Press any key to continue.
Con quest'implementazione non penso di star facendo più operazioni del necessario, o sbaglio?
vict85 ha scritto: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
v
nel for più interno possa essere potenzialmente soggetta ad overflow.--------------------------------------------------------------------------------------------------------------------------
Utilizzando l'approccio suggerito da apatriarca nel suo ultimo post, presumo che la funzione multiplication() si riduca a:
- Codice:
vector<uint32_t> multiplication_2(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);
for(unsigned int i = 0; i < v_1.size(); ++i)
{
uint64_t r1 = 0;
uint64_t r2 = 0;
v3.resize(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[v3.size()] + (uint32_t)r1;
v3.push_back((uint32_t)r2);
r1 >>= 32;
r2 >>= 32;
}
}
return v3;
}
Giusto?
Non ho la certezza che questa versione funzioni, in quanto devo ancora implementare una funzione per stamparne correttamente il risultato in base 10.
In ogni caso, come prevedibile, risulta molto più performante dell'omologa "in base 10"; lo scetticismo espresso nei precedenti post, infatti, non si riferiva a questo approccio, in cui comunque non si verifica alcun overflow e ci si limita a sostituire l'operatore modulo con il casting e la divisione con il right-shift, ma quello che prevedeva di sfruttare "l'overflow circolare" degli interi senza segno, ma molto probabilmente ho capito io male.
Oltre ad un'apposita funzione per stampare i risultati, ipotizzo che bisogna anche prevedere un apposito "costruttore" da stringa, che invece di dividere la stringa in gruppi fissi di 9 cifre, divida la stringa in gruppi di 9 o 10 cifre in base a quando si verifica l'overflow. Giusto?