C++

[Lusina]

Մեկ էլ էդ նույնը C++-ում կարելի է ցուցիչների ու հղումների միջոցով անել, բայց ամենահարմար ու արագ լուծումն է ashot_1987-ի տված տարբերակը`

x=x+y;
y=x-y;
x=x-y;

Ես հիմա ճակատագրական քայլ կանեմ ու կփորձեմ հակառակվել Varzor-ին
Ես գրեթե համոզված եմ, որ xor-ը ավելի արագ կաշխատի, քան այդ գրված տարբերակը.

Հ.Գ."Գրեթե" բառս հետո կարա փրկի

[soultaker]

Ես հիմա ճակատագրական քայլ կանեմ ու կփորձեմ հակառակվել Varzor-ին
Ես գրեթե համոզված եմ, որ xor-ը ավելի արագ կաշխատի, քան այդ գրված տարբերակը.

Հ.Գ."Գրեթե" բառս հետո կարա փրկի

Բնականաբար XOR-ը ավելի արագ կաշխատի, որովհետև 3 բիտային գործողություն անելը ավելի արագ է քան 3 գումարում/հանումը:

Մի այսպիսի հարց` ենթադրենք ունեմ m[10000][10000] մատրից: Հերթով արժեք եմ տալիս(կամ արժեք վերցնում) էլեմենտներին`

for(i = 0; i < 10000; i++)
{
for(j = 0; j < 10000; j++)
{
m[i][j] = m[i][10000 - j - 1] * 2; // Օրինակի համար
}
}

Նույն բանը` երկրորդ տարբերակով

for(i = 0; i < 10000; i++)
{
int* p = m[i];
for(j = 0; j < 10000; j++)
{
p[j] = p[10000 - j - 1] * 2;
}
}

Այժմ հարցը` ինչի համար երկրորդ տարբերակը ավելի արագ չի աշխատում (ոնց որ մի բան էլ ավելի դանդաղ):

[ashot_1987]

for(i = 0; i < 10000; i++)
{
int* p = m[i];
for(j = 0; j < 10000; j++)
{
p[j] = p[10000 - j - 1] * 2;
}
}

Ինձ թվում ա երկրորդ տարբերակը ավելի արագ չի աշխատում քանի որ երկրորդ տարբերակում p ցուցիչը 10000 անգամ հայտարարվում ա.
for(i = 0; i < 10000; i++)
{
int* p = m[i];
...........

[Ruzanna Stepanyan]

Խնդրում եմ օգնեք, էս խնդրի մեջ մի բանը էն չեմ արել

Հաշվել և արտածել տրված n տարր պարունակող միաչափ զանգվածի կենտ ինդեքս ունեցող տարրերի քառակուսիների արտադրայլը:

#include <iostream>
#include <math.h>
using namespace std;
void main()
{
int x[10], p, i, n;

do {
cin>>n;
}
while(1>n||n>10);
for(i=0; i<n; i++)
{
cout<<"x["<<i<<"]=";
cin>>x[i];
}
p=1;
for(i=2; i<n; i+=2)

p=p*pow(double (x(i)),2);

cout<<"p="<<p<<endl;
}

[ashot_1987]

Խնդրում եմ օգնեք, էս խնդրի մեջ մի բանը էն չեմ արել

Հաշվել և արտածել տրված n տարր պարունակող միաչափ զանգվածի կենտ ինդեքս ունեցող տարրերի քառակուսիների արտադրայլը:

#include <iostream>
#include <math.h>
using namespace std;
void main()
{
int x[10], p, i, n;

do {
cin>>n;
}
while(1>n||n>10);
for(i=0; i<n; i++)
{
cout<<"x["<<i<<"]=";
cin>>x[i];
}
p=1;
for(i=2; i<n; i+=2)

p=p*pow(double (x(i)),2);

cout<<"p="<<p<<endl;
}

Մի հատ ակնհայտ սխալ որ առաջին հայացքից տեսա էսա p=p*pow(double (x(i)),2); x(i) չէ x[i]

[Ruzanna Stepanyan]

x(i) x[i] կասեք էս երկուսի տարբերությունը որն է

[ashot_1987]

x(i) x[i] կասեք էս երկուսի տարբերությունը որն է

Տարբերությունը ահավոր շատ ա: Զանգվածի ինդեքսը գրվում ա [ ] նշանների մեջ, կոմպիլյատորը մենակ տենց ա հասկանում

[Varzor]

Ես հիմա ճակատագրական քայլ կանեմ ու կփորձեմ հակառակվել Varzor-ին
Ես գրեթե համոզված եմ, որ xor-ը ավելի արագ կաշխատի, քան այդ գրված տարբերակը.
Հ.Գ."Գրեթե" բառս հետո կարա փրկի

Հեչ էլ ճակատագրական չի Ըստ էության ճիշտ եք տեսականորեն, մասսամբ էլ տեխնիկապես: Մոդուլ երկուսով գումարման գործողությունը պրոցեսորից ավելի քիչ տակտեր է պահանջում` ստանդարտով, մանավանդ երբ այդ թվերն ամբողջ թվեր են: AMR, MIPS (RISK) ճարտարապետության պրոցեսորներում միանշանակ այդպես է, բայց այ x86-ում...
Պրոցեսորն ունի առանձին բլոկներ, որոնք կոնկրետ գործողություններն ավելի արագ են կատարում` ավելի օպտիմիզացված: Ու կախված արժեքների տիպից գործողության "արժեքը" տակտերով հաշված կարող է տարբեր լինել:
Ըստ էթության մոդուլ երկուսով գումարումը իրենից ներկայացնում է N քանակով տրամաբանական համեմատության օպերացիաներ` քանի հատ բիտ կա, այդքան էլ համեմատություն է անում:
Սակայն էլ. տեխնիկական տեսանկյունից դա այսպես չէ.
Կան երկու ռեգիստրներ, որոնցում պահված են գումարվող ամբողջ թվերը: "գումարիր ըստ մոդուլ երկուսի" հրամանի դեպքում այդ ռեգիստրների թվերը փոխանցվում են ըստ մոդուլ երկուսի գումարող մոդուլին, որն էլ իր հերթին մի տակտով ստանում է արդյունքը և այն գրանցում ելքային ռեգիստրում:
Սովորական գումարման ժամանակ "գումարիր" գործողության ժամանակ երկու ռեիստրների թվերը փոխանցվում են գումարիչին, որն էլ մեկ տակտում ստանում է արդյունքը (սակայն այդ նպատակով օգտագործում է լրացուցիչ ռեգիստր) և տեղափոխում է ելքային ռեգիստր:
Սակայն երբ թվերը սահող ստորակետով են, ապա գործողություններին ընթացքն այլ է: Շատ չմանրանամ ու ասեմ, որ մոդուլ երկուսովը ավելի արագ է կատարվում:
Քանոր որ այստեղ հնչած խնդիրը ամբողջ թվերին էր վերաբերվում, ապա ինձ թույլ տվեցի պնդել, որ սովորական գումարումն ամենահարմար ու արագ լուծումն է, քանի որ այն ավելի հասկանալի է

[Varzor]

Այժմ հարցը` ինչի համար երկրորդ տարբերակը ավելի արագ չի աշխատում (ոնց որ մի բան էլ ավելի դանդաղ):

Շատ պարզ` ամեն տողի էլէմենտի համար ուկազատելներ ես պահում: համ տակտ ես կորցնում, համ էլ ուկազատելից (ցուցիչ) արժեք վերցնելն ավելի դանդաղ գործողություն է, քան ուղղակի դիմելը: Երբ որ զանգվածը հայտարարում ես, էդ ժամանակ հիշողությունում, ծրագրի ստեկում հասցեների տիրույթ է ռեզերվացվում այդ զանգվածի համար: Զանգվածի անունն էլ հենց հղումն է այդ տիրույթին: Իսկ դու մի հատ էլ առանձին ցուցիչ ես հայտարարում էդ հղման վրա ` համ հիշողություն է գնում, համ էլ տակտ: Պիտի սկզբից կարդա ցուցիչի տվյալը, որը հենց հղման արժեքն է ու նոր ըստ այդ տվյալի անցնի մատրիցին:

Բայց իմաստը որնա, որ տենց ես գրում?

[MSGM]

Ես հիմա ճակատագրական քայլ կանեմ ու կփորձեմ հակառակվել Varzor-ին
Ես գրեթե համոզված եմ, որ xor-ը ավելի արագ կաշխատի, քան այդ գրված տարբերակը.

Հ.Գ."Գրեթե" բառս հետո կարա փրկի

Մեջբերում Վիկիպեդիայից.

Most modern compilers can optimize away the temporary variable in the naive swap, in which case the naive swap uses the same amount of memory and the same number of registers as the XOR swap and is at least as fast, and often faster. The XOR swap is also much less readable and completely opaque to anyone unfamiliar with the technique.
On modern CPU architectures, the XOR technique is considerably slower than using a temporary variable to do swapping. One reason is that modern CPUs strive to execute instructions in parallel via instruction pipelines. In the XOR technique, the inputs to each operation depend on the results of the previous operation, so they must be executed in strictly sequential order. If efficiency is of tremendous concern, it is advised to test the speeds of both the XOR technique and temporary variable swapping on the target architecture.

Այսինքն ավելի լավ ա "լրացուցիչ փոփոխականով" գրել: Համ գրողի համար ա հասկանալի, համ էլ կոմպիլյատորի:

[soultaker]

Շատ պարզ` ամեն տողի էլէմենտի համար ուկազատելներ ես պահում: համ տակտ ես կորցնում, համ էլ ուկազատելից (ցուցիչ) արժեք վերցնելն ավելի դանդաղ գործողություն է, քան ուղղակի դիմելը: Երբ որ զանգվածը հայտարարում ես, էդ ժամանակ հիշողությունում, ծրագրի ստեկում հասցեների տիրույթ է ռեզերվացվում այդ զանգվածի համար: Զանգվածի անունն էլ հենց հղումն է այդ տիրույթին: Իսկ դու մի հատ էլ առանձին ցուցիչ ես հայտարարում էդ հղման վրա ` համ հիշողություն է գնում, համ էլ տակտ: Պիտի սկզբից կարդա ցուցիչի տվյալը, որը հենց հղման արժեքն է ու նոր ըստ այդ տվյալի անցնի մատրիցին:

Բայց իմաստը որնա, որ տենց ես գրում?

Տենց գրելուս իմաստը արագացնելնա, բայց դանդաղումա ավելի: m[i][j] դիմումը պետք է կատարի մեկ բազմապատկում և մեկ գումարում, իսկ p[i] դիմումը` մեկ գումարում: Այսինքն քանի որ պիտի դիտարկեմ ամբողջ i տողը, ու այդ տողի ամեն էլեմենտը գտնելու համար տրված i ու j ինդեքսներից պիտի ամեն դիմումի ժամանակ ծրագիրը պիտի հաշվի *(m + i * 10000 + j), դրա համար ես պահում եմ ցուցիչ այդ տողի վրա, որ տողի ամեն էլեմենտին դիմելուց միանգամից տողի ցուցիչից ստանա, ամեն անգամ բազմապատկում չանի: Իսկ ցուցիչի վրա կորցրած տակտը հազարավոր անգամ ավելի փոքր պիտի լինի քան թե բազմապատկման վրա կորցրած տակտը (մեկ անգամ ցուցիչ հայտարարել ու արժեք տալու շնորհիվ խնայվում է 10000 բազմապատկման տակտ): Ամեն դեպքում ամեն ինչ այդքան պարզ չի, որովհետև գոյություն ունի պրոցեսորի կեշ հիշողություն, ու կարող է դա էլ դեր խաղալ, այդ ամենին գումարած կոմպիլյատորի օպտիմիզացիան, այնպես որ բավականին դժվար է ենթադրություններ անել:

[Varzor]

Տենց գրելուս իմաստը արագացնելնա, բայց դանդաղումա ավելի: m[i][j] դիմումը պետք է կատարի մեկ բազմապատկում և մեկ գումարում, իսկ p[i] դիմումը` մեկ գումարում: Այսինքն քանի որ պիտի դիտարկեմ ամբողջ i տողը, ու այդ տողի ամեն էլեմենտը գտնելու համար տրված i ու j ինդեքսներից պիտի ամեն դիմումի ժամանակ ծրագիրը պիտի հաշվի *(m + i * 10000 + j), դրա համար ես պահում եմ ցուցիչ այդ տողի վրա, որ տողի ամեն էլեմենտին դիմելուց միանգամից տողի ցուցիչից ստանա, ամեն անգամ բազմապատկում չանի: Իսկ ցուցիչի վրա կորցրած տակտը հազարավոր անգամ ավելի փոքր պիտի լինի քան թե բազմապատկման վրա կորցրած տակտը (մեկ անգամ ցուցիչ հայտարարել ու արժեք տալու շնորհիվ խնայվում է 10000 բազմապատկման տակտ): Ամեն դեպքում ամեն ինչ այդքան պարզ չի, որովհետև գոյություն ունի պրոցեսորի կեշ հիշողություն, ու կարող է դա էլ դեր խաղալ, այդ ամենին գումարած կոմպիլյատորի օպտիմիզացիան, այնպես որ բավականին դժվար է ենթադրություններ անել:

Չգիտեմ, պարզ գրել եմ, թե ինչի է դանդաղ անում: Արագ չի անի: Էդ քեզ թվում է, որ բազմապատսկամն գործողոթւյան համար այդքան շատ տակտեր է օգտագործում: Իրականում ներակռւցված մոդուլը այդ գործողությունն ավելի արագ է կատարում` մեկ տակտի մեջ շատ գործողություններ` 8 գործողություն:
Համամաիտ եմ` պրոցեսորի քեշը կապ ունի, ու նայած թե ինչ կառուցվածքի պրոցեսոր էու ինչ մակարդակի քեշեր ունի:
Բայց հիմա նայենք սենց.
i-երորդ տողի հասցեն ցուցիչում գրանցելու համար միևնույն է էդ քո ասած բազմաբատկումը պիտի անի: m[i]-ն հաշվելու համար պիտի բազմապատկի չէ? դու էլ գրել էս *p = m[i]: Որքան հիշում եմ ստեղ m-ը հենց ինքը ցուցիչ է հանդիսանում մատրիցի զրոյական ինդեքսով էլէմենտին: m[i]-ն արդեն ցուցիչ է հանդիսանում i-երորդ տողի զրոյական ինդեքսով էլէմենտին ու ըստ էության m[i]-ն հասցե է: Այսինքն տեսականորեն` *p = *(m + i * 10000) և p-ն ստանում է i-երորդ տողի զրոյական ինդեքսով էլէմենտի հասցեն: Երբ գրում ենք p[j] նշանակում է p-ի արժեքին գումարում ենք j հատ p-ի տիպին համապատասխան բայտ ու դիմում համապատասխան հասեցին` p[j]= p+j*sixeof(int): Ստացվում է որ j=1, 10000 ցիկլի ընթացքում p[j] հասեցները ստանալու համար 10000 անգամ j-ով կատարում ենք բազմապատկում p-ի տիպի բայտերի քանակով` 4-ով (sizeof(int) = 4): Այնպես որ բազմապատկումների քանակը հեչ էլ չի նվազում:
Իսկ հաշվի առնելով նաև այն, որ p-երի պահպանման համար լրացուցիչ հասցեներ են զբաղեցվում, դա ավելի է դանդաղացնում աշխատանքը:

Եթե ինչ-որ բան սխալ եմ հիշում, արի այլ ձևով խելք-խելքի տանք
Միգուցե &` հղումով գրելը առավելություն տա?

[soultaker]

Չգիտեմ, պարզ գրել եմ, թե ինչի է դանդաղ անում: Արագ չի անի: Էդ քեզ թվում է, որ բազմապատսկամն գործողոթւյան համար այդքան շատ տակտեր է օգտագործում: Իրականում ներակռւցված մոդուլը այդ գործողությունն ավելի արագ է կատարում` մեկ տակտի մեջ շատ գործողություններ` 8 գործողություն:
Համամաիտ եմ` պրոցեսորի քեշը կապ ունի, ու նայած թե ինչ կառուցվածքի պրոցեսոր էու ինչ մակարդակի քեշեր ունի:
Բայց հիմա նայենք սենց.
i-երորդ տողի հասցեն ցուցիչում գրանցելու համար միևնույն է էդ քո ասած բազմաբատկումը պիտի անի: m[i]-ն հաշվելու համար պիտի բազմապատկի չէ? դու էլ գրել էս *p = m[i]: Որքան հիշում եմ ստեղ m-ը հենց ինքը ցուցիչ է հանդիսանում մատրիցի զրոյական ինդեքսով էլէմենտին: m[i]-ն արդեն ցուցիչ է հանդիսանում i-երորդ տողի զրոյական ինդեքսով էլէմենտին ու ըստ էության m[i]-ն հասցե է: Այսինքն տեսականորեն` *p = *(m + i * 10000) և p-ն ստանում է i-երորդ տողի զրոյական ինդեքսով էլէմենտի հասցեն: Երբ գրում ենք p[j] նշանակում է p-ի արժեքին գումարում ենք j հատ p-ի տիպին համապատասխան բայտ ու դիմում համապատասխան հասեցին` p[j]= p+j*sixeof(int): Ստացվում է որ j=1, 10000 ցիկլի ընթացքում p[j] հասեցները ստանալու համար 10000 անգամ j-ով կատարում ենք բազմապատկում p-ի տիպի բայտերի քանակով` 4-ով (sizeof(int) = 4): Այնպես որ բազմապատկումների քանակը հեչ էլ չի նվազում:
Իսկ հաշվի առնելով նաև այն, որ p-երի պահպանման համար լրացուցիչ հասցեներ են զբաղեցվում, դա ավելի է դանդաղացնում աշխատանքը:

Եթե ինչ-որ բան սխալ եմ հիշում, արի այլ ձևով խելք-խելքի տանք
Միգուցե &` հղումով գրելը առավելություն տա?

Ուշադրություն դարձրու թե բազմապատկում քանի անգամ կկատարվի առաջին դեպքում, ու քանի անգամ` երկրորդ դեպքում:

[Varzor]

Ուշադրություն դարձրու թե բազմապատկում քանի անգամ կկատարվի առաջին դեպքում, ու քանի անգամ` երկրորդ դեպքում:

Նույն քանակով է կատարվում:
Սենց հաշվենք` m[i][j] պարագայում կատարվում է i*j անգամ: *p=m[i] դեպքում կատարվում է i անգամ, իսկ քանի որ յուրաքանչյուր p[i] համար, ինչպես ցույց տվեցի, կատարվում է j անգամ, ուստի նույնպես կատարվում է i*j անգամ
Բայց քանի որ յուրաքանչյուր տողի համար կատարվում է *p=m[i], ապա i անգամ կատարվում է հղման փոփոխականի վերագրում և հասցեի տրամադրում: Հենց սա էլ դանդաղացնում է:
Համ էլ արդեն գտել եմ` Դեյտելից գտա զանգվածների հետ ցուցիչներով ու հղումներով աշխատելու համեմատականությունը:
Ծրագրի համարժեքության տեսանկյունից այսպես է.
Օրինակ` ունենք
int b[5];
int x;
int *bPrt = b;
Ուզում ենք դիմել 3-րդ էլէմենտին
Իրար համարժեք են
1. x = b[2]
2. x = *(b+2)
3. x = bPtr[2]
4. x = *(bPtr+2)

Բայց այս գործողութոյւններից ավելի արագ են կատարվում առաջին 2-ը, քանի որ չկա միջանկյալ *bPtr = b գործողութունը, որն էլ իր հերթին է տակտեր վերցնում պրոցեսորից:

աղբյուր` Դեյտել C++ էջ 346-347

[soultaker]

Նույն քանակով է կատարվում:
Սենց հաշվենք` m[i][j] պարագայում կատարվում է i*j անգամ: *p=m[i] դեպքում կատարվում է i անգամ, իսկ քանի որ յուրաքանչյուր p[i] համար, ինչպես ցույց տվեցի, կատարվում է j անգամ, ուստի նույնպես կատարվում է i*j անգամ
Բայց քանի որ յուրաքանչյուր տողի համար կատարվում է *p=m[i], ապա i անգամ կատարվում է հղման փոփոխականի վերագրում և հասցեի տրամադրում: Հենց սա էլ դանդաղացնում է:
Համ էլ արդեն գտել եմ` Դեյտելից գտա զանգվածների հետ ցուցիչներով ու հղումներով աշխատելու համեմատականությունը:
Ծրագրի համարժեքության տեսանկյունից այսպես է.
Օրինակ` ունենք
int b[5];
int x;
int *bPrt = b;
Ուզում ենք դիմել 3-րդ էլէմենտին
Իրար համարժեք են
1. x = b[2]
2. x = *(b+2)
3. x = bPtr[2]
4. x = *(bPtr+2)

Բայց այս գործողութոյւններից ավելի արագ են կատարվում առաջին 2-ը, քանի որ չկա միջանկյալ *bPtr = b գործողութունը, որն էլ իր հերթին է տակտեր վերցնում պրոցեսորից:

աղբյուր` Դեյտել C++ էջ 346-347

Եթե p[j]= p+j*sixeof(int) նկատի ունես որպես բազմապատկում, ապա ես դա չեմ համարում սովորական բազմապատկում, որովհետև sizeof(int) սովորաբար 4 է, հետևաբար կոմպիլյատորը պարտավոր է օպտիմիզացնել (j * 4) գործողությունը և այն վերածել (j << 2) շատ ավելի արագ բիտային գործողության: Իսկ ցուցիչը չի կարող նկատելի չափով դանդաղեցնել, որովհետև դրսի ցիկլի մեջ է գտնվում, իսկ ամբողջ ժամանակը ծախսվում է ներսի ցիկլի վրա, այնպես որ ցուցիչի վրա ծախսված ժամանակը կկազմի ամբողջ ժամանակի մոտավորապես 0.01% մասը: Ամեն դեպքում ես հարցը տալիս նկատի ունեի ավելի սարքային պատճառներ` պրոցեսորի աշխատելու մեխանիզմը և այլն, որովհետև զուտ տրամաբանական տեսանկյունից նայելիս 2րդ տարբերակում միայն արագանալու միտում եմ տեսնում: