ToB企服应用市场:ToB评测及商务社交产业平台

标题: 一个操作让数组处理速率快了5倍，到底是为什么 [打印本页]

---

作者: 徐锦洪    时间: 2024-5-15 05:36
标题: 一个操作让数组处理速率快了5倍，到底是为什么

 
概述：通过对数组进行排序，代码更好地利用了缓存，从而提高了程序的性能。这种征象通常被称为"缓存友好"（cache-friendly）或"空间局部性"（spatial locality）
本日做一个数组数据计算时，发现一个效率问题，给大家分享一下 一个数组排序和不排序时同样的逻辑处理速率是不一样的。排序后速率快了近5倍，上图：

 

• 再来阐明原因：
  

这段代码之所以在排序后运行更快，是因为它利用了现代计算机体系结构中的一个优化：CPU缓存。
在主循环中，对data数组的访问是次序的，即按照数组元素的次序依次访问。在没有排序的情况下，由于数组的内存结构是随机的，这可能导致对内存的随机访问，而这种随机访问可能导致较多的缓存缺失（cache misses）。
而在经过排序之后，数组的元素被重新排列，使得相邻元素的值更加接近。这就意味着在主循环中，对数组的访问会更加一连，这有助于提高缓存的命中率（cache hit rate）。高缓存命中率意味着CPU可以更快地获取数据，而不必等待痴钝的主内存。这对于循环中的迭代非常紧张，因为它会不停地访问数组的差别部分。
通过对数组进行排序，代码更好地利用了缓存，从而提高了程序的性能。这种征象通常被称为"缓存友好"（cache-friendly）或"空间局部性"（spatial locality）。

• 然后来看看实际测试代码,不排序测试：
  

1.         static void Main()
2.         {
3.             double elapsedTime = Test1();
4.             double elapsedTime2 = Test2();
6.             Console.WriteLine($"排序前后：Test1/Test2={(double)(elapsedTime / elapsedTime2)}");
7.             Console.ReadKey();
8.         }
10.         /// <summary>
11.         /// 不排序测试
12.         /// </summary>
13.         static double Test1()
14.         {
15.             // 生成数据
16.             const int arraySize = 32768;
17.             int[] data = new int[arraySize];
18.             Random rand = new Random();
20.             for (int c = 0; c < arraySize; ++c)
21.                 data[c] = rand.Next(256);  // 生成0-255的随机数
23.             // 测试
24.             Stopwatch stopwatch = new Stopwatch();
25.             stopwatch.Start();
27.             long sum = 0;
28.             for (int i = 0; i < 100000; ++i)
29.             {
30.                 for (int c = 0; c < arraySize; ++c)
31.                 {   // 主循环
32.                     if (data[c] >= 128)
33.                         sum += data[c];  // 如果数据大于等于128，则加到总和中
34.                 }
35.             }
37.             stopwatch.Stop();
38.             double elapsedTime = stopwatch.ElapsedMilliseconds;  // 计算所花费的时间
40.             Console.WriteLine($"不排序效果：用时{elapsedTime}毫秒");  // 输出所花费的时间
41.             Console.WriteLine("sum = " + sum);  // 输出总和
42.             Console.WriteLine();
43.             return elapsedTime;
44.         }

复制代码

• 排序后的测试代码：
  

1.         /// <summary>
2.         /// 排序测试
3.         /// </summary>
4.         /// <returns></returns>
5.         static double Test2()
6.         {
7.             // 生成数据
8.             const int arraySize = 32768;
9.             int[] data = new int[arraySize];
10.             Random rand = new Random();
12.             for (int c = 0; c < arraySize; ++c)
13.                 data[c] = rand.Next(256);  // 生成0-255的随机数
16.             double elapsedTime = 0;
17.             // 测试
18.             Stopwatch stopwatch = new Stopwatch();
19.             stopwatch.Start();
21.             // 对数据进行排序，这样下一个循环会运行得更快
22.             Array.Sort(data);
23.             stopwatch.Stop();
24.             elapsedTime = stopwatch.ElapsedMilliseconds;  // 计算所花费的时间
25.             stopwatch.Restart();
27.             long sum = 0;
28.             for (int i = 0; i < 100000; ++i)
29.             {
30.                 for (int c = 0; c < arraySize; ++c)
31.                 {   // 主循环
32.                     if (data[c] >= 128)
33.                         sum += data[c];  // 如果数据大于等于128，则加到总和中
34.                 }
35.             }
37.             stopwatch.Stop();
38.             double elapsedTime2 = stopwatch.ElapsedMilliseconds;  // 计算所花费的时间
40.             double elapsedTime3 = (elapsedTime + elapsedTime2);
42.             Console.WriteLine($"排序后效果：排序用时{elapsedTime}毫秒，计算用时:{elapsedTime2}毫秒,合计用时：{(elapsedTime3)}毫秒");  // 输出所花费的时间
43.             Console.WriteLine("sum = " + sum);  // 输出总和
44.             Console.WriteLine();
46.             return elapsedTime3;
47.         }

复制代码

大家在Java、C++、Python是不是也碰到过类似的问题。
源代码获取：https://pan.baidu.com/s/1vm6faDdFFGFEmvpLMPATcQ?pwd=6666 
 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4