Использовать содержимое таблицы в качестве ключа

Question

Существует ли простой способ создать словарную коллекцию, например

1. Таблицы могут использоваться в качестве ключей
2. Таблицы с одинаковым содержимым считаются эквивалентными (вместосравнение указателей по умолчанию)

например, после

t = createCustomTable()
k1 = {'a','b','c'}
k2 = {'a','b','c'}
t[k1] = true

t[k2] должно быть оценено как true.
Также сам t должен использоваться в качестве ключа в

Есть ли способ сделать это без

1. Повторная реализация хеш-таблиц
2. Преобразование k1 и k2 в строки?(это то, чем я сейчас занимаюсь.)

Answer 1

Сериализация двух таблиц в строки - это решение, которое Роберто Иерусалимский (главный архитектор Lua) рекомендует для индексации по содержимому в Программирование в Lua 2nd Edition .

Если все ваши таблицы ключей являются массивами строк (без встроенных нулей), это можно сделать быстро с помощью table.concat(t,'\0'). (Очевидно, что ваша таблица должна быть отсортированной , если вы хотите независимую от индекса идентичность.)

Answer 2

Если таблицы, которые будут использоваться в качестве ключей, являются фиксированными, а их содержимое не изменяется, вы можете создать дайджест SHA2 по требованию в метаметоде newindex для t и использовать дайджест в качестве реального ключа. Дайджест будет кэширован в другой таблице, проиндексированной реальными таблицами.

Answer 3

Вы можете реализовать и установить метод __eq в метатаблице двух таблиц.

k1 = {'a','b','c'}
k2 = {'a','b','c'}
mt1={__eq=function(a,b)
   for k,v in pairs(a) do
      if b[k]~=v then return false end
   end
   for k,v in pairs(b) do
      if a[k]~=v then return false end
   end
   return true
end
}
setmetatable(k1,mt1)
setmetatable(k2,mt1)

assert(k1==k2,"Table comparison failed")

function newDict(orig)
    if orig then
        return orig
    else
        local mt2={}
        local lookup ={} -- lookup table as upvalue to the metamethods
        mt2.__newindex = function(t,k,v) -- Registering a new table
            if type(k)~="table" then return end
            if v then   -- v ~= false
                local found
                for idx,val in pairs(lookup) do
                    if k==val then
                        found=1
                        break
                    end -- If already seen, skip.
                end
                if not found then
                    lookup[#lookup+1]=k -- not seen before, add
                end 
            else -- v == false or nil
                local to_erase
                for idx,val in pairs(lookup) do -- Assume there is only one match in the dict.
                    if k==val then
                        lookup[k]=nil
                        break
                    end --don't continue after this, next will be confused.
                end
            end         
        end

        mt2.__index = function(t,k) -- looking up a table
            for idx,val in pairs(lookup) do
                if k==val then 
                    return true
                end
            end
            return false
        end
        return setmetatable({},mt2)
    end
end

t1 = newDict()
t2 = newDict()

k1={1,2,3}
k2={"a"}
k3={"z","d","f"}

k1b={1,2,3}
k2b={"a"}
k3b={"z","d","f"}

setmetatable(k1,mt1)
setmetatable(k2,mt1)
setmetatable(k3,mt1)

setmetatable(k1b,mt1)
setmetatable(k2b,mt1)
setmetatable(k3b,mt1)

-- Test multiple entries in 1 dict
t1[k1]=true
t1[k2]=true
assert(t1[k1b],"t1[k1b] did not return true")
assert(t1[k2b],"t1[k2b] did not return true")
-- Test confusion between 2 dicts
t2[k3]=true
assert(not t1[k3b],"t1[k3b] did return true")
assert(not t2[k1b],"t2[k1b] did return true")

Сравнение может быть реализовано быстрее, потому что теперь общие записи проверяются дважды, но вы получаете точку.

Я не могу комментировать производительность, так как она использует метатабельный поиск довольно интенсивно и нуждается в просмотре всех таблиц при каждом сравнении или назначении, но, поскольку вы не хотите хешировать таблицы или преобразовывать их в строки (ака их сериализуют) это единственный способ.Если бы я был тобой, я бы серьезно подумал о том, чтобы сверяться с сериализацией таблиц, а не с описанным выше подходом.

Answer 4

Если вы можете выдержать зависимость от библиотеки, вы можете использовать что-то вроде Penlight , который предлагает наборы http://penlight.luaforge.net/#T10.

Answer 5

В этом (раздел «Ключи являются ссылками») говорится, что ключи являются ссылками на объекты, поэтому использование идентичной таблицы, как в вашем примере, не будет работать.Я думаю, что то, как вы сейчас это делаете, может быть лучшим, но я могу ошибаться.