Unajua tofauti ya hizi for~loops mbili? (Programmers)

NullPointer

JF-Expert Member
Joined
Feb 7, 2011
Messages
3,473
Points
2,000

NullPointer

JF-Expert Member
Joined Feb 7, 2011
3,473 2,000
Kuna jamaa hua wananitumiatumia code zao humu jf nazicheki sasa nimekutana na hili tatizo many times sijui kwa nini.
Em angalia hizi for loops mbili, zote zinafanya kazi moja ila jaribu kuniambia tofauti ni nini.

Code:
for (int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        A[i][j] = B[i][j];
   }
}

Na hii hapa ya pili

Code:
for (int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        A[j][i] = B[j][i];
   }
}
Kama umenotice, ni mstari moja tu umebadilika, hapo kwenye assignment ya hizo elements za B kuziweka kwenye A.

Hizi loops zote zinafanya kazi ileile, in the end utapata matokeo yaleyale ila kuna moja ni poor design na nyingine ni sahihi, we unahisi ipi ni poor? Na kwa nini?
 

ndea

Member
Joined
Aug 28, 2013
Messages
92
Points
95

ndea

Member
Joined Aug 28, 2013
92 95
No 1 n poor kwasababu inaanza na loop ya njee wakati inaitajika ianze na loop ya ndan imalize ndio iangalie ya nje.
 

NullPointer

JF-Expert Member
Joined
Feb 7, 2011
Messages
3,473
Points
2,000

NullPointer

JF-Expert Member
Joined Feb 7, 2011
3,473 2,000
Ya pili hiyo ndio poor design, ya kwanza itakuwa ina assign elements according to rows, ya pili according to columns.
Uko sahihi, ya pili ndio poor design, lakini sababu hujaifafanua, kwa nini ni mbaya kuloop kwa rows instead of columns ?
Jibu linatakiwa liongelee kitu flani kuhusu memory access, hapo ndipo kuna umuhimu.
 

Cannabis

JF-Expert Member
Joined
Jan 20, 2014
Messages
1,085
Points
2,000

Cannabis

JF-Expert Member
Joined Jan 20, 2014
1,085 2,000
Jibu linaweza kuwa Loop ya kwanza au loop ya pili inategemea umeuliza kwa language ipi

Kwa kuwa avatar yako ina C++:p:p basi nitajibu in context ya C++ and the likes (Loop ya Pili ni sahihi) in which a two dimensional array inakuwa arranged kwa order ya rows ikifuatiwa na columns "row-major"
i.e. 0,0|0,1|0,2|0,3|1,0|1,1|1,2|1,3|2,0|2,1|2,2|2,3.......

Kwa Loop ya kwanza unakuwa unazipata hizo elements zako za array kama kwa order ilivyowekwa kwenye memory
i.e. 0,0|0,1|0,2|0,3|1,0|1,1|1,2|1,3|2,0|2,1|2,2|2,3.........

kwa loop ya pili unakuwa unaruka ovyo, hauzipati kama order iliyowekwa kwenye memory.
i.e. 0,0|1,0|2,0|3,0|4,0|5,0|6,0|7,0|8,0|9,0|0,1|1,1|2,1|3,1|4,1|5,1|6,1|7,1|8,1|9,1|.......

Shida inakuja jinsi hizo elements zinavyoletwa kwenye CPU kwa lugha rahisi ni kwamba zinaletwa kupitia cache memory kwa vipande vipande kufuata order iliyowekwa kwenye memory, sasa imagine umeletewa vipande vya elements 4 tu kama vilivyowekwa kwenye memory i.e. 0,0|0,1|0,2|0,3| Kwa njia ya kwanza utazipitia zote bila shida kwa mleto wa kwanza
Kwa njia ya pili utapitia 0,0| halafu hizi nyingine unaziacha mpaka usubiri mleto wa pili uone kama kuna element unazozihitaji, kwa lugha ya kitaalamu wanaiita "Cache Miss".

Kwa lugha kama MATLAB,GNU Octave zenyewe zinafuata notation ya "column major" hivyo loop ya kwanza itakuwa ndio sahihi na sababu ni kinyume cha maelezo ya hapo juu.:)
 

NullPointer

JF-Expert Member
Joined
Feb 7, 2011
Messages
3,473
Points
2,000

NullPointer

JF-Expert Member
Joined Feb 7, 2011
3,473 2,000
Jibu linaweza kuwa Loop ya kwanza au loop ya pili inategemea umeuliza kwa language ipi

Kwa kuwa avatar yako ina C++:p:p basi nitajibu in context ya C++ and the likes (Loop ya Pili ni sahihi) in which a two dimensional array inakuwa arranged kwa order ya rows ikifuatiwa na columns "row-major"
i.e. 0,0|0,1|0,2|0,3|1,0|1,1|1,2|1,3|2,0|2,1|2,2|2,3.......

Kwa Loop ya kwanza unakuwa unazipata hizo elements zako za array kama kwa order ilivyowekwa kwenye memory
i.e. 0,0|0,1|0,2|0,3|1,0|1,1|1,2|1,3|2,0|2,1|2,2|2,3.........

kwa loop ya pili unakuwa unaruka ovyo, hauzipati kama order iliyowekwa kwenye memory.
i.e. 0,0|1,0|2,0|3,0|4,0|5,0|6,0|7,0|8,0|9,0|0,1|1,1|2,1|3,1|4,1|5,1|6,1|7,1|8,1|9,1|.......

Shida inakuja jinsi hizo elements zinavyoletwa kwenye CPU kwa lugha rahisi ni kwamba zinaletwa kupitia cache memory kwa vipande vipande kufuata order iliyowekwa kwenye memory, sasa imagine umeletewa vipande vya elements 4 tu kama vilivyowekwa kwenye memory i.e. 0,0|0,1|0,2|0,3| Kwa njia ya kwanza utazipitia zote bila shida kwa mleto wa kwanza
Kwa njia ya pili utapitia 0,0| halafu hizi nyingine unaziacha mpaka usubiri mleto wa pili uone kama kuna element unazozihitaji, kwa lugha ya kitaalamu wanaiita "Cache Miss".

Kwa lugha kama MATLAB,GNU Octave zenyewe zinafuata notation ya "column major" hivyo loop ya kwanza itakuwa ndio sahihi na sababu ni kinyume cha maelezo ya hapo juu.:)

Mkuu uko sahihi kabisa, jibu nililokua natafuta ni linaloongelea cache hit na cache miss.

Ambavyo ningelijibu mimi which is exactly the same thing na ulivojibu wewe sema a different explanation.

RAM inavyokua accessed, mtu akiomba data kawaida kunakua na buffer ambayo inachukua an entire row from the memory na kuijaza kwenye buffer then inatuma hiyo value moja inayohitajika kwenda kwenye CPU, mtu anavyoomba data zilizopo kwenye row moja ile row buffer inakua nazo tayari haihitaji kurudi kwenye memory na kuvuta row nzima inaituma tu direct, wanaiita spatial locality (next address to the data that is current accessed is more likely to be accessed in the futute, so its kept close).

Mtu anayechukua data zilizopo rows tofauti anasababisha kila muda akiomba data row nzima iombwe kwenye RAM iwekwe kwenye buffer then itumwe kila wakati which is more expensive kwa hiyo loop ya pili lazima itakua slow kuliko ya kwanza unless compiler ni very smart kuweza kuzipanga katika format hiyo.
 

Forum statistics

Threads 1,388,912
Members 527,828
Posts 34,014,453
Top