具有数组的时间与空间位置

Question

我对空间和时间局部的含义有点困惑.我希望通过一个数组示例来看它,这将有助于我更好地理解它.

在这样的例子中:A [0] [1],A [0] [2],A [0] [3] ......等

这是否证明了时间局部性？我看到同一行被多次访问但是在不同的偏移处...这是否意味着访问了不同的地址？

另外,我说的是这样的例子:A [1],A [2],A [3] ......等等

展示空间位置？

希望对实时代码中时空局部性如何工作的一些澄清将有助于我更好地理解它们.

Answer 1

空间和时间局部性描述了程序如何访问数据(或指令)的两个不同特征.维基百科有一篇关于参考地点的好文章.

spatial如果在时间上接近引用的事物在空间中也很近(附近的存储器地址,磁盘上的附近扇区等),则称一系列引用具有局部性.temporal如果对同一事物的访问在时间上聚集,则称序列具有局部性.

如果一个程序访问一个大数组中的每个元素并读取它一次然后移动到下一个元素并且不再重复访问任何给定位置,直到它触及每个其他位置,那么它是空间局部性的明显情况但不是时间局部性.另一方面,如果程序在移动到另一个随机子集之前花费时间重复访问阵列上的位置的随机子集,则称其具有时间局部性但不具有空间局部性.编写良好的程序将具有将一起访问的内容组合在一起的数据结构,从而确保空间局部性.如果你的程序有可能访问乙它访问后不久,一则这两个一和乙应彼此接近分配.

你的第一个例子

A[0][1], A[0][2], A[0][3]

显示空间局部性,在时间上接近的事物在空间中很近.它没有显示时间局部性,因为您没有多次访问同一个事物.

你的第二个例子

A[1], A[2], A[3]

还显示空间局部性,但不显示时间局部性.

这是一个显示时间局部性的例子

A[1], A[2000], A[1], A[1], A[2000], A[30], A[30], A[2000], A[30], A[2000], A[30], A[4], A[4]

Answer 2

简单来说,

时间局部性:在某个时间点引用的资源将在不久的将来某个时间再次引用的概念.

空间局部性:如果仅引用资源附近的资源,则引用资源的可能性更高的概念.

来源:维基百科

Answer 3

以下是具有位置的代码示例:

var sum = 0;
for (i = 0; i < n; i++){
  for(j=0; j < m ; j++){
    sum += a[i][j];
    }
}
return sum;

• 存在时间局部性,因为在循环中频繁访问和.通过将最近使用的指令和数据值保存在高速缓存存储器中并利用高速缓存层次结构来利用时间局部性.甚至在寄存器中,根本不在内存中.

• 存在空间局部性,因为我们有一个数组'a',我们按顺序访问数组的每个元素.通常通过使用较大的高速缓存块并通过将预取机制(获取预期使用的项目)合并到高速缓存控制逻辑中来利用空间局部性.