關聯數組查找成本

Question

考慮兩個查找函數：

simple={1,3,5} 

function isX(id) 
for _,v in ipairs(simple) do 
    if v==id then return true end 
end 
return false 
end 


assoc={[1]=true,[3]=true,[5]=true} 

function isX2(id) 
return assoc[id] or false 
end 

哪個函數具有較低成本的查找？還是他們平等？ Lua如何在內部存儲關聯數組？

Answer 1

從本質上講，全部表是散列表，並且您的第一個表只是隱式使用整數鍵1..n。一個體面散列函數（一個給定的）的體面散列表需要預期的恆定時間，儘管在最不可能的情況下它可能需要線性時間。你的第二個功能就是利用這個功能，第一個功能不會 - 它總是需要時間線性表的大小。

如The Implementation of Lua 5.0（其中您還可以找到關於散列表的一些細節）中所述，對用作數組的表（連續整數鍵）進行優化。如果本文中的信息是準確的，並且我正確解釋，則此優化也應由第二個表格觸發（使用1..5中的5個索引中的3個）。所以它很可能只是將五個值存儲在一個C數組中，並對該數組進行有保證的常量時間索引。

無論哪種方式，你可以打賭你的房子，第二個是漸近快。也就是說，隨着元素數量接近無窮大，它將變得比線性掃描更快。在實踐中，你不需要去任何接近無限的地方（我的直覺是幾十個就足夠了，可能更少），看到一個顯着的差異。

Answer 2

第二個肯定比較快。 Lua使用基於散列的表格實現，這意味着在大多數情況下直接讀取將是次線性的，甚至是O(1)。第一個是Ω(n)。