Associative array search cost
Consider two search functions:
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
Which feature has a lower search cost? Or are they equal? How does Lua store associative arrays locally?
source to share
Basically all tables are hash tables, and your first table is just implicitly using integer keys 1..n
. A reasonably written hash table with decent hash functions (as given) takes an expected-constant time, although in the very unlikely worst case this could result in linear time. Your second function uses this, the first does not - it always requires a linear linear value for the table size.
There is an optimization for tables being used as arrays (sequential integer keys) as described in Lua 5.0 Implementation (where you will also find some details about the hash table). If the information in this article is accurate and I am interpreting it correctly, this optimization should be triggered by your second table (3 out of 5 indexes in 1..5
). So it is likely that it will just store five values in array C and make indexing that metric a guaranteed constant time.
Either way, you can put your home on that second asymptotically faster. That is, as the number of elements approaches infinity, it will be faster than a linear scan. In practice, you don't have to go anywhere near infinity (my gut feeling is that a few dozen will be sufficient, perhaps less) to see a significant difference.
source to share