algorithm - 关联数组查找成本

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 数组中，并对该数组进行保证恒定时间的索引。

无论哪种方式，您可以打赌第二个渐近更快。也就是说，随着元素数量趋近于无穷大，它会变得比线性扫描更快。在实践中，您无需接近无穷大(我的直觉是几十个就足够了，可能更少)就能看到显着差异。