2

1セットの値をテーブルキーに配置し、テーブル値としてLuaテーブルをセットとして使用しています。

function addToSet(s,...)      for _,e in ipairs{...} do s[e]=1   end end
function removeFromSet(s,...) for _,e in ipairs{...} do s[e]=nil end end

local logics = {}
addToSet(logics,true,false,"maybe")

2 つのセットが等しいかどうかをテストするには、キーがまったく同じであることを確認する必要があります。これを行う効率的な方法は何ですか？

4

2 に答える 2

4

効率について質問されたので、代替の実装を提供します。予想される入力テーブルによっては、2 番目のループのルックアップを回避したい場合があります。テーブルが同じであると予想される場合はより効率的ですが、違いがある場合は効率が低下します。

function sameKeys(t1,t2)
  local count=0
  for k,_ in pairs(t1) do
    if t2[k]==nil then return false end
    count = count + 1
  end
  for _ in pairs(t2) do
    count = count - 1
  end
  return count == 0
end

別のバージョンでは、必要でない限りルックアップを回避します。これは、さらに別の一連のユースケースでより高速に実行される場合があります。

function sameKeys(t1,t2)
  local count=0
  for _ in pairs(t1) do count = count + 1 end
  for _ in pairs(t2) do count = count - 1 end
  if count ~= 0 then return false end
  for k,_ in pairs(t1) do if t2[k]==nil then return false end end
  return true
end

編集:さらに調査とテストを行った結果、Lua と LuaJIT を区別する必要があるという結論に達しました。Lua では、パフォーマンス特性は Lua のパーサーによって支配されるため、ソース コード トークンの数によって支配されます。Lua の場合、これは Phrogz のバージョンがより高速な代替手段である可能性が最も高いことを意味します。LuaJIT の場合、パーサーはもはや問題ではないため、状況は劇的に変化します。ほとんどの場合、最初に示したバージョンが改善されています。テーブルが非常に大きい場合は、おそらく 2 番目のバージョンが最適です。独自のベンチマークを実行し、環境でどのバージョンが最適かを確認することをお勧めします。

于 2013-02-15T06:27:02.170 に答える
3

両方のテーブルをループして、キーがもう一方のテーブルに値を持っていることを確認します。不一致を見つけたらすぐに失敗し、true両方を通過した場合は戻ります。サイズのセットの場合M、Nこれは O(M+N) の複雑さです。

function sameKeys(t1,t2)
  for k,_ in pairs(t1) do if t2[k]==nil then return false end end
  for k,_ in pairs(t2) do if t1[k]==nil then return false end end
  return true
end

実際に見られる:

local a,b,c,d = {},{},{},{}
addToSet(a,1,2,3)
addToSet(b,3,1,2,3,3,1)
addToSet(c,1,2)
addToSet(d,2,1)
print(sameKeys(a,b)) --> true
print(sameKeys(a,c)) --> false
print(sameKeys(d,c)) --> true

のテストは、テーブル エントリの値を設定し、キーをセットに存在させたい(可能性が低い) ケースを処理するt[k]==nilよりも優れていることに注意してください。not t[k]false

于 2013-02-15T06:12:50.357 に答える