我是靠谱客的博主 美满鸡翅,这篇文章主要介绍常用概念之程序局部性原理程序局部性原理,现在分享给大家,希望可以做个参考。

程序局部性原理

  程序的局部性原理是指程序在执行时呈现出局部性规律,即在一段时间内,整个程序的执行仅限于程序中的某一部分。它们倾向于引用的数据项邻近于其他最近引用过的数据项,或者邻近于最近自我引用过的数据项。
  在现代计算机系统的各个层次,从硬件到操作系统、应用程序等,设计上都利用了局部性原理。比如缓存机制,CPU指令顺序处理等。
  局部性通常有两种形式:时间局部性和空间局部性,下面分别进行简单介绍。


时间局部性(temporal locality)

  时间局部性是指如果程序中的某条指令一旦执行,则不久之后该指令可能再次被执行;如果某数据被访问,则不久之后该数据可能再次被访问。强调数据的重复访问。
  利用时间局部性,缓存在现代程序系统中扮演着重要角色,数据缓存,磁盘缓存,文件缓存等,极大提高数据的重复访问性能。而在程序设计中,循环体则是时间局部性常见的一个场景:

复制代码
1
2
3
4
5
6
7
8
9
10
int sum(std::vector<int>& vecNums) { int nSum = 0; int nNumsLen = vecNums.size(); for (int nIndex = 0; nIndex < nNumsLen; nIndex++) { nSum += vecNums[nIndex]; } return nSum; }

示例中nSum及nNumsLen具有较好的时间局部性。

空间局部性(spatial locality)

  空间局部性是指一旦程序访问了某个存储单元,则不久之后。其附近的存储单元也将被访问。强调连续空间数据的访问,一般顺序访问每个元素(步长为1)时具有最好的空间局部性,步长越大,空间局部性越差。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* * 我们知道,二维数组在内存是线性存储的,按行排列 * sumarrayrows函数中按行访问每个数据,内存中是顺序访问的,步长为1 * sumarraycols函数中按列访问数据,步长为M,空间局部性较差 */ int sumarrayrows(int a[M][N]) { int nSum = 0; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { nSum += a[i][j]; } } return nSum; } int sumarraycols(int a[M][N]) { int nSum = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { nSum += a[j][i]; } } return nSum; }

最后

以上就是美满鸡翅最近收集整理的关于常用概念之程序局部性原理程序局部性原理的全部内容,更多相关常用概念之程序局部性原理程序局部性原理内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(77)

评论列表共有 0 条评论

立即
投稿
返回
顶部