2019年2月7日 星期四

[資料結構]關於陣列效能的改善

本篇文章探討陣列元素讀取的順序對效能的影響。

首先我們來看看這段用C++編寫的程式碼


解析:
我們在第5到第8行利用指標建構了一個8192*8192的陣列,隨後在第10行做起動計時器的動作。

在第11到第13行,我們利用迴圈將陣列填滿0。

在第14行,我們停止計時器,計算填滿陣列所花費的時間。

執行結果如下

此次填滿陣列花費了136毫秒


接著,我們對調行與列的位置,然後再執行一次程式

執行結果如下


此次填滿陣列花費了823毫秒,比上一次多花費了687毫秒

同樣都是填滿陣列的動作,為什麼會有如此可觀的時間差距呢。

以第一支程式來看,填滿陣列的動作是由左至右執行。


但是,第二支程式將行列的位置對調了,執行的順序變成由上至下執行。


這樣會造成什麼影響呢,從程式碼的第5到第8行中,可看出我們創造出的是以列為主的陣列。

在第一支程式中,一次填滿一列,填完一列再填滿下一列,只需花費136毫秒。

但是在第二支程式中,每填完一個元素,指標位置就得挪到下一列,直到填完整行元素後,指標位置才回到第一列的位置,浪費了不少移動時間。