Гибридный массив и хэш-таблица Lua; это существует где-нибудь еще?

Question

Реализация таблиц Lua хранит свои элементы в двух частях: часть массива и часть хеша.

Существует ли такая вещь на каких-либо других языках?

Взгляните на раздел 4, Таблицы, в Реализация Lua 5.0 .

Исходный код Lua 5.1 - table.c

Answer 1

Эта идея была оригинальной с Роберто Иерусалимским и остальной командой Lua. Я слышал, как Роберто выступил с докладом об этом на семинаре по облегченным языкам в Массачусетском технологическом институте в 2003 году, и в этом выступлении он обсуждал предыдущую работу и убедительно доказывал, что идея была новой. Я не знаю, копировали ли это другие языки с тех пор.

Оригинальный Awk имеет несколько более ограниченную языковую модель, чем Lua; в качестве ключа в массиве может использоваться либо число, либо строка, но сами массивы не являются первоклассными значениями: массив должен иметь имя, а массив не может использоваться в качестве ключа в массиве.

Что касается реализации, я проверил источники исходного Awk, поддерживаемые Брайаном Керниганом, и реализация Awk использует хеш-таблицу, а не структуру гибридного массива / таблицы Lua. Различие важно, потому что в Lua, когда таблица используется с последовательными целочисленными ключами, затраты пространства такие же, как и для массива C. Это не верно для оригинального Awk.

Я не удосужился исследовать все последующие реализации awk, например, Gnu Awk, mawk и т. Д.

Answer 2

РЕДАКТИРОВАТЬ: Это не отвечает на вопрос, который был о реализации.

AWK тоже сделал это.

Интересно, как некоторые языки объединяют операции, отличающиеся в других:

• Индексирование списка - a[10]
• Ассоциативное индексирование - a['foo']
• Доступ к полям объекта - a.foo
• Вызовы функций / методов - a('foo') / a.foo()

Очень неполные примеры:

• Perl - это редкий язык, в котором последовательное / ассоциативное индексирование имеет отдельный синтаксис - a[10] / a{'foo'}. AFAIK, поля объекта отображаются на одну из других операций, в зависимости от того, что разработчик класса хотел использовать.

• В Python все 4 различны; последовательное / ассоциативное индексирование использует тот же синтаксис, но для них оптимизированы отдельные типы данных.

• В Ruby поля объекта являются методами без аргументов - a.foo.

• В JavaScript поля объектов a.foo являются синтаксическим сахаром для ассоциативной индексации a['foo'].

• В Lua и AWK ассоциативные массивы также используются для последовательной индексации - a[10].

• В Arc последовательное и ассоциативное индексирование выглядит как вызовы функций - (a 10) / (a "foo"), и я думаю, что a.foo также является синтаксическим сахаром для этого (?).

Answer 3

Самая близкая вещь, о которой я могу подумать, это Javascript - вы создаете массив с new Array(), а затем переходите к индексированию по номеру или по строковому значению. Вполне возможно, по соображениям производительности некоторые реализации Javascript решили сделать это, используя два массива, по причинам, указанным в документации по Lua, на которую вы ссылались.

Answer 4

ArrayWithHash - быстрая реализация гибридного массива в C ++.

Поскольку C ++ является статически типизированным языком, в ArrayWithHash разрешены только целочисленные ключи (нет способа вставить строку или ключ указателя). Другими словами, это что-то вроде массива с резервной копией хеш-таблицы для больших индексов. Также он использует другую реализацию хеш-таблицы, которая менее эффективна по сравнению с реализацией Lua-таблицы.