Lua: come cercare in una tabella in cui le chiavi sono tabelle (o oggetti)

Question

Voglio memorizzare un tavolo lua in cui le chiavi sono altre tabelle lua. So che questo è possibile, ma voglio essere in grado di fare ricerche nella tabella usando copie di quelle tabelle. In particolare, voglio essere in grado di fare:

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

e poi voglio essere in grado di guardare in alto:

t[key2] 

e ottenere 4.

So che posso girare key in una stringa e metterlo nella tabella t. Ho anche pensato di scrivere una funzione di hash personalizzata o farlo nidificando le tabelle. C'è un modo migliore per me per ottenere questo tipo di funzionalità? Quali altre opzioni ho?

Answer 1

In Lua, due tabelle create separatamente sono considerati "diversi". Ma se crei una tabella una volta, puoi assegnarla a qualsiasi variabile che vuoi, e quando le paragoni, Lua ti dirà che sono uguali. In altre parole:

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

Quindi, questo è il modo semplice e pulito di fare quello che vuoi.Memorizza key da qualche parte, in modo da poter recuperare il 4 indietro usandolo. Anche questo è molto veloce.

Se si in realtà non voglio farlo ... beh, c'è un modo. Ma è piuttosto inefficiente e brutto.

La prima parte sta creando una funzione che confronta due tabelle separate. Dovrebbe restituire true se due tabelle sono "equivalenti" e false se non lo sono. Chiamiamolo equivalente. Dovrebbe funzionare in questo modo:

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

La funzione deve essere ricorsiva, per gestire tabelle che contengono tavoli stessi. Inoltre, non deve essere ingannato se una delle tabelle "contiene" l'altra, ma ha più elementi. Sono uscito con questa implementazione; probabilmente ce ne sono di migliori là fuori.

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 

Non ho intenzione di spiegare questa funzione qui. Spero sia abbastanza chiaro cosa faccia.

L'altra parte del puzzle consiste nel rendere t utilizzare la funzione equivalent quando si confrontano le chiavi. Questo può essere fatto con un'attenta manipolazione misurabile, e con una tabella di "memorizzazione" extra.

Fondamentalmente trasformiamo t in un impostore. Quando il nostro codice dice di memorizzare un valore sotto una chiave, non lo salva da solo; invece lo dà al tavolo extra (lo chiameremo così store). Quando il codice richiede t per un valore, lo cerca in store, ma utilizzando la funzione equivalent per ottenerlo.

Questo è il codice: esempio

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

Usage:

t[{a = 1}] = 4 

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

Answer 2

Non sono sicuro che tu possa farlo. Puoi definire l'uguaglianza per le tabelle usando il metatable, ma non c'è modo di definire una funzione di hash, e dubito che definire l'uguaglianza da sola farà ciò di cui hai bisogno. Ovviamente è possibile definire l'uguaglianza, quindi iterare sulla tabella utilizzando pairs() e confrontare i tasti manualmente, ma ciò trasformerà la ricerca da O(1) in O(n).

Answer 3

Questo non è possibile in Lua. Se si usano le tabelle come chiavi, la chiave è quella specifica "istanza" della tabella. Anche se si crea una tabella diversa con gli stessi contenuti, l'istanza è diversa, quindi è una chiave diversa.

Se si vuole fare qualcosa di simile, è possibile creare una sorta di funzione di hash, che attraversa la tavola per servire come chiave (forse anche in modo ricorsivo, se necessario) e costruire una rappresentazione di stringa del contenuto della tabella. Non ha bisogno di essere leggibile dall'uomo, purché sia ​​diverso per contenuti diversi e uguale per le tabelle con lo stesso contenuto. Oltre all'utilizzo di pairs() per attraversare la tabella, è necessario inserire le chiavi in ​​una tabella e ordinarle utilizzando table.sort(), perché pairs() le restituisce in un ordine arbitrario e si desidera la stessa stringa per le tabelle "uguali".

Una volta che avete costruito tale stringa, è possibile utilizzarlo come chiave:

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 

A mio parere, tutto questo è troppo complicato per il semplice compito di indicizzazione, e si consiglia di ripensare il tuo desiderio di indicizzazione utilizzando copie di tabelle. Perché vorresti una tale funzionalità?

Aggiornamento

Se avete solo bisogno di lavorare con frasi, penso che li concatenando è più facile che la creazione di tale funzione hash generica. Se ne hai bisogno per sequenze di frasi, non dovrai effettivamente scorrere le tabelle e ordinare le chiavi, ma solo raccogliere le informazioni principali da ogni frase. Si avrebbe ancora bisogno di utilizzare una funzione di supporto, che può creare una chiave adatta per voi:

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

Non so molto di elaborazione del linguaggio, e circa la meta che si vuole raggiungere con il vostro programma, ma per quanto riguarda la raccolta di token in questo modo: utilizzare una struttura di tabella nidificata tale ha la tabella di indice memorizza solo le tabelle indicizzate dal token di prima frase, quindi ogni sottotabella contiene il valore indicizzato dal token di seconda frase ... ecc ... fino a raggiungere una frase finale token indicizzerà un valore numerico corrispondente a quello che si verifica ce della frase.

forse sarà più chiaro con un exemple, se avete la due seguente frase:

• mi piace banana.
• Mi piace il pulcino caldo.

Il tuo indice avrebbe la seguente struttura:

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

In questo modo si può contare frenquencies con un solo passo attraversamento, e contare le occorrenze allo stesso tempo che l'indicizzazione, ma come ho detto prima, dipende da qual è il tuo obiettivo e implicherà una nuova suddivisione della frase in modo da trovare le occorrenze attraverso il tuo indice.risposta

Answer 5

di Kikito è buono, ma ha alcuni difetti:

• Se si esegue t[{a=1}] = true due volte, store conterrà due tabelle (la memoria che perde per tutta la durata della tabella hash)
• Modifica del valore di una volta hai già memorizzato che non funziona, né puoi rimuoverlo. Il tentativo di cambiarlo comporterà il recupero di tutti i valori che hai assegnato a quella chiave in passato.
• La performance di accesso è O (n) (n è il numero di voci memorizzate e presuppone che il recupero del valore di lua da una tabella sia O (1)); combinato con il primo punto, le prestazioni di questa tabella hash si degradano con l'uso

(noti anche funzione "equivalente" che di Kikito causerà un ciclo infinito se qualsiasi tabella contiene un riferimento circolare.)

Se non è mai necessario cambiare/rimuovere alcuna informazione nella tabella, quindi la risposta di kikito sarà sufficiente così com'è. In caso contrario, il metatabella deve essere cambiato in modo che il __newindex fa in modo che la tabella non esiste già:

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

Come hai suggerito, un'opzione completamente diverso è quello di scrivere una funzione di hashing personalizzata. Ecco un HashTable che può fare uso di tale:

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 

Esempio di utilizzo:

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' 

Naturalmente, si vorrà ottenere una migliore Hash/Equals funzioni.

Fintanto che gli hash delle tue chiavi si scontrano raramente, questa prestazione di questa classe deve essere O (1).

(Nota: avrei messo la metà superiore di questa risposta come un commento alla Kikito, ma non ho la reputazione in questo momento per farlo.)