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

Ответ 1

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

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

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

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

Ответ 2

EDIT: Это не отвечает на вопрос, касающийся реализации.

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 является синтаксическим сахаром для этого тоже (?).

Ответ 3

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

Ответ 4

ArrayWithHash - это быстрая реализация гибрида array-hashtable в С++.

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