是否有一種情況下array_search比連續array_flip和直接查找更快？

想象一下，您要搜索一個包含N個元素的數組，並對數組值執行Y搜索以查找相應的鍵;您可以執行Y array_search's或做一個array_flip和Y直接查找。爲什麼第一種方法比第二種方法慢？有沒有第一種方法比第二種方法快的情況？你可以假設鍵和值是唯一的是否有一種情況下array_search比連續array_flip和直接查找更快？

來源

2013-05-31 EnJayz

這是一個有趣的問題。你有任何性能測試證明這一點？另外，你在做這個檢查時是否使用了嚴格的選項？ –

@Daryl Gill你爲什麼編輯我的問題？實際上，我的意思是N查找和N次搜索，現在如果將其編輯回原始狀態，所有這些討論都將失效。 – EnJayz

我只是想說一句：'你可以假定鍵和值是唯一的'：這非常重要：如果值不是唯一的，那麼當執行'array_flip'時，由於各種值會丟失一些項目將最終結束在同一個關鍵中，後者會覆蓋前者。 –

數組鍵被散列，所以查找它們只需要調用散列函數並將索引編入散列表。所以array_flip()是O（N），查找陣列鍵是O（1），所以Y搜索是O（Y）+ O（N）。

數組值不被散列，因此搜索它們需要線性搜索。這是O（N），所以Y搜索是O（N * Y）。

假設要搜索的值在數組中均勻分佈，則線性搜索的平均情況必須比較N/2個元素。所以array_flip()應該需要大約2 array_search()調用的時間，因爲它必須檢查N個元素。

創建哈希表時會有額外的開銷。但是，PHP使用寫時複製，所以它不需要在array_flip()期間複製密鑰或值，所以它不是太糟糕。對於少數查找，第一種方法可能會更快。你必須以此爲基準找到盈虧平衡點。

來源

2013-05-31 00:14:17 Barmar

我從來沒有*完全理解爲什麼查找數組鍵是恆定時間，但查找數組值是線性的（假設兩者都是可哈希）？ –

@Asad因爲這些值沒有被散列。您需要另外一個哈希結構映射值來定位值。 – Corbin

更新我的回答來解釋這一點。 – Barmar

是否有一種情況下array_search比連續array_flip和直接查找更快？

回答

相關問題