文章目錄
- 一、陣列在記憶體的存盤方式
- 二、代碼示例及結果
- 三.分析
一、陣列在記憶體的存盤方式
陣列是資料結構的基礎，之所以這么說是因為陣列反映了記憶體的物理結構，在記憶體中，陣列是連續分布的，而在程式中，往往要在記憶體中分配一塊連續的空間來使用，例如，在影像處理鄰域，耳熟能詳的opencv中有一資料型別Mat，我們一般都會以Mat來存盤影像資料，Mat是一個二維陣列，可以通過兩個for回圈遍歷影像上各個像素值，有人習慣按行優先遍歷，有人喜歡按列優先遍歷，表面上看，這兩中寫法的時間復雜度都是O(nm)（n表示影像的高，m表示影像的寬),可實際上是否都是O(nm)呢？
二、代碼示例及結果
列優先遍歷代碼如下（示例）：
Mat src = imread("image0.jpg", IMREAD_GRAYSCALE);
if (!src.empty())
imshow("src", src);
int nums = 10;
while (nums)
{
double t = (double)getTickCount();
for (int i = 0; i < src.cols; i++)
{
for (int j = 0; j < src.rows; j++)
{
uchar srcValue = src.at<uchar>(j, i);
}
}
t = ((double)getTickCount() - t) / getTickFrequency(); //獲得時間，單位是秒
cout << "time:" << t<<"ms"<<endl;
nums--;
}
通過一個回圈，重復測驗了10次，列優先遍歷的時間耗時通過控制臺列印如下：
行優先遍歷代碼如下（示例）：
Mat src = imread("image0.jpg", IMREAD_GRAYSCALE);
if (!src.empty())
imshow("src", src);
int nums = 10;
while (nums)
{
double t = (double)getTickCount();
for (int i = 0; i < src.rows; i++)
{
for (int j = 0; j < src.cols; j++)
{
uchar srcValue = src.at<uchar>(i, j);
}
}
t = ((double)getTickCount() - t) / getTickFrequency(); //獲得時間，單位是秒
cout << "time:" << t<<"ms"<<endl;
nums--;
}
同樣，行優先遍歷也通過一個回圈，重復測驗了10次，時間耗時通過控制臺列印如下：
通過以上測驗可以發現，行優先遍歷的方式比列優先效率快，
三.分析
1. CPU高速快取（英語：CPU Cache）：在計算機系統中，CPU高速快取是用于減少處理器訪問記憶體所需平均時間的部件，當處理器發出記憶體訪問請求時，會先查看快取內是否有請求資料，如果存在（命中），則不經訪問記憶體直接回傳該資料；如果不存在（失效），則要先把記憶體中的相應資料載入快取，再將其回傳處理器，快取之所以有效，主要是因為程式運行時對記憶體的訪問呈現區域性（Locality）特征，這種區域性既包括空間區域性（Spatial Locality），也包括時間區域性（Temporal Locality），有效利用這種區域性，快取可以達到極高的命中率，（百度百科解釋），
2.虛擬記憶體：虛擬記憶體被作業系統用以管理記憶體，對物理記憶體進行擴展，其作用是替代物理記憶體的部分作業來運行程式，讓作業系統就可以運行更多的程式，同時執行更多的任務，
3.二維陣列在記憶體中的存盤結構如下圖：資料在記憶體中是以行優先的方式存盤，
4.代碼測驗的影像大小為4096X1200,位深度為8，如下圖，之所以行優先遍歷的方式比列優先效率快，是因為cpu在訪問記憶體地址的時候，首先訪問的是虛擬記憶體，檢查TLB，映射成對應的物理地址進行資料訪問，如果命中，會得到其物理地址，之后會訪問cache，如果cache中有要訪問的資料，那么本次訪問就結束，如果沒有，就到記憶體中尋找，并更新cache；如果TLB不命中，那么那么系統內核會呼叫缺頁例外處理程式去處理，這個程序中會進行頁替換等操作，最終取得要訪問的資料，而記憶體的物理地址中，二維陣列是以行優先的順序存盤，測驗影像資料大小為4096X1200位元組，假設記憶體頁為4096位元組，那么按行優先遍歷，遍歷完一行則中斷一次缺頁，整個程序只需要中斷1200次缺頁例外，進行頁替換，而按列優先遍歷，每遍歷一個元素便中斷一次缺頁例外，整個程序4096X1200次中斷，可想而知，按列優先遍歷產生中斷耗時比按行優先遍歷大了許多，而實際中物理記憶體一般比較充足，系統分配的頁記憶體遠遠不止4096位元組，所以缺頁中斷的次數不會這么多，同理，如果檢查TLB命中，得到其物理地址之后會訪問cache，如果cache沒有要訪問的資料，就到記憶體中尋找，并更新cache；由于二維陣列在記憶體中的存盤方式，按列優先遍歷訪問cache的命中率比按行優先遍歷的低，
綜上所述：行優先遍歷的方式比列優先效率快，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296778.html
標籤：其他