|
概述:通过对数组进行排序,代码更好地利用了缓存,从而提高了程序的性能。这种现象通常被称为"缓存友好"(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
来源:https://www.cnblogs.com/hanbing81868164/p/18092404
免责声明:由于采集信息均来自互联网,如果侵犯了您的权益,请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容,谢谢合作! |
本帖子中包含更多资源
您需要 登录 才可以下载或查看,没有账号?立即注册
x
|