0

我读过关于空间和时间的地方。

就几句话。

时间局部性：程序经常重复访问相同的内存位置。

空间局部性：程序也经常重复访问相邻的内存位置。

现在我要分析以下代码以查找所有出现的时间和空间参考局部性。

for (int i = 0, j = 10; i < 100; i++)
    a[i] = j++;

我只知道以下几点。

空间

  • a[i] = j++;参考后a[i]我们即将参考a[i+1]。
  • 执行所有这些操作的指令彼此相邻地存储在内存中。

颞

  • i与 100 相比。
  • i加一：i++.
  • 赋值a[i] = j++用作i数组索引。
  • 用于a索引每个a[i].
  • j由 assignment 中的 1 递增a[i] = j++。

那么我在所有这些方面都是正确的吗？我是否错过了其他东西？

4

1 回答 1

2

定义则相反。

空间局部性 - 空间局部性，访问附近的内存位置。

时间局部性 - 时间局部性，多次访问同一位置。

在设计缓存时使用空间局部性是这样的，当您的程序需要时a[i]，缓存不会a[i]从内存中获取。它获取的条目a[i], a[i+1], a[i+2] ...与缓存行的大小一样少。通过这样做，缓存预计您可能a[i+1]很快就会访问。当你这样做时，缓存不需要从内存中获取它，由于使用了空间局部性，它已经存在了。

当您访问i和时，时间局部性就出现了j。每次你需要iandj时，不需要从内存中获取它，因为它是缓存的。通过缓存，i和j，缓存认为你会再次访问它，这样可以节省从内存中获取它的时间。

并且要回答确切的问题，是的，您已经确定了空间和时间局部性的位置。唯一不正确的是，您的陈述，“执行所有这些操作的指令都存储在内存中”。不会有单独的访问说明a[i]，a[i+1]. 它将是在循环中使用的单个指令，使用每次计算的内存地址。正如我上面解释的那样，优点是缓存不需要为下一次迭代获取数据，因为它很可能作为循环中早期迭代的一部分来获取。

于 2017-03-30T14:10:02.313 回答