概述：通過對數組進行排序，代碼更好地利用了緩存，從而提高了程式的性能。這種現象通常被稱為"緩存友好"（cache-friendly）或"空間局部性"（spatial locality） 今天做一個數組數據計算時，發現一個效率問題，給大家分享一下 一個數組排序和不排序時同樣的邏輯處理速度是不一樣的。排 ...
概述：通過對數組進行排序，代碼更好地利用了緩存，從而提高了程式的性能。這種現象通常被稱為"緩存友好"（cache-friendly）或"空間局部性"（spatial locality）
今天做一個數組數據計算時，發現一個效率問題，給大家分享一下 一個數組排序和不排序時同樣的邏輯處理速度是不一樣的。排序後速度快了近5倍，上圖：
- 再來說明原因：
這段代碼之所以在排序後運行更快，是因為它利用了現代電腦體繫結構中的一個優化：CPU緩存。
在主迴圈中，對data數組的訪問是順序的，即按照數組元素的順序依次訪問。在沒有排序的情況下，由於數組的記憶體佈局是隨機的，這可能導致對記憶體的隨機訪問，而這種隨機訪問可能導致較多的緩存缺失（cache misses）。
而在經過排序之後，數組的元素被重新排列，使得相鄰元素的值更加接近。這就意味著在主迴圈中，對數組的訪問會更加連續，這有助於提高緩存的命中率（cache hit rate）。高緩存命中率意味著CPU可以更快地獲取數據，而不必等待緩慢的主記憶體。這對於迴圈中的迭代非常重要，因為它會不斷地訪問數組的不同部分。
通過對數組進行排序，代碼更好地利用了緩存，從而提高了程式的性能。這種現象通常被稱為"緩存友好"（cache-friendly）或"空間局部性"（spatial locality）。
- 然後來看看實際測試代碼,不排序測試：
static void Main()
{
double elapsedTime = Test1();
double elapsedTime2 = Test2();
Console.WriteLine($"排序前後：Test1/Test2={(double)(elapsedTime / elapsedTime2)}");
Console.ReadKey();
}
/// <summary>
/// 不排序測試
/// </summary>
static double Test1()
{
// 生成數據
const int arraySize = 32768;
int[] data = new int[arraySize];
Random rand = new Random();
for (int c = 0; c < arraySize; ++c)
data[c] = rand.Next(256); // 生成0-255的隨機數
// 測試
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
for (int c = 0; c < arraySize; ++c)
{ // 主迴圈
if (data[c] >= 128)
sum += data[c]; // 如果數據大於等於128，則加到總和中
}
}
stopwatch.Stop();
double elapsedTime = stopwatch.ElapsedMilliseconds; // 計算所花費的時間
Console.WriteLine($"不排序效果：用時{elapsedTime}毫秒"); // 輸出所花費的時間
Console.WriteLine("sum = " + sum); // 輸出總和
Console.WriteLine();
return elapsedTime;
}- 排序後的測試代碼：
/// <summary>
/// 排序測試
/// </summary>
/// <returns></returns>
static double Test2()
{
// 生成數據
const int arraySize = 32768;
int[] data = new int[arraySize];
Random rand = new Random();
for (int c = 0; c < arraySize; ++c)
data[c] = rand.Next(256); // 生成0-255的隨機數
double elapsedTime = 0;
// 測試
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
// 對數據進行排序，這樣下一個迴圈會運行得更快
Array.Sort(data);
stopwatch.Stop();
elapsedTime = stopwatch.ElapsedMilliseconds; // 計算所花費的時間
stopwatch.Restart();
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
for (int c = 0; c < arraySize; ++c)
{ // 主迴圈
if (data[c] >= 128)
sum += data[c]; // 如果數據大於等於128，則加到總和中
}
}
stopwatch.Stop();
double elapsedTime2 = stopwatch.ElapsedMilliseconds; // 計算所花費的時間
double elapsedTime3 = (elapsedTime + elapsedTime2);
Console.WriteLine($"排序後效果：排序用時{elapsedTime}毫秒，計算用時:{elapsedTime2}毫秒,合計用時：{(elapsedTime3)}毫秒"); // 輸出所花費的時間
Console.WriteLine("sum = " + sum); // 輸出總和
Console.WriteLine();
return elapsedTime3;
}大家在Java、C++、Python是不是也遇到過類似的問題。
源代碼獲取：https://pan.baidu.com/s/1vm6faDdFFGFEmvpLMPATcQ?pwd=6666
