Lua: Jak sprawdzić w tabeli, gdzie klucze są tabelami (lub obiektami)

Question

Chcę przechowywać tabelę lua, gdzie klucze są inne tabele lua. Wiem, że jest to możliwe, ALE chcę mieć możliwość sprawdzenia w tabeli przy użyciu kopii tych tabel. W szczególności chcę, aby być w stanie zrobić:

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

a następnie chcę, aby móc spojrzeć w górę:

t[key2] 

i dostać 4.

wiem, że mogę włączyć key w łańcuch i umieścić go w tabeli t. Myślałem także o pisaniu niestandardowej funkcji skrótu lub wykonywaniu tego przez zagnieżdżanie tabel. Czy istnieje najlepszy sposób na uzyskanie tego typu funkcji? Jakie mam inne opcje?

Answer 1

w Lua, dwa stoły tworzone osobno są uważane za „inny”. Ale jeśli utworzysz tabelę raz, możesz przypisać ją do dowolnych zmiennych, a kiedy porównasz je, Lua powie Ci, że są one równe. Innymi słowy:

t = {} 
key = { a = "a" } 
t[key] = 4 
key2 = key 
... 
t[key2] -- returns 4 

Tak, to jest proste, czyste sposób robienia tego, co chcesz.Przechowuj gdzieś numer key, aby odzyskać numer 4, korzystając z niego. Jest to również bardzo szybkie.

Jeśli naprawdę nie chce zrobić ... dobrze, jest na to sposób. Ale jest to rodzaj nieefektywnego i brzydkiego.

Pierwsza część polega na wykonaniu funkcji porównującej dwie oddzielne tabele. Zwraca wartość true, jeśli dwie tabele są "równoważne", a fałsz, jeśli nie są. Nazwijmy to równoważnym. Powinno to działać tak:

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

Funkcja musi być rekurencyjne, do obsługi tabel, które zawierają tabele siebie. Nie należy też oszukiwać, jeśli jedna z tabel "zawiera" drugą, ale ma więcej elementów. Wyszedłem z tą implementacją; prawdopodobnie są tam lepsze.

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 

Nie zamierzam tu wyjaśniać tej funkcji. Mam nadzieję, że jest wystarczająco jasne, co robi.

Druga część układanki polega na wykonaniu funkcji t przy użyciu funkcji equivalent podczas porównywania klawiszy. Można to zrobić poprzez ostrożną manipulację i dodatkową tabelę "przechowywania".

W zasadzie przekształcamy t w oszusta. Kiedy nasz kod nakazuje mu zapisanie wartości pod kluczem, nie zapisuje go w sobie; zamiast tego podaje ją do dodatkowego stołu (będziemy to nazywać store). Gdy kod prosi o podanie wartości t, wyszukuje ją w store, ale używa funkcji equivalent, aby ją uzyskać.

Jest to kod: przykład

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 
}) 

Zastosowanie:

t[{a = 1}] = 4 

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

Answer 2

Nie jestem pewien, czy możesz to zrobić. Możesz zdefiniować równość tabel za pomocą metatable, ale nie ma sposobu, aby zdefiniować funkcję mieszającą, i wątpię, że samo zdefiniowanie równości zrobi to, czego potrzebujesz. Można oczywiście zdefiniować równość, a następnie iterować po stole przy użyciu pairs() i porównywać klucze samodzielnie, ale to zmieni to, co powinno być O(1) wyszukiwanie w O(n).

Answer 3

To nie jest możliwe w Lua. Jeśli używasz tabel jako kluczy, kluczem jest ta konkretna "instancja" tabeli. Nawet jeśli tworzysz inną tabelę z tą samą zawartością, instancja jest inna, dlatego jest to inny klucz.

Jeśli chcesz zrobić coś takiego, możesz utworzyć rodzaj funkcji mieszającej, która przemierza tabelę, aby służyć jako klucz (może nawet rekursywnie, jeśli to konieczne) i skonstruować ciąg znaków reprezentujący zawartość tabeli. Nie musi być czytelny dla ludzi, o ile jest inny dla różnych treści i dla tabel o tej samej treści. Oprócz korzystania pairs() przechodzić do stołu, będzie trzeba także włożyć klucze do tabeli i sortować je korzystając table.sort(), ponieważ pairs() zwraca je w dowolnej kolejności, a chcesz ten sam ciąg na „równe” tabel.

Po skonstruowali taki ciąg, można użyć go jako klucza:

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 

Moim zdaniem, to wszystko jest zbyt skomplikowane dla prostego zadania indeksowania, a może chcesz do ponownego przemyślenia Twoje życzenie indeksowania przy użyciu kopii tabel. Dlaczego miałbyś chcieć takiej funkcjonalności?

Aktualizacja

Jeśli tylko trzeba pracować z wyrażeń, myślę, że ich złączenie jest łatwiejsze niż tworzenie takiego rodzajowe funkcji skrótu. Jeśli potrzebujesz tego do sekwencji fraz, nie będziesz musiał dokonywać iteracji po tabelach i sortowania kluczy, po prostu zbieraj główne informacje z każdej frazy. Nadal będzie trzeba użyć funkcji pomocnika, który może stworzyć odpowiedni klucz dla Ciebie:

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

nie wiem wiele na temat przetwarzania języka oraz o celu chcesz dotrzeć ze swoim programem, ale a co ze zbieraniem tokena w ten sposób: użyj zagnieżdżonej struktury tabeli, która ma tabele tabeli indeksów przechowujące tylko tabele indeksowane przez token pierwszej frazy, a następnie każda podtabela zawiera wartość zindeksowaną przez token drugiej frazy ... etc ... aż dojdziesz do końcowego tokena fraza , zindeksuje wartość liczbową odpowiadającą onemu occuren ce zdania.

Może to będzie bardziej jasne z exemple, jeśli masz dwa następujące zdanie:

• lubię banana.
• Lubię gorącą laskę.

indeks będzie miał następującą strukturę:

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

W ten sposób można liczyć frenquencies się od jednego kroku traversal, i policzyć wystąpień w tym samym czasie można indeksowanie, ale jak powiedziałem wcześniej, zależy to od tego, jaki jest Twój cel, a to oznacza, że ​​musisz ponownie podzielić zdanie, aby znaleźć zdarzenia za pośrednictwem indeksu.Odpowiedź

Answer 5

kikito jest dobry, ale ma kilka wad:

• Jeśli wykonać t[{a=1}] = true dwa razy, store będzie zawierać dwie tabele (pamięć wycieka przez cały okres tabeli hash)
• Zmiana wartości raz już zapisałeś to nie działa, ani nie możesz go usunąć. Próba jej zmiany spowoduje, że odzyskiwanie potwierdzi zwrot każdej wartości przypisanej do tego klucza w przeszłości.
• Wydajność dostępu to O (n) (n oznacza liczbę zapisanych wpisów i przy założeniu, że wartość lua pobierania z tabeli to O (1)); w połączeniu z pierwszym punktem, wydajność tej tabeli mieszania będzie degradować z zastosowaniem

(również pamiętać, funkcja, która kikito za „równoważne” spowoduje nieskończoną pętlę jeśli każdy stół ma okrągły odniesienie.)

jeśli nigdy nie trzeba zmieniać/usuwać żadnych informacji w tabeli, wtedy odpowiedź Kikito wystarczy. W przeciwnym razie, metatable musi zostać zmieniony tak, że __newindex zapewnia, że ​​tabela nie istnieje:

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 
}) 

Jak już sugeruje, zupełnie inna opcja jest napisać funkcję zwyczaj mieszającego. Oto HashTable, które można wykorzystać, że:

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 

Przykład użycia:

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' 

Oczywiście, będziemy chcieli, aby uzyskać lepsze Hash/Równa funkcje.

Dopóki skróty Twoich kluczy rzadko się zderzają, wydajność tej klasy powinna wynosić O (1).

(Uwaga: bym umieścić górną połowę tej odpowiedzi jako komentarz do kikito, ale nie mam reputację w tej chwili, aby to zrobić.)