一個操作讓數組處理速度快了5倍，到底是為什麼

概述：通過對數組進行排序，代碼更好地利用了緩存，從而提高了程式的性能。這種現象通常被稱為"緩存友好"（cache-friendly）或"空間局部性"（spatial locality）

今天做一個數組數據計算時，發現一個效率問題，給大家分享一下 一個數組排序和不排序時同樣的邏輯處理速度是不一樣的。排序後速度快了近5倍，上圖：

1. 再來說明原因：

這段代碼之所以在排序後運行更快，是因為它利用了現代電腦體繫結構中的一個優化：CPU緩存。

在主迴圈中，對data數組的訪問是順序的，即按照數組元素的順序依次訪問。在沒有排序的情況下，由於數組的記憶體佈局是隨機的，這可能導致對記憶體的隨機訪問，而這種隨機訪問可能導致較多的緩存缺失（cache misses）。

而在經過排序之後，數組的元素被重新排列，使得相鄰元素的值更加接近。這就意味著在主迴圈中，對數組的訪問會更加連續，這有助於提高緩存的命中率（cache hit rate）。高緩存命中率意味著CPU可以更快地獲取數據，而不必等待緩慢的主記憶體。這對於迴圈中的迭代非常重要，因為它會不斷地訪問數組的不同部分。

通過對數組進行排序，代碼更好地利用了緩存，從而提高了程式的性能。這種現象通常被稱為"緩存友好"（cache-friendly）或"空間局部性"（spatial locality）。

2. 然後來看看實際測試代碼,不排序測試：

        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;
        }

3. 排序後的測試代碼：

        /// <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