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

Question

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

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

, а затем я хочу иметь возможность искать:

t[key2]

и получить 4.

Iзнаю, что я могу превратить 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

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

Если вы хотите сделать что-то подобное, вы можете создать своего рода хеш-функцию, которая пересекаеттаблица, служащая ключом (может быть, даже рекурсивным, если необходимо) и создающая строковое представление содержимого таблицы.Он не должен быть удобочитаемым, если он различен для разного содержимого и одинаков для таблиц с одинаковым содержимым.Помимо использования 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 3

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

• Если вы выполните 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 4

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

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

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

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

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

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

Answer 5

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