arrays - 花费 O(1) 时间的数组访问是否可以改进？

Question

我一直在读一本分配给类(class)的书，它提到数组访问需要 O(1) 时间。我意识到这非常快(也许尽可能快)，但是如果您有一个循环必须多次引用它，那么分配一个临时变量以在数组中查找值有什么好处吗？或者使用临时变量仍然是 O(1) 吗？

我假设这个问题与语言无关。我还意识到，即使答案是肯定的，但优势很小，我只是好奇。

Answer 1

请注意，O(1) 并不意味着“瞬时”。它只是意味着“至多某个常数”。这意味着 1 和 10¹⁰⁰⁰ 都是 O(1)，尽管其中第二个比宇宙中的原子数还要大。

如果多次重复访问同一个数组元素，则每次访问将花费 O(1) 时间。将该数组元素存储在局部变量中也会提供 O(1) 查找时间，但常量可能不同。选择一个选项可能比其他选项更好，但您确实必须分析该程序才能确定。

实际上，这种微优化不太可能对程序时间产生可测量的影响，除非您正在运行的代码占程序运行时间的很大一部分。如果我发现一个示例，其中此更改会对任何实际代码产生显着影响，我会感到震惊。

现代架构可能会使这种变化更快一些，但不会太快。如果您多次访问同一数组元素，处理器可能会将数组的该部分保留在缓存中，从而使查找速度非常快。此外，一个好的优化编译器可能已经为您将非本地复制代码转换为本地复制代码。

希望这有帮助!