4

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

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

4

5 回答 5

6

请注意，O(1) 并不意味着“瞬时”。它只是意味着“至多是一些常数”。这意味着 1 和 10 1000都是 O(1)，即使其中的第二个大于宇宙中的原子数。

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

在实践中，这种微优化不太可能对程序时间产生可衡量的影响，除非您正在运行的代码占程序运行时间的很大一部分。我会很震惊地找到一个例子，这个变化会对任何真实的代码产生明显的影响。

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

希望这可以帮助！

于 2013-02-07T06:39:54.603 回答
4

如果我明白了，你问的是

for (int i=0; i<len; i++) {
   int temp = ar[i];
   foo += temp;
   bar -= temp;
}

比：

for (int i=0; i<len; i++) {
   foo += ar[i];
   bar -= ar[i];
}

我不会担心它：

如果循环体中的代码要访问同一个数组条目，比如说ar[i]多次，任何中途的编译器（在非零优化级别）都会将该值保存在寄存器中以便快速重用。换句话说，编译器可能会在给定上述任一代码示例的情况下生成完全相同的程序集。

请注意，其中任何一个仍然是 O(1)（一次访问一件事）。不要将算法的大 O 表示法与指令级优化混淆。

编辑

我刚刚编译了一个带有两个函数的示例程序，包含上述两个示例，并且在-O2gcc 4.7.2 生成了完全相同的机器代码；逐字节。

于 2013-02-07T06:38:55.730 回答
1

比 O(1) 时间表现更好的唯一方法是一开始就不必做任何事情。那将是 O(0) 时间。

或者用更少的词：不。

于 2013-02-07T06:38:50.287 回答
0

现代 CPU 硬件（例如高速缓存行）中已经内置了一些东西，它们可以像您描述的那样做一些事情，但以临时变量无法做到的方式更好。甚至更好的是，不需要修改源代码。

于 2013-02-07T06:44:50.690 回答
0

不。阵列访问不是由闪闪发光和爱组成的神奇的零占用空间。从 C 中的数组索引确定地址的算法可以在这里看到。数组上的维度越多，访问速度就越慢，因为需要额外的操作（主要是muls 和条件，在成本方面）才能到达最终的一维内存地址。即使你的数组​​只有一维，你仍然需要计算基地址上的偏移量，这是一个单一的add操作，因此 O(1)。

于 2014-12-29T13:08:52.617 回答