為什么很少有人按列去遍歷訪問二維數(shù)組呢？

分享一道360的C語言筆試題。x是一個(gè)行列均為1000的二維數(shù)組，下面代碼運(yùn)行效率最高的是哪個(gè)？

二維數(shù)組大家都很熟悉，正常人遍歷二維數(shù)組都是一行一行來的，為什么很少有人按列去遍歷？

這道筆試題其實(shí)考察的就是遍歷效率的問題。

選項(xiàng)A，j是行，i是列，很顯然 x[i][j] 是按列訪問，先是第一列第一個(gè)元素，然后第一列第二個(gè)元素，以此類推。



選項(xiàng)B和選項(xiàng)C都存在按列訪問。

只有選項(xiàng)D，屬于正常的按行遍歷。

那么問題來了，為什么二維數(shù)組按行遍歷比按列遍歷來的快？

這個(gè)涉及的問題就太多了，得從CPU高速緩存講起。



CPU處理速度很快，但是訪問內(nèi)存太慢，嚴(yán)重影響了機(jī)器運(yùn)行效率。

于是就出現(xiàn)了高速緩存。

從名字應(yīng)該能看出，訪問它速度確實(shí)快。

當(dāng)CPU發(fā)出內(nèi)存訪問請求時(shí)，會(huì)首先查看緩存內(nèi)是否有請求的數(shù)據(jù)，如果有，直接返回，如果沒有，就要先把內(nèi)存中的數(shù)據(jù)載入緩存，再把它返回給處理器。

由于緩存比內(nèi)存貴很多，所以它的大小一般都以KB或者M(jìn)B為單位，如果是一級(jí)緩存，那就更小了。

題目中的二維數(shù)組大小接近4M，CPU在訪問的時(shí)候，緩存先從內(nèi)存抓取數(shù)據(jù)，而且一般都是抓取相鄰整個(gè)數(shù)據(jù)塊，簡單點(diǎn)理解，就是當(dāng)前行以及后面的部分?jǐn)?shù)據(jù)，這也符合內(nèi)存訪問局部性特征。

如果二維數(shù)組按列遍歷，就需要不斷的抓取內(nèi)存的數(shù)據(jù)，降低程序效率，這也將會(huì)失去緩存的意義。

審核編輯：劉清