数组访问是否总是常数时间/ O(1)？

Question

数组访问是否总是常数时间/ O(1)？

arraysperformanceoptimization

4

以下是来自 Richard Bird 的 Functional Algorithm Design Pearls（2010年）第6页内容的翻译：

对于纯函数式编程人员，更新操作在数组大小的对数时间内完成。公平地说，过程式编程人员也认为，只有在数组很小的情况下才能实现常数时间索引和更新。

何时会出现非常数时间访问数组的情况？这与 CPU 缓存有关吗？

- cubetwo1729

1

是的，缓存未命中可能会花费多达几百条机器指令的时间。 - Basile Starynkevitch

6

你正在完全断章取义地引用那句话。 - Jeff Mercado

我同意@JeffMercado的观点。这确实是可变与不可变数组/列表/向量（或者你想叫它什么都可以）的区别。 - leppie

1

他的引用可能是断章取义了。如果你忽略他的引用，问题仍然存在。 - Ira Baxter

4个回答

2

橙子可以是红色的吗？

是的，它们可以由于许多原因而变成红色，包括：

- 您把它们染成红色。 - 您种植了一种经过基因改造的品种。 - 您在火星上种植，这是一个看起来全是红色的行星。 - （理论上可能的）实用和不切实际（虚构/或未来现实）的列表还有很多...

关键是，我认为你所问的问题实际上涉及两个正交的概念。即：

- 大O符号表示（在数学中，大O符号描述了当参数趋向于特定值或无穷大时函数的极限行为，通常以更简单的函数为基础。） - 与架构/设计应用程序以及编写代码时软硬件相关的实际问题。

换句话说，虽然大O符号的概念可以被称为学术性的，但它是分类算法复杂度（时间/空间）的最合适的方式，这就是它的作用。 没有必要用不相关的问题来混淆视听。

需要明确的是，我并不是说你不应该了解底层实现细节和工作原理，因为它们会影响你编写的软件的性能..但是把这两者混在一起是没有意义的。例如，说“数组没有常数时间访问（使用索引）”，这样的说法有意义吗？

大型数组无法适应CPU缓存，因此会产生高昂的缓存未命中成本。
在内存压力下的系统中，不管是大还是小的数组，都已经从物理内存交换到硬盘上，并且不仅受到缓存未命中的影响，而且还受到硬页错误的影响。
在极端CPU负载的系统中，读取所谓数组的线程可能会被抢占，并且可能要等待几秒钟才能执行。
在一个假设的操作系统上，它不仅使用磁盘来支持其内存，还使用了位于世界另一端的另一台计算机上的额外内存，这将使数组访问变得难以想象地缓慢。

就像我的苹果和橙子例子一样，当您阅读我越来越荒谬的例子时，希望我要表达的观点是清楚的。

结论 - 任何一天，我都会回答问题“数组是否具有常数时间O（1）访问（使用索引）”，答案是是的..毫无疑问或如果和但是，他们确实。

“编辑：”

“换句话说——如果O（1）不是答案……那么O（log n）、O（n log n）、O（n ^ 2）或O（n ^ 3）也不是答案……当然也不是42。”

- Vikas Gupta

不好意思，我脑海中又冒出更多的评论了 :) - 等到量子计算机变得商业化实用和可行.. 那么这类问题的答案将是一个响亮的“是”.. 这一切都可以在常数时间内完成.. :D (注 - 我对量子计算一无所知) - Vikas Gupta

1

他正在谈论计算模型，特别是基于单词(word-based)的RAM机器。

RAM机器是对实际计算机的形式化描述：我们将计算机内存建模为一个包含w位每个单词的大数组，我们可以在O(1)时间内读写任何单词。

但我们还需要定义一些重要的内容：单词应该有多大？

我们需要一个单词大小w ≥ Ω(log n)，以至少能够寻址我们输入的n部分。因此，基于单词(word-based)的RAM通常假定单词长度为O(log n)。

然而，将机器的单词长度与输入大小相关联似乎很奇怪，也不现实。

如果保持单词长度固定呢？那么即使跟随指针也需要Ω(log n)时间才能读取整个指针。

我们需要Ω(log n)个单词来存储指针，需要Ω(log n)的时间来访问输入元素。

- Nicola Bizzoca

我认为你应该补充说明，从这个模型推导出来的理论O(n)与现实几乎没有任何联系：现代计算机在64位上进行数学运算的速度与8位相同，由于CPU与RAM之间的通信是以更长的缓存行为单位的，所有延迟完全独立于大小。在真实的计算机中，数组索引操作完全独立于数组的大小。 - cmaster - reinstate monica

是的，这些模型并没有涵盖开发人员必须考虑的复杂性。一些工作始于缓存无关结构，由Frigo等人引入（1999年）。 - Nicola Bizzoca

@cmaster：你从未有过一个足够大的数组来迫使你的机器进行分页吗？ - Ira Baxter

0

如果一种语言支持稀疏数组，那么对数组的访问将必须通过一个目录进行，而树形目录将具有非线性访问时间。或者你是指现实条件吗？;-)

- Andras

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ira Baxter · Accepted Answer

大多数现代机器体系结构都试图提供对内存的小单元时间访问，但它们失败了。相反，我们看到具有不同速度的缓存层。问题很简单：光速太慢。如果你需要一个巨大的内存[数组]（极端情况下，想象一下大小等于仙女座星系的内存），它将占用巨大的空间，而光线无法在短时间内穿过巨大的空间。信息不能比光速更快地传输。物理学从一开始就阻碍了你。所以你能做的最好的事情就是把内存的一部分“靠近”光只需花费纳秒级别的时间就可以穿过的地方（因此寄存器和L1缓存），将内存的另一部分远离（磁盘驱动器）。其他实际的复杂情况也会出现，比如电容（想象惯性）会减慢对距离更远的物品的访问速度。现在，如果您愿意将最远的内存元素的访问时间视为“单位”时间，那么是的，所有内容的访问都需要相同的时间，例如O(1)。在实际计算中，我们大多数时候都将RAM内存视为这种方式，并且我们忽略其他较慢的设备，以避免破坏我们的简单模型。然后你会发现有些人对此不满意，于是你就会有人优化缓存行访问。因此，理论上可能是O(1)，并且对于小数组（适合第一级缓存）来说表现得像O(1)，但在实践中通常都不是。一个极端的实际案例是一个无法适应主内存的数组;现在，数组访问可能会导致从磁盘进行分页。有时我们甚至不在乎这种情况。谷歌本质上是一个巨大的缓存。我们倾向于将Google搜索视为O(1)。