关联数组查找成本

2013-2-13 13:59:45
收藏：0
阅读：188
评论：2

考虑两个查找函数：

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内部如何存储关联数组？

点赞
用户752976
用户752976

第二个肯定更快。Lua使用基于哈希的表实现，这意味着在大多数情况下直接读取的复杂度将是次线性或甚至O(1)。

第一个是Ω(n)。

2013-02-13 14:03:45
用户88888888
用户88888888

实质上，_所有_表都是哈希表，在您的第一个表中，隐式使用整数键1..n。一个良好编写的哈希表和良好的哈希函数（两者都是已知的）需要平均常量时间，但在_非常不可能_的最坏情况下，它可能需要线性时间。您的第二个函数使用了这一点，而第一个函数没有 - 它总是需要与表大小成比例的时间。

在Lua 5.0的实现 中，有一个用于表格作为数组（连续整数键）的优化（在其中还有关于哈希表的一些细节）。如果这篇论文中的信息是准确的，并且我正确地理解了它，这个优化也应该被你的第二个表触发（在1..5中使用了5个中的3个索引）。因此，它很可能只会在C数组中存储五个值，并对此数组进行保证常数时间的索引。

无论哪种方式，第二种方法在渐进性上都更快。也就是说，当元素数量趋近于无穷大时，它将比线性扫描更快。在实践中，您不需要接近无限（我的直觉是几十个就足够了，可能更少）就可以看到显着的差异。

2013-02-13 14:04:22

作者:

用户615405

用户615405
推荐文章