Список ассоциаций в LISP - это то же самое, что словарь в C #?

Question

Я читаю книгу о Common LISP, и автор говорит: «Alist состоит из пар ключ / значение, хранящихся в списке».

Так что это заставило меня задуматься, это то же самое, что словарь в C # или нет? Если так, то почему?

Answer 1

Существует различие между абстрактными понятиями и конкретными структурами данных.

Словарь - это абстрактное понятие - отображение ключей на значения. Это может быть реализовано несколькими различными подходами:

• в виде списка: пары ключ-значение (списки Lisp), плоский список чередующихся ключей и значений (списки Lisp), как пара из двух списков ключей и значений
• как таблица, будь то хеш-таблица Лиспа / HashMap Java или какая-то другая таблица
• как дерево (TreeMap Java)
• и т.д.

Словарь C # - это структура данных, которая поддерживает (амортизируется) постоянное время поиска, как хеш-таблица CL. В этом отношении он отличается от alist тем, что имеет линейное время поиска. Кроме того, списки не зависят от хеш-кода элемента для его сохранения / извлечения. API списков также отличается от словаря. Есть assoc и rassoc для поиска элемента с левой и правой стороны соответственно. (Таким образом, в отличие от обычного словаря, в alist может быть несколько отображений одного и того же ключа на разные значения). Также есть acons и pairlis для построения alist.

РЕДАКТИРОВАТЬ И, наконец, нет стандартной функции для удаления элемента из списка. Вы можете удалить элемент с помощью (remove key alist :key #'car). Но обратите внимание, что эта операция оставляет исходный список без изменений и возвращает в результате измененный список.

Answer 2

Сравнение между алистами и хеш-таблицами (которые использует Dictionary), так как никто, кажется, еще не коснулся этого:

Alists:

• Просты в реализации (просто список пар)
• Иметь линейный поиск по времени (поэтому полезно только для небольших списков)

Хеш-таблицы:

• Приложите немного больше усилий для реализации (в частности, вы должны реализовать стабильную хэш-функцию для ключей)
• Амортизировал поиск в постоянном времени

Answer 3

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

Answer 4

Да, они очень похожи и служат сходной цели, но есть как минимум одно существенное отличие:

.NET Dictionary не может иметь несколько элементов с одним и тем же ключом!

По-видимому, список может :

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

Answer 5

Да, это одно и то же.Также называется ассоциативными массивами (perl) и картами (java и др.).