Как реализовать карту с уникальными ключами, которые сами по себе являются таблицами в Lua?

Большинство языков предлагают способ эффективно реализовать карты для ЛЮБОГО типа ключа либо с помощью отношения эквивалентности и хеш-функции (с хеш-таблицами), либо с использованием отношения порядка (с деревьями).

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

Это своего рода требуется для реализации поведения, аналогичного индексу базы данных или кешу для некоторого значения на основе «уникальных» ключей, по крайней мере, без использования линейного поиска по времени.

Единственное, что я мог придумать, это то, что если ключевой объект состоит из полей f1,...,fn, мы могли бы сделать кучу вложенных карт и посмотреть их так T[f1][f2]...[fn] (по крайней мере, если поля сами являются целыми числами или строками). Это довольно ужасно и нарушает намерение инкапсулировать f1,...,fn в «объект».

Есть другие идеи?


lua lua-table
person yonil    schedule 22.08.2013    source источник
comment
Вы пробовали переопределить __index метаметод в своей таблице? Это позволяет вам самостоятельно управлять способом использования индексов. Затем вы можете проверить содержимое ключевой таблицы вместо ссылки на нее. См. lua.org/pil/13.4.1.html.   -  person SolarBear    schedule 22.08.2013

Ответы (2)


arrow_upward
3
arrow_downward

Похоже, вы хотите что-то вроде this.

В противном случае правильным подходом было бы сериализовать ваш ключ в строку детерминированным способом и использовать результат (или его хеш) в качестве ключа.

Как SolarBear сказал вам в комментарии, вы можете затем использовать метаметоды, чтобы у него был тот же интерфейс, что и у обычной таблицы.

person catwell    schedule 22.08.2013
comment
не будет ли использование хэша ключа полагаться на отсутствие хеш-коллизий вообще? даже переопределение __index не помешает ему перезаписать более раннюю запись с тем же значением хэша [если я правильно понял] - person yonil; 22.08.2013
comment
@catwell Для пояснения - я полагаю, что когда вы говорите сериализовать детерминированным способом, вы имеете в виду создание взаимно-однозначного сопоставления между фактическим ключом и его внутренним строковым представлением. - person Lorenzo Donati -- Codidact.com; 22.08.2013
comment
@yonil, если вы используете хеш, вам придется самостоятельно обрабатывать столкновения внутри __index и __newindex. Я полагаю, что хеширование может быть полезным только в том случае, если внутреннее строковое представление становится слишком большим и расходует много памяти. Подходящая хеш-функция может быть способом его сжать. Я предполагаю, что это компромисс между памятью и сложностью реализации (@catwell, если я правильно угадаю, что вы имели в виду). - person Lorenzo Donati -- Codidact.com; 22.08.2013
comment
Да, это компромисс, но если вы хотите использовать большие таблицы в качестве ключей, это действительно хорошо. Что касается коллизий, вы можете просто использовать хеш-функцию без технически никакого риска коллизии, такую ​​как SHA-256. А для сериализации вы могли бы использовать, вероятно, внутреннее представление или любую достаточно быструю библиотеку сериализации, которая имеет нужные вам свойства. - person catwell; 23.08.2013

arrow_upward
0
arrow_downward

Вы можете индексировать таблицы с таблицами, что позволяет использовать их в качестве справочных.

local cache = {}
local t = {}
cache[t] = 345 -- key is not important, but must not equal nil
local other = {
  ref = t
}

...
print(cache[other.ref]
person lipp    schedule 01.07.2014