首页 > 其他分享 >一个操作让数组处理速度快了5倍,到底是为什么

一个操作让数组处理速度快了5倍,到底是为什么

时间:2024-03-24 14:46:14浏览次数:20  
标签:处理速度 到底 int double elapsedTime 数组 stopwatch 排序 data

 

概述:通过对数组进行排序,代码更好地利用了缓存,从而提高了程序的性能。这种现象通常被称为"缓存友好"(cache-friendly)或"空间局部性"(spatial locality)

今天做一个数组数据计算时,发现一个效率问题,给大家分享一下 一个数组排序和不排序时同样的逻辑处理速度是不一样的。排序后速度快了近5倍,上图:

 

  1. 再来说明原因:

这段代码之所以在排序后运行更快,是因为它利用了现代计算机体系结构中的一个优化:CPU缓存。

在主循环中,对data数组的访问是顺序的,即按照数组元素的顺序依次访问。在没有排序的情况下,由于数组的内存布局是随机的,这可能导致对内存的随机访问,而这种随机访问可能导致较多的缓存缺失(cache misses)。

而在经过排序之后,数组的元素被重新排列,使得相邻元素的值更加接近。这就意味着在主循环中,对数组的访问会更加连续,这有助于提高缓存的命中率(cache hit rate)。高缓存命中率意味着CPU可以更快地获取数据,而不必等待缓慢的主内存。这对于循环中的迭代非常重要,因为它会不断地访问数组的不同部分。

通过对数组进行排序,代码更好地利用了缓存,从而提高了程序的性能。这种现象通常被称为"缓存友好"(cache-friendly)或"空间局部性"(spatial locality)。

  1. 然后来看看实际测试代码,不排序测试:
        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;
        }
  1. 排序后的测试代码:
        /// <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 

 

标签:处理速度,到底,int,double,elapsedTime,数组,stopwatch,排序,data
From: https://www.cnblogs.com/hanbing81868164/p/18092404

相关文章

  • JAVA数组和内存
    目录数组的概述和静态初始化介绍定义数组的初始化静态初始化动态初始化区别索引数组遍历常见问题数组练习求最值交换数据打乱数据数组的内存图!两个数组指向同一个空间的内存图总结数组的概述和静态初始化介绍1、数组是一种容器,用来存放同种数据类型的......
  • Java零基础-数组
    哈喽,各位小伙伴们,你们好呀,我是喵手。  今天我要给大家分享一些自己日常学习到的一些知识点,并以文字的形式跟大家一起交流,互相学习,一个人虽可以走的更快,但一群人可以走的更远。  我是一名后端开发爱好者,工作日常接触到最多的就是Java语言啦,所以我都尽量抽业余时间把......
  • Java零基础-数组:异常处理和错误处理
    哈喽,各位小伙伴们,你们好呀,我是喵手。  今天我要给大家分享一些自己日常学习到的一些知识点,并以文字的形式跟大家一起交流,互相学习,一个人虽可以走的更快,但一群人可以走的更远。  我是一名后端开发爱好者,工作日常接触到最多的就是Java语言啦,所以我都尽量抽业余时间把......
  • 和为 K 的子数组 - LeetCode 热题 10
    大家好!我是曾续缘......
  • 后缀数组学习笔记(未完成
    后缀数组定义与实现定义后缀从字符串某个位置i到字符串末尾的子串,定义s的第i个字符为第一个元素的后缀为suf(i)。后缀数组把s的每一个后缀按照字典序排序,后缀数组sa[i]表示排名为i的后缀的起始位置的下标。rk[i]数组代表起始位置为i的后缀的排名。rk[]和sa[]是一一对应关系......
  • C105 整体二分+树状数组 P2617 Dynamic Rankings
    视频链接:C105整体二分+树状数组P2617DynamicRankings_哔哩哔哩_bilibili  C96树状数组套权值线段树P2617DynamicRankings-董晓-博客园(cnblogs.com)C104【模板】整体二分+树状数组P3834可持久化线段树2-董晓-博客园(cnblogs.com)LuoguP2617Dynamic......
  • HashMap的数组最大容量为什么要设计为2的30次方?而不是2的31次方-1?数组容量为什么一定
    目录问题 数组容量为什么一定要设计为2的幂(2的n次方)?1、首先要清楚HashMap的底层基本原理2、再来看下怎么通过hash值决定存放在哪个桶中?首先看下hash值再看下怎么确定当前key存放在哪个数组下标下的为什么要做按位与而不用模运算符%?为什么要n-1呢?n是一个什么样的数......
  • 100道面试必会算法-09-最大子数组和(初探动态规划)
    100道面试必会算法-09-最大子数组和(初探动态规划)题目一个整数数组nums,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。子数组是数组中的一个连续部分。示例1:输入:nums=[-2,1,-3,4,-1,2,1,-5,4]输出:6解释:连续子数组[4,-1,2,1]的和最大,......
  • BUGAWAY算法小抄-树状数组(2024.03.23 更新)
    什么是树状数组?树状数组是支持单点修改和区间查询的、代码量小的数据结构。事实上,树状数组能解决的问题是线段树(一棵二叉树,每个节点表示一个区间,并存储该区间的一些相关信息。线段树可以高效地进行区间查询和区间更新操作。不是本文重点)能解决的问题的子集:树状数组能做的,线段树......
  • 用函数和数组实现扫雷游戏(从0开始)
    文章目录概要整体架构流程(这里用VS2023来制作)代码实现小结概要学完数组和函数后我们可以通过所学知识写一个扫雷游戏,并实现一些拓展功能。我们采用多文件联调的模式来制作,这里需要先建好三个文件game.hgame.cminesweeper.c整体架构流程(这里用VS2023来制作)在......