arrays - 使用数组的时间与空间局部性

Question

我对空间和时间局部性的含义有些困惑。我希望通过一个数组示例来查看它，它可以帮助我更好地理解它。

在这样的示例中：A[0][1]、A[0][2]、A[0][3]....等

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

另外，我说这样的例子是否正确：A [1]，A [2]，A [3] ...等

展示空间局部性？

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

Answer 1

空间和时间局部性描述了程序如何访问数据（或指令）的两个不同特征。Wikipedia 有一篇关于参考位置的好文章。

spatial如果在时间上被引用的事物在空间上也很接近（附近的内存地址，磁盘上的附近扇区等），则称引用序列具有局部性。temporal如果对同一事物的访问在时间上聚集在一起，则称该序列具有局部性。

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

你的第一个例子

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;

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

• 存在空间局部性，因为我们有一个数组“a”，并且我们按顺序访问数组的每个元素。空间局部性通常通过使用更大的缓存块并将预取机制（获取预期使用的项目）合并到缓存控制逻辑中来加以利用。

Answer 4

尽管我记得两种类型的地方，但我断断续续地难以记住它们之间的区别。

要记住的空间局部性，请记住“顺序”副词。

时间局部性要记住，在学习排序算法的开始时，您会看到要交换的“临时变量”。例如冒泡排序。它有两个循环并且交换那里就像int temp = ......

您可以通过方式识别哪个定义属于什么。

Answer 5

时间局部性：时间局部性基于重复引用的资源。

空间局部性：空间局部性表明与最近引用的数据相邻的数据将在不久的将来被请求。

Answer 6

时间局部性是空间局部性的特例。