嘉兴做网站软件,宣传片策划拍摄制作公司,用meteor框架做的微博网站,居家养老网站建设什么是局部性#xff1f;局部性分类局部性有什么作用#xff1f;局部性举例数据引用的局部性取指令的局部性结论完整代码什么是局部性#xff1f;程序倾向于使用它们最近使用的地址接近或相等的数据和指令。局部性分类局部性主要分为时间局部性和空间局部性。时间局部性局部性分类局部性有什么作用局部性举例数据引用的局部性取指令的局部性结论完整代码什么是局部性程序倾向于使用它们最近使用的地址接近或相等的数据和指令。局部性分类局部性主要分为时间局部性和空间局部性。时间局部性最近使用过的数据和指令在不久的将来可能再次被使用。具体如下图所示。时间局部性空间局部性某个地址或者某个地址附近的数据和指令可能在不久的将来再次被引用。具体如下图所示。空间局部性局部性有什么作用在现代计算机的软硬件中处处体现着局部性原理。在硬件上计算机通过引入称为高速缓存来保存最近被使用的指令和数据。在软件上操作系统用主存来缓存磁盘文件系统中最近被使用的磁盘块。在应用程序的设计中Web浏览器将最近被引用的文档放在本地磁盘上利用的就是时间局部性。作为程序员应该理解局部性原理一般来说有良好局部性的程序比局部性差的程序运行得更快。局部性举例数据引用的局部性看下下面两个函数。都是计算数组a的和。唯一的区别在于行列的访问先后顺序不同。那么这两个程序运行起来会有什么差别呢我们测试下。/*** Description: 行优先方式求二维数组a的和* Param: 整型数组a* Return: 数组a的和sum* Author: 嵌入式与Linux那些事*/int SumArrRow(int aarr[ROW][COL]){//1393.166487usint i,j,sum 0;for(i 0;i for(j 0;j sum a[i][j];printf(%d\r\n,sum);return sum;}/*** Description: 列优先方式求二维数组a的和* Param: 整型数组a* Return: 数组a的和sum* Author: 嵌入式与Linux那些事*/int SumArrCol(int a[ROW][COL]){//2083.776579usint i,j,sum 0;for(j 0;j for(i 0;i sum a[i][j];printf(%d\r\n,sum);return sum;}运算的数组为2 * 3大小。测试结果如下。15SumArrRow run_time:1039.612803us15SumArrCol run_time:2011.529889usSumArrCol函数的运行时间是SumArrRow运行时间的将近2倍。原因是什么呢首先我们要知道数组在内存中是以行优先的方式存储的。SumArrRow函数在for循环中访问a的顺序如下。地址 0 4 8 12 16 20内容 a00 a01 a02 a10 a11 a12访问顺序 1 2 3 4 5 6而SumArrRow函数中双重嵌套循环按照行优先顺序读数组的元素。也就是内层循环读第一行的元素然后读第二行依此类推。元素被访问的步长为1。和数组在内存中的存储方式是一样的因此具有很好的空间局部性。SumArrCol函数和SumArrRow函数唯一的区别是我们交换了i和j的循环。这样交换循环对它的局部性有何影响因为它按照列顺序来扫描数组而不是按照行顺序。因为C数组在内存中是按照行顺序来存放的元素被访问的步长为COL。所以其空间局部性较差。SumArrCol函数在内存中的存放方式如下所示。地址 0 4 8 12 16 20内容 a00 a01 a02 a10 a11 a12访问顺序 1 3 5 2 4 6下面再看一个时间局部性的例子。/*** Description: 求一维数组a的和* Param: 整型数组a* Return: 数组a的和sum* Author: 嵌入式与Linux那些事*/int SumArr(int a[MAX]){int i,sum 0;for(i 0;i sum a[MAX];printf(%d\r\n,sum);return sum;}SumArr单函数它对一个向量的元素求和。这个程序有良好的局部性吗要回答这个问题我们来看看每个变量的引用模式。地址 0 4 8 12 16 20内容 a0 a1 a2 a3 a4 a5访问顺序 1 2 3 4 5 6在这个例子中变量sum在每次循环迭代中被引用一次因此对于sum来说有好的时间局部性。另一方面因为sum是标量对于sum来说没有空间局部性。数组a的元素是被顺序读取的一个接一个按照它们存储在内存中的顺序(为了方便我们假设数组是从地址0开始的)。因此对于数组a函数有很好的空间局部性但是时间局部性很差因为每个数组元素只被访问一次。对于循坏体中的每个变量这个函数要么有好的空间局部性要么有好的时间局部性所以我们可以断定 SumArr函数有良好的局部性。取指令的局部性因为程序的指令是放在内存中的程序运行时CPU必须取出这些指令。SumArr中for循环体中的指令是按照连续的内存顺序执行的。因此具有很好的空间局部性。而且循环体又被执行很多次所以也有很好的时间局部性。取指令的局部性和数据引用的局部性的区别在于在程序运行时指令是不可修改的。程序只能对指令读。结论上面我们介绍了局部性的概念并给出了程序示例。现将以上内容总结如下。重复引用相同变量的程序有良好的时间局部性。对于具有步长为k的引用模式的程序步长越小空间局部性越好。在内存中以大步长跳来跳去的程序空间局部性会很差。对于取指令来说循环有好的时间和空间局部性。循环体越小循环迭代次数越多局部性越好。完整代码/** Description: 【计算机基础】程序的局部性简介* Version: V1.0* Autor: 嵌入式与Linux那些事* Date: 2020-12-21 21:40:12* LastEditors: 嵌入式与Linux那些事* LastEditTime: 2020-12-23 23:11:58*/#include #include #include #define ROW 2#define COL 3/*** Description: 行优先方式求数组a的和* Param: 整型数组a* Return: 数组a的和sum* Author: 嵌入式与Linux那些事*/int SumArrRow(int aarr[ROW][COL]){//1393.166487usint i,j,sum 0;for(i 0;i for(j 0;j sum a[i][j];printf(%d\r\n,sum);return sum;}/*** Description: 列优先方式求数组a的和* Param: 整型数组a* Return: 数组a的和sum* Author: 嵌入式与Linux那些事*/int SumArrCol(int a[ROW][COL]){//2083.776579usint i,j,sum 0;for(j 0;j for(i 0;i sum a[i][j];printf(%d\r\n,sum);return sum;}/*** Description: 求一维数组a的和* Param: 整型数组a* Return: 数组a的和sum* Author: 嵌入式与Linux那些事*/int SumArr(int arr[MAX]){int i,sum 0;for(i 0;i sum a[MAX];printf(%d\r\n,sum);return sum;}int main(){int a[ROW][COL] {0,1,2,3,4,5};double run_time;LARGE_INTEGER time_start; //开始时间LARGE_INTEGER time_over; //结束时间double dqFreq; //计时器频率LARGE_INTEGER f; //计时器频率QueryPerformanceFrequency(f);dqFreq(double)f.QuadPart;QueryPerformanceCounter(time_start); //计时开始SumArrRow(a);QueryPerformanceCounter(time_over); //计时结束run_time1000000*(time_over.QuadPart-time_start.QuadPart)/dqFreq;//乘以1000000把单位由秒化为微秒精度为1000 000/(cpu主频)微秒printf(\nSumArrRow run_time%fus\n,run_time);return 0;}
