루아 : 키가 테이블 (또는 객체) 인 테이블을 찾는 방법

Question

키가 다른 루아 테이블 인 루아 테이블을 저장하고 싶습니다. 이것이 가능하다는 것을 알고 있지만 테이블의 복사본을 사용하여 테이블에서 look ups를 할 수 있기를 원합니다.

t[key2] 

을하고 내가 key을 창출 할 수 있다는 사실을 알고 4.

얻을 : 내가 찾아 볼 수 있도록하려면 다음

t = {} 
key = { a = "a" } 
t[key] = 4 
key2 = { a = "a" } 

과 : 특히, 나는 할 수 있도록하려면 문자열에 넣고 t 테이블에 넣습니다. 또한 사용자 정의 해시 함수를 작성하거나 테이블을 중첩하여이 작업을 수행하는 방법에 대해 생각해 보았습니다. 이러한 유형의 기능을 사용할 수있는 가장 좋은 방법이 있습니까? 다른 옵션은 무엇입니까?

Answer 1

루아에서 별도로 생성 된 두 테이블은 "다르게"간주됩니다. 그러나 테이블을 한 번 만들면 원하는 모든 변수에 테이블을 할당 할 수 있으며, 테이블을 비교할 때 루아는 테이블이 동일하다는 것을 알려줍니다. 즉,

이렇게하면 간단하고 깨끗한 방법으로 원하는 것을 할 수 있습니다.어딘가에 key을 저장하면 4을 다시 검색 할 수 있습니다. 이것은 또한 매우 빠릅니다.

정말로을하고 싶지 않은 경우 ... 음, 방법이 있습니다. 그러나 그것은 비효율적이고 추악합니다.

첫 번째 부분은 두 개의 별도 테이블을 비교하는 함수를 만들고 있습니다. 2 개의 테이블이 「동등」인 경우는 true를 돌려 주어, 그렇지 않은 경우는 false를 돌려줍니다. 동급이라고 부르 자. 다음과 같이 작동해야합니다.

equivalent({a=1},{a=1})   -- true 
equivalent({a=1,b=2}, {a=1})  -- false 
equivalent({a={b=1}}, {a={b=2}}) -- false 

테이블 자체가 포함 된 테이블을 처리하려면이 함수가 순환 적이어야합니다. 테이블 중 하나가 다른 테이블을 "포함"하지만 더 많은 요소가 있으면 테이블을 속일 수 없습니다. 나는이 구현으로 나왔다. 아마도 더 좋은 것들이있을 것입니다.

local function equivalent(a,b) 
    if type(a) ~= 'table' then return a == b end 

    local counta, countb = 0, 0 

    for k,va in pairs(a) do 
    if not equivalent(va, b[k]) then return false end 
    counta = counta + 1 
    end 

    for _,_ in pairs(b) do countb = countb + 1 end 

    return counta == countb 
end 

여기서는이 기능에 대해 설명하지 않겠습니다. 나는 그것이 무엇을하는지 분명히 밝혀지기를 바랍니다.

퍼즐의 다른 부분은 t 키를 비교할 때 equivalent 기능을 사용합니다. 이 작업은주의 깊은 메타 테이블 조작과 추가 "저장소"테이블을 사용하여 수행 할 수 있습니다.

우리는 기본적으로 t을 사기범으로 변환합니다. 우리 코드가 키 아래에 값을 저장하라고 지시하면 코드 자체에 저장하지 않습니다. 대신 여분의 테이블에이를 제공합니다 (우리는 store이라고 부를 것입니다). 코드에서 t에 값을 묻는 경우 store에서 코드를 검색하지만 equivalent 함수를 사용하여 값을 찾습니다.

local function equivalent(a,b) 
... -- same code as before 
end 

local store = {} -- this is the table that stores the values 

t = setmetatable({}, { 
    __newindex = store, 
    __index = function(tbl, key) 
    for k,v in pairs(store) do 
     if equivalent(k,key) then return v end 
    end 
    end 
}) 

사용 예 :

이

코드입니다, 나는 언어 처리에 대해 많이 모르는

t[{a = 1}] = 4 

print(t[{a = 1}]) -- 4 
print(t[{a = 1, b = 2}]) -- nil 

Answer 2

나는 이것을 할 수 있을지 확신하지 못합니다. 메타 테이블을 사용하여 테이블에 대한 동등성을 정의 할 수 있지만 해시 함수를 정의 할 수있는 방법은 없으며 평등 만 정의하면 필요한 작업을 수행 할 수 없습니다. 분명히 평등을 정의한 다음 pairs()을 사용하여 테이블을 반복하고 키를 직접 비교할 수 있지만 O(1)을 O(n)으로 찾아야합니다.

Answer 3

루아에서는이 기능을 사용할 수 없습니다. 테이블을 키로 사용하는 경우 키는 테이블의 특정 "인스턴스"입니다. 동일한 내용의 다른 테이블을 만들더라도 인스턴스가 다르므로 다른 키입니다.

이와 같은 작업을 수행하려는 경우 해시 함수의 종류를 만들 수 있습니다. 해시 함수는 테이블을 키로 사용하여 (필요할 경우 재귀 적으로) 테이블을 탐색하고 테이블 내용의 문자열 표현을 구성합니다. 내용이 다르거 나 동일한 내용의 표가 같으면 사람이 읽을 수 있어야합니다. pairs()을 사용하여 테이블을 탐색하는 것 외에 을 임의의 순서로 반환하고 "동일한"테이블에 대해 동일한 문자열을 원하기 때문에 테이블에 키를 삽입하고 table.sort()을 사용하여 정렬해야합니다.

당신이 그런 캐릭터 라인을 구축 한 후에는 열쇠로 사용할 수 있습니다 : 제 생각에는

function hash(t) ... end 
t = {} 
key1 = { a = "a", b = "b" } 
t[hash(key1)] = 4 
key2 = { a = "a", b = "b" } 
print(t[hash(key2)]) -- should print "4" if the hash function works correctly 

는,이 모두가 색인의 간단한 작업이 너무 복잡

, 당신은 다시 생각 할 수 있습니다 테이블 사본을 사용하여 색인 생성을 원한다. 왜 그러한 기능을 원하십니까?

만 문구와 함께 작동해야하는 경우 업데이트, 나는 그들을 연결하는 등의 일반적인 해시 함수를 만드는 것보다 쉽다는 것을 생각한다. 문구 시퀀스가 ​​필요한 경우 테이블을 반복하고 키를 정렬 할 필요가 없으며 각 문구의 주요 정보 만 수집하면됩니다.

function pkey(...) 
    local n, args = select('#', ...), { ... } 
    for i=1,n do args[i] = args[i].value end -- extract your info here 
    return table.concat(args, ' ') -- space or other separator, such as ':'   
end 
tab[pkey(phrase1, phrase2, phrase3)] = "value" 

Answer 4

및 목표에 대해 당신이 당신의 프로그램에 도달하고 싶지만 이런 식으로 토큰을 수집하는 방법은 다음과 같습니다. 중첩 된 테이블 구조를 사용하는 경우 인덱스 테이블에 첫 번째 구문 토큰으로 인덱싱 된 테이블 만 저장 한 다음 각 하위 테이블에 두 번째 구 토큰으로 인덱싱 된 값이 포함됩니다. 그 숫자에 해당하는 숫자 값을 인덱싱합니다. 문구의 ce.

이

• 내가 바나나를 좋아한다 : 당신은 다음 두 구절이있는 경우
  은 아마는 exemple 더 명확 할 것이다.
• 나는 뜨거운 병아리를 좋아한다. 내가 전에 말했듯이, 당신은 하나의 탐색 단계 frenquencies를 계산, 당신은 색인 동시에 발행 수를 셀 수있는 방법으로

  index["I"] = { 
      ["like"] = { 
       ["banana"] = 1, 
       ["hot"] = { 
        ["chick"] = 1 
       } 
      }  
  } 
  

  있지만 :

귀하의 인덱스는 다음과 같은 구조를 가질 것 그것은 당신의 목표가 무엇인지에 달려 있으며, 그것은 당신의 색인을 통해 일어나는 것을 발견 할 수 있도록 당신을 다시 분할하는 것을 의미합니다.

Answer 5

kikito의 대답은 좋지만, 몇 가지 결함이있다 : 당신이 t[{a=1}] = true 두 번 수행 할 경우, store 한 번 값을 수정

(해시 테이블의 수명 동안 누출 메모리) 두 테이블을 포함

• 을 이미 저장했거나 작동하지 않거나 제거 할 수 없습니다. 이를 변경하려고 시도하면 검색에서 이전에 해당 키에 할당 한 값이 모두 반환됩니다.
• 액세스 성능은 O (n)입니다 (n은 저장된 항목 수이고 테이블에서 루아 값 검색은 O (1)이라고 가정). 제 점과 함께,이 해시 테이블의 성능은 사용

(또한 어떤 테이블이 순환 참조 경우 무한 루프가 발생할 것이다 kikito의 "등가"기능을 참고.)

귀하와 분해 할 테이블의 정보를 변경/제거 할 필요가 없다면 kikito의 답변으로 충분합니다. 그렇지 않으면, 메타 테이블은 __newindex 테이블이 아직없는 것을 확인합니다 있도록 변경해야 존재 : 당신이 제안했듯이

t = setmetatable({}, { 
    __newindex = function(tbl, key, value) 
     for k,v in pairs(store) do 
      if equivalent(k,key) then 
       tbl[k] = value 
       return 
      end 
     end 
     store[key] = value 
    end, 
    __index = function(tbl, key) 
     for k,v in pairs(store) do 
      if equivalent(k, key) then return v end 
     end 
    end 
}) 

는 완전히 다른 옵션은 사용자 정의 해시 함수를 작성하는 것입니다.

local function HashTable(Hash, Equals) 
    --Hash is an optional function that takes in any key and returns a key that lua can use (string or number). If you return false/nil, it will be assumed that you don't know how to hash that value. 
    -- If Hash is not provided, table-keys should have a GetHash function or a .Hash field 
    --Equals is an optional function that takes two keys and specify whether they are equal or not. This will be used when the same hash is returned from two keys. 
    -- If Equals is not provided, items should have a Equals function; items are in this case assumed to not be equal if they are different types. 
    local items = {} --Dict<hash, Dict<key, value>> 
    local function GetHash(item) 
     return Hash and Hash(item) or type(item) == "table" and (item.GetHash and item:GetHash() or item.Hash) or item 
    end 
    local function GetEquals(item1, item2) 
     if Equals then return Equals(item1, item2) end 
     local t1, t2 = type(item1), type(item2) 
     if t1 ~= t2 then return false end 
     if t1 == "table" and item1.Equals then 
      return item1:Equals(item2) 
     elseif t2 == "table" and item2.Equals then 
      return item2:Equals(item1) 
     end 
     return false 
    end 
    return setmetatable({}, { 
     __newindex = function(_, key, value) 
      local hash = GetHash(key) 
      local dict = items[hash] 
      if not dict then 
       if value ~= nil then --Only generate a table if it will be non-empty after assignment 
        items[hash] = {[key] = value} 
       end 
       return 
      end 
      for k, v in pairs(dict) do 
       if GetEquals(key, k) then --Found the entry; update it 
        dict[k] = value 
        if value == nil then --check to see if dict is empty 
         if next(dict) == nil then 
          items[hash] = nil 
         end 
        end 
        return 
       end 
      end 
      --This is a unique entry 
      dict[key] = value 
     end, 
     __index = function(_, key) 
      local hash = GetHash(key) 
      local dict = items[hash] 
      if not dict then return nil end 
      for k, v in pairs(dict) do 
       if GetEquals(key, k) then 
        return v 
       end 
      end 
     end 
    }) 
end 

사용 예 :

local h = HashTable(
    function(t) return t.a or 0 end, --Hash 
    function(t1, t2) return t1.a == t2.a end) --Equals 
h[{a=1}] = 1 
print(h[{a=1}]) -- 1 
h[{a=1}] = 2 
print(h[{a=1}]) -- 2 
print(h[{a=1,b=2}]) -- 2 because Hash/Equals only look at 'a' 

당연히, 당신은 더 나은 해시/함수 같음 싶어합니다 여기에 사용할 수있다 해시 테이블입니다.

키의 해시가 거의 충돌하지 않는 한이 클래스의 성능은 O (1)이어야합니다.

(참고 : 나는 kikito에 주석으로이 답변의 위쪽 절반을 넣어 가지고 싶지만, 그렇게 할이 시간에 명성이 없습니다.)