Consider below two C language functions to compute sum of elements in a 2D array. Ignoring the compiler optimizations, which of the two is better implementation of sum?

[ad type=”banner”] [pastacode lang=”c” manual=”%2F%2F%20Function%201%0Aint%20fun1(int%20arr%5BR%5D%5BC%5D)%0A%7B%0A%20%20%20%20int%20sum%20%3D%200%3B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3CR%3B%20i%2B%2B)%0A%20%20%20%20%20%20for%20(int%20j%3D0%3B%20j%3CC%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20sum%20%2B%3D%20arr%5Bi%5D%5Bj%5D%3B%0A%7D%0A%20%0A%2F%2F%20Function%202%0Aint%20fun2(int%20arr%5BR%5D%5BC%5D)%0A%7B%0A%20%20%20%20int%20sum%20%3D%200%3B%0A%20%20%20%20for%20(int%20j%3D0%3B%20j%3CC%3B%20j%2B%2B)%0A%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3CR%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20sum%20%2B%3D%20arr%5Bi%5D%5Bj%5D%3B%0A%7D” message=”” highlight=”” provider=”manual”/]

In C/C++, elements are stored in Row-Major order. So the first implementation has better spatial locality (nearby memory locations are referenced in successive iterations). Therefore, first implementation should always be preferred for iterating multidimensional arrays.

Categorized in:

Analysis of Algorithm

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,