关联数组查找成本

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.具有良好散列函数(两者都是给定的)的正确编写的散列表需要预期的恒定时间,尽管在极不可能的最坏情况下它可能需要线性时间.你的第二个函数使用它,第一个函数没有 - 它总是需要时间线性的表格大小.

对于用作数组(连续整数键)的表进行了优化,如Lua 5.0的实现中所述(您还可以在其中找到有关哈希表的一些详细信息).如果本文中的信息是准确的,并且我正确地解释了它,那么这个优化也应该由你的第二个表触发(在1..5使用的5个索引中有3个).因此,它很可能只在C数组中存储五个值,并对此数组进行保证 - 恒定时间索引.

无论哪种方式,你可以打赌你的房子,第二个是渐近更快.也就是说,随着元素数量接近无穷大,它将变得比线性扫描更快.在实践中,你不需要去任何接近无限的地方(我的直觉是几十个就足够了,可能更少)看到显着的差异.