數組訪問總是恆定時間/ O（1）？

Question

從理查德伯德，Pearls of Functional Algorithm Design（2010），第6頁：

對於純功能程序員，更新操作需要對數時間在所述陣列的大小。公平地說，程序員程序員也認識到，恆定索引和更新 只有在數組很小時纔有可能。

在什麼情況下數組具有非常數時間訪問？這與CPU緩存有關嗎？

Answer 1

大多數現代機器架構嘗試提供小的單位時間訪問內存。

它們失敗。相反，我們看到不同速度的緩存層。

問題很簡單：光速。如果你需要一個巨大的記憶[陣列]（在極端情況下，想象一下仙女座星系大小的記憶），它將需要巨大的空間，光線不能在短時間內穿過巨大的空間。信息的傳播速度不能超過光速。你從一開始就被物理學搞砸了。

所以你可以做的最好的事情就是構建「附近」內存的一部分內存，光線只需要幾納秒的時間來遍歷（因此寄存器和L1緩存）以及部分內存很遠（磁盤驅動器）。其他的實際併發症也隨之而來，例如電容（認爲慣性）會減慢對事物的進一步訪問速度。現在，如果你願意將最遠記憶元素的訪問時間作爲「單位」時間，那麼對所有事物的訪問都需要相同的時間，例如O（1）。在實際計算中，我們大多數時候以這種方式處理RAM內存，而我們忽略了其他較慢的設備，以避免搞亂我們的簡單模型。

然後你發現那些不滿意的人，瞧，你有人優化高速緩存行訪問。所以在理論上它可能是O（1），對於小數組（適合第一級緩存），它的行爲類似於O（1），但實際上通常不會。

一個極端的實際案例是一個不適合主存的數組;現在數組訪問可能會導致從磁盤進行分頁。

即使在這種情況下，我們也不在乎。谷歌本質上是一個巨大的緩存。我們傾向於將Google搜索視爲O（1）。

Answer 2

他談論的是計算模型，特別是基於詞的RAM機

一個內存的機器是非常相似的東西，真實的計算機形式化：我們的計算機內存的大陣列模式我們可以在O（1）時間內讀取/寫入任何字詞

但是我們還有一些重要的定義：一個單詞應該多大？

我們需要一個字大小w≥Ω（log n）至少能夠解決我們輸入的n個部分。 爲此，根據字的RAM通常假設O（log n）的

的字長但有你的機器字長取決於輸入的尺寸出現奇怪和不切實際

如果我們保持字長固定？那麼即使下面的指針需要Ω（log n）的時間僅需讀取整個指針

我們需要Ω（log n）的字來存儲指針和Ω（log n）的時間，如果訪問輸入元素

Answer 3

一語言支持稀疏數組，對數組的訪問必須經過一個目錄，並且樹形結構的目錄將具有非線性訪問時間。還是你的意思是現實條件？ ;-)

Answer 4

桔子可以變紅嗎？

是的，他們可以是紅色，由於多種原因 -

• 你點顏色他們的紅色。
• 你種植了一種轉基因品種。
• 你在火星這個紅色的星球上生長，每個東西都應該看起來是紅色的。
• 一些實際的（因爲今天的技術）的（理論）名單和不切實際（小說/或未來現實）的推移...

的一點是，我認爲你是在問這個問題，是真的約兩個正交的概念。即 -

Big O Notation - 「- 在數學中，大O符號描述了當參數趨向於特定值或無窮大時函數的限制行爲，通常用簡單的函數表示。「

VS

實用性（硬件和軟件），一個優秀的軟件工程師應該知道的，而架構/設計他們的應用程序和編寫代碼。

換句話說，而概念大O符號可以稱爲學術，但它是最合適分類算法複雜性（時間/空間）的方式..這就是它結束的地方。沒有必要以正交關注混濁水域

要清楚，我是而不是表示不應該意識到引擎蓋下的實現細節和事情的工作，這會影響您編寫的軟件的性能..但沒有任何混合點兩個在一起。例如，是否有意義地說 -

數組沒有固定的時間訪問（使用索引），因爲 -

• 大數組不會在CPU緩存適合，因此招致高速緩存未命中的成本高。
• 在內存壓力下的系統上，大小的陣列已從物理內存換出到硬盤，不僅受到緩存未命中的影響，而且還會出現硬頁面故障。
• 在CPU負載過重的系統上，讀取所需數組的線程可以被搶佔，並且可能沒有機會執行幾秒鐘。
• 在一個假想的操作系統上，它不僅支持磁盤，而且在另一個角落的另一臺計算機上支持更多的內存，這將會讓數組訪問變得難以想象的緩慢。

就像我的蘋果和橙色的例子，當你閱讀我越來越荒謬的例子時，希望我想說明的一點是清楚的。

結論 - 任何一天，我會回答這個問題：「做數組有固定的時間O（1）訪問（使用索引）」，爲是..沒有任何疑問或如果和但是，他們做。

---

編輯：

換一種說法 - 如果O（1）是沒有答案..然後也不是O（log n）的，或爲O（n log n）的或O （n^2）或O（n^3）.....並且當然不是42.