algorithm - 連想配列ルックアップ コスト

Question

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 はどのように連想配列を内部に格納しますか?

Answer 1

2番目は確かに高速です。Lua はテーブルのハッシュベースの実装を使用します。つまり、ほとんどの場合、直接読み取りはサブリニアまたはO(1).

最初のものはΩ(n)です。