问题标签 [localityofreference]

据我了解，空间局部性与在不久的将来使用的附近内存有关。但是我想知道是否多次执行循环，这会导致良好的空间局部性吗？提前谢谢，如果我很难理解，对不起。

我们应该根据地方而不是概念来组织课程吗？

假设我们编写了一个程序来模拟具有三个对象的真实世界环境：汽车、道路和树木。传统的 OOP 设计建议在概念上将这 3 个单独的类分开。

但是假设汽车和道路对象在其类成员数据和方法中进行数百万次计算。由于引用的位置，我们可以通过将 Car 和 Road 混入 CarRoad 类来提高性能吗？或者如果这个例子太荒谬了，如果我们有另一个单独的 Wheel 类，它与 Car 密切相关，如果 Car 和 Wheel 类的类成员交互非常频繁，我们是否应该将它们混在一起？

分区函数是否可以快速排序其参考位置？如果有，怎么做？

我的意思是，与其他算法（如合并排序或堆排序）相比，快速排序中有什么可以提供参考的局部性？

我也读过

“快速排序中的分区步骤通常具有极好的局部性，因为它访问前后附近的连续数组元素”。

我不明白 ？

阅读这个问题和这个答案我知道访问字段会在 AOT 编译器中消耗一些性能（感谢 JVM，我可以忘记它）

现在请指导我这个场景：

两者都barMethod1()做barMethod2()同样的事情。问题是在以下情况下哪一个做得更好（在性能方面）：

1. fooObject是原始类型
2. fooObject是一个对象实例

PS请考虑访问成本和缓存未命中。

在讨论局部性原则时，我的教科书作了如下陈述：

除了仅占所有程序指令一小部分的分支和调用指令外，程序执行是顺序的。因此，在大多数情况下，要获取的指令紧跟在最后一条获取的指令之后。

作为一个新手，我觉得这很难相信。我遇到的所有代码都充满了调用指令。事实上，在我看来，调用指令实际上执行了程序中最重要的操作。

如果有人能详细说明为什么这个概念是正确的，我将不胜感激，尽管调用指令在程序中起着重要作用。

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

就几句话。

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

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

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

我只知道以下几点。

空间

• 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++。

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

考虑一个假设的 HBase 表。

• (k, m, n)密钥必须对0 到 1000 之间的 3 元组整数进行编码。
• m典型的读取是对和的范围查询n，将 的值固定为k。
• 读取负载相对于呈指数分布k。换句话说，少数几个值k负责大部分读取负载。

Alice 认为，"k-m-n"为了利用参考的局部性，密钥应该看起来像。理想情况下，一台机器应该能够服务于整个查询。

Bob 认为，"sha1(k-m)-n"为了避免热点，密钥应该看起来像：如果k=1访问非常频繁，那么所有k=1记录最好不要都在相同的几台机器上。

这两个论点对我来说都有意义。我如何确定哪个选项更具可扩展性/面向未来？有没有一种快速、实用的方法来凭经验对此进行测试？

在这个问题中，我被要求找到局部性的期望值。我明白问题的答案是什么

(n - 1) * (expected value of |π(i) − π(i − 1)|).

问题解决方案表明，期望值

|π(i) − π(i − 1)| is (n + 1) / 3.

我不明白这部分解决方案。有人可以解释一下这个推理吗？谢谢你。

我已经阅读了这个博客，但我仍然不确定位置的重要性。为什么局部性对缓存性能很重要？是因为它导致更少的缓存未命中吗？此外，如何编写程序以实现良好的局部性并因此获得良好的缓存性能？

解决两个和问题可以使用 O(n) 复杂度算法来实现，但是，我只是尝试了 O(n^2) 复杂度，这是使用 2 个嵌套循环检查每个第 i 个整数与每个其余整数对目标值，以下是 O(n^2) 实现，对于 2 个实现，nums是整数数组，n是 nums 的大小，indices是一个大小为 2 的数组，用于保存索引2个整数

这个实现在 140 毫秒内解决了这个问题。我尝试了另一种 O(n^2) 方法，即对于从 1 到 n-1 的每个 k 值，检查第 i 个整数和第 (i+k) 个整数的和与目标值，以下是实现，

如您所见，相同的循环体，但运行速度更快，运行时间为 8 毫秒。这是为什么？是否与空间局部性有关？