一个操作让数组处理速度快了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