以O（1）時間可改進的數組訪問？

我一直在閱讀一本爲類指定的書，它提到數組訪問需要O（1）次。我意識到這是非常快的（也許儘可能快），但是如果你有一個循環必須引用這個幾次，是否有任何優勢來分配一個臨時變量來在數組中查找值？或者使用臨時變量仍然是O（1）以供使用？以O（1）時間可改進的數組訪問？

我假設這個問題是獨立於語言的。我也意識到，即使答案是肯定的，優勢很小，我只是好奇。

來源

2013-02-07 asimes

如果我理解號，你問如果

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符號和指令級優化。

編輯

我剛編譯的示例程序與兩個功能，含有上述兩種樣品，並在-O2 GCC 4.7.2中生成的完全相同機器代碼;字節的字節。

來源

2013-02-07 06:38:55

即使使用＃2，一個內存讀取和兩個內存讀取之間仍然存在差異（OK，而不是L1中的緩存） –

是的，這就是我的意思（代碼）。我不確定這是否是字面上的操作，書中稱它爲O（1），所以我寫了同樣的東西。看起來答案沒有改善，它在低水平上保持不變。 – asimes

@JanDvorak啊，你說得對。在我的回答中，我必須轉換思路。刪除它。 –

您可以執行比O（1）時間更好的唯一方法是不必首先執行什麼。那將是O（0）時間。

或者用更少的話：

來源

2013-02-07 06:38:50 placeybordeaux

請注意，O（1）並不意味着「瞬間」。它只是意味着「至多有一些不變」。這意味着1和10都是O（1），儘管其中的第二個比宇宙中的原子的數量大。

如果您多次訪問相同的數組元素，則每次訪問需要O（1）次。將該數組元素存儲在局部變量中也會給出O（1）查找時間，但常量可能不相同。它可能比其他選擇一個選項更好，但你真的需要確定程序的配置文件。

實際上，這種微型優化不可能對程序時間產生可測量的影響，除非您運行的代碼佔程序運行時間的很大一部分。我會很震驚地發現一個例子，這個變化會在任何真實的代碼中產生顯着的影響。

現代體系結構可能會使這種變化更快一些，但並不是如此。如果多次訪問相同的數組元素，處理器可能會將該數組的一部分保存在緩存中，使查找速度非常快。此外，優化編譯器可能已經將非本地副本代碼轉換爲本地副本代碼。

希望這會有所幫助！

來源

2013-02-07 06:39:54 templatetypedef

謝謝，我寫了O（1），因爲這本書確實存在，並且我不願意寫1個操作，因爲我不知道這是否正確。我知道它永遠不會產生重大影響，我最想知道它是否有所作爲。「 – asimes

現代CPU硬件（例如高速緩存行）中已經包含了一些內容，它們可以執行類似於您所描述的內容，但更好的方式是臨時變量無法執行的操作。甚至比這更好，不需要源修改。

來源

2013-02-07 06:44:50 ldav1s

」以臨時變量無法做到的方式更好。「 - 臨時變量不能做什麼？ –

您通常不能依賴存儲器的臨時變量。臨時變量是否在內存中創建？在註冊表中？在優化的情況下，根本？ – ldav1s

編號數組訪問不是一些由閃閃發光和愛所構成的神奇的零佔用空間的東西。從C中的數組索引中確定地址的算法可見here。陣列上的維數越多，訪問的速度越慢，因爲需要額外的操作（主要是成本方面的mul和條件）才能達到最終的一維內存地址。即使你的數組只有一個維度，你仍然必須計算基地址的偏移量，這是一個單一的add操作，因此O（1）。

來源

2014-12-29 13:08:52

以O（1）時間可改進的數組訪問？

回答

相關問題