Lua: Как посмотреть в таблице, где ключи - это таблицы (или объекты)

Question

Я хочу хранить таблицу lua, где ключами являются другие таблицы lua. Я знаю, что это возможно, но я хочу иметь возможность искать в таблице, используя копии этих таблиц. В частности, я хочу иметь возможность сделать:

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

и тогда я хочу иметь возможность посмотреть:

t[key2]

и получить 4.

Я знаю что могу превратить key в строку и положить его в таблицу t, Я также думал о написании пользовательской хеш-функции или выполнении этого путем вложения таблиц. Есть ли лучший способ для меня, чтобы получить этот тип функциональности? Какие еще варианты у меня есть?

Answer 1

В Lua две таблицы, созданные отдельно, считаются "разными". Но если вы создадите таблицу один раз, вы можете назначить ее любым переменным, которые захотите, и когда вы сравните их, Lua скажет вам, что они равны. Другими словами:

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

Итак, это простой, чистый способ делать то, что вы хотите. хранить key где-то, так что вы можете получить 4 назад, используя его. Это тоже очень быстро.

Если ты действительно не хочешь этого делать... ну, есть способ. Но это неэффективно и некрасиво.

Первая часть - создание функции, которая сравнивает две отдельные таблицы. Он должен возвращать 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

Ответ Кикито хорош, но имеет некоторые недостатки:

• Если вы выполняете t[{a=1}] = true два раза, store будет содержать две таблицы (утечка памяти за время существования хеш-таблицы)
• Изменение значения после того, как вы уже сохранили его, не работает, и вы не можете его удалить. Попытка изменить его приведет к тому, что поиск потенциально вернет любое значение, которое вы присвоили этой клавише в прошлом.
• Производительность доступа - O(n) (n - количество сохраненных записей и предполагается, что извлечение значения lua из таблицы - 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
})

Как вы предложили, совершенно другой вариант - написать собственную функцию хеширования. Вот HashTable, который может использовать это:

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'

Естественно, вы захотите получить лучшие функции Hash/Equals.

Пока хэши ваших ключей редко сталкиваются, производительность этого класса должна быть O (1).

(Примечание: я бы поместил верхнюю половину этого ответа в качестве комментария к kikito, но у меня нет репутации, чтобы сделать это.)

Answer 3

Это невозможно в Луа. Если вы используете таблицы в качестве ключей, ключ - это конкретный "экземпляр" таблицы. Даже если вы создаете другую таблицу с одинаковым содержимым, экземпляр отличается, поэтому это другой ключ.

Если вы хотите сделать что-то подобное, вы можете создать своего рода хеш-функцию, которая обходит таблицу, чтобы служить ключом (возможно, даже рекурсивно, если необходимо), и создать строковое представление содержимого таблицы. Он не должен быть удобочитаемым, если он различен для разного содержимого и одинаков для таблиц с одинаковым содержимым. Помимо использования pairs() чтобы пройти таблицу, вам также нужно вставить ключи в таблицу и отсортировать их, используя table.sort(), так как pairs() возвращает их в произвольном порядке, и вы хотите одну и ту же строку для "равных" таблиц.

После того, как вы сконструировали такую ​​строку, вы можете использовать ее в качестве ключа:

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

Я не очень много знаю о языковой обработке и о цели, которую вы хотите достичь с помощью своей программы, но как насчет сбора токенов, например, так: используйте структуру вложенных таблиц, в которой таблицы индексов хранят только таблицы, проиндексированные токеном первой фразы, тогда каждая подтаблица содержит значение, проиндексированное токеном второй фразы... и т. д.... пока вы не достигнете окончательного токена фразы, будет индексировать числовое значение, соответствующее вхождению фразы.

Может быть, это будет более понятно с примером, если у вас есть две следующие фразы:

• Мне нравится банан.
• Мне нравится горячая цыпочка.

Ваш индекс будет иметь следующую структуру:

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

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

Answer 5

Я думаю, что самый простой способ сделать что-то подобное - это иметьtableKeyфабрика, которая возвращает таблицы только для чтения для введенной таблицы.

Вы хотели бы назначить__key(или подобное) значение для использования в качестве ключей. Что-то вроде:

      _cachedTableKeys = {}
function tableKey (t)
  if(not t.__key) t.__key = calculateKey(t)
  local existing = _cachedTableKeys[t.__key]
  if(existing) return existing
  existing = readOnly(t) -- https://www.lua.org/pil/13.4.5.html
  _cachedTableKeys[t.__key] = existing
  return existing 
end

Это гарантирует, что таблица, используемая в качестве ключа, доступна только для чтения и что ее идентификатор всегда будет совпадать, если он равен.

Обратите вниманиеcalculateKeyфункция будет рекурсивно выполнять хеш-функцию для ключей таблицы. Вы хотите использовать достаточно большой хеш (например, 16 байт или около того), чтобы коллизия была практически невозможна. Вы также можете реализовать какой-то алгоритм коллизий при поиске таблицы по ключу.

Answer 6

Я не уверен, что вы можете сделать это. Вы можете определить равенство для таблиц, используя метатаблицу, но нет способа определить хеш-функцию, и я сомневаюсь, что определение равенства само по себе сделает то, что вам нужно. Очевидно, вы можете определить равенство, а затем перебрать таблицу, используя pairs() и сравнивая ключи самостоятельно, но это превратит то, что должно быть O(1) поиск в O(n),

Answer 7

Ответ kikito имеет начало решения, но, как отмечается в ответе chess123mate , он предназначен только для записи (среди других недостатков). Это решение не устраняет их всех, но это только начало. (Это тоже очень и очень медленно.)

      local function equivalent(stack)
    local a, b = stack.a, stack.b

    if type(a) ~= 'table' then return a == b end
    if a == b then return true end

    local top = stack.next
    while top ~= nil do
        if stack.a == a and stack.b == b then return true end
        top = stack.next
    end

    local counta, countb = 0, 0

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

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

    return counta == countb
end

t = setmetatable({}, {
    __newindex = function(tbl, key, value)
        for k, _ in pairs(tbl) do
            if equivalent({a = k, b = key}) then rawset(tbl, k, value); return end
        end
        rawset(tbl, key, value)
    end,
    __index = function(tbl, key)
        for k, v in pairs(tbl) do
            if equivalent({a = k, b = key}) then return v end
        end
    end
})

Ссылка Lua Playground (или ссылка GitHub Gist для копирования и вставки на игровую площадку, если ваш браузер меня ненавидит за это последнее).