tableau Associatif recherche coût

Question

deux fonctions Tenir compte lookup:

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 

Quelle fonction a le coût de recherche plus faible? Ou sont-ils égaux? Comment Lua stocke-t-elle les baies associatives en interne?

Answer 1

Par essence, toutes les tables sont des tables de hachage et votre première table utilise implicitement les touches entières 1..n. Une table de hachage décemment écrite avec des fonctions de hachage décentes (les deux un donné) prend le temps attendu-constant, bien que dans le pire des cas, il peut prendre le temps linéaire. Votre deuxième fonction utilise cela, la première ne le fait pas - cela prend toujours du temps linéaire dans la taille de la table.

Il existe une optimisation pour les tables utilisées en tant que tableaux (clés entières consécutives) comme décrit dans The Implementation of Lua 5.0 (où vous trouverez également quelques détails sur la table de hachage). Si les informations contenues dans cet article sont exactes et que je les interprète correctement, cette optimisation doit être déclenchée par votre deuxième table (3 des 5 indices utilisés dans 1..5). Il est donc probable qu'il va simplement stocker cinq valeurs dans un tableau C et faire une indexation à temps constant garanti de ce tableau. Dans tous les cas, vous pouvez parier que le second est asymptotiquement plus rapide. C'est-à-dire que lorsque le nombre d'éléments s'approche de l'infini, il deviendra plus rapide que le balayage linéaire. En pratique, vous n'avez pas besoin d'aller n'importe où près de l'infini (mon instinct est que quelques douzaines suffiront, peut-être moins) pour voir une différence significative.

Answer 2

La seconde est certainement plus rapide. Lua utilise l'implémentation des tables basée sur le hachage, ce qui signifie que les lectures directes seront dans la plupart des cas sous-lignées ou même O(1).

Le premier est Ω(n).