Хэш-таблицы в прологе

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

Итак, мой первый вопрос: есть ли прологи, которые поддерживают подобную словарю структуру данных с характеристиками производительности хеш-таблицы?

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

Ответ 1

Я только что узнал, что:

Версия 7 SWI-Prolog представляет диктовки как абстрактный объект с конкретным современным синтаксисом и функциональной нотацией для доступа к членам, а также к функциям доступа, определенным пользователем.

Синтаксис выглядит следующим образом:

Tag{Key1:Value1, Key2:Value2,...}

См. Dicts: структуры с именованными аргументами для деталей.

Обратите внимание, что:

Это первоклассные граждане языка
Семантика объединения между диктатами может измениться в будущем
Оператор. /2, ранее использовавшийся для поиска, был изменен для доступа к элементам dict с помощью выражений, таких как point{x:1,y:2}.x
Dicts могут быть деструктивно изменены, но это не рекомендуется, так как " нелогично ", не говоря уже о нефункциональности.
Текущая базовая реализация - это "составной термин с использованием аргумента dict. Первым аргументом является тег. Остальные аргументы создают массив отсортированных пар ключ-значение".

Временная сложность операций настоящей реализации (2019) приведена в руководстве по SWI Prolog в разделе "5.4.5: Замечания по реализации о диктантах":

Dicts в настоящее время представлены как составной термин, используя dict. Первый аргумент - это тег. Оставшиеся аргументы создают массив отсортированных пар ключ-значение. Это представление компактно и гарантирует хорошее месторасположение. Поиск - это журнал порядка (N), в то время как добавление значений, удаление значений и слияние с другими диктовками имеет порядок N. Основной недостаток состоит в том, что изменение значений в больших диктовках является дорогостоящим как с точки зрения памяти, так и времени.

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

Ответ 2

В некоторых средах Prolog есть списки Ассоциации, которые можно использовать для создания и редактирования словаря:

Edit:

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

SWI-Prolog Java или C++
GNU Prolog Интерфейс C
SICStus C, С++ и Java/.Net.

Ответ 3

Я не парень Пролога (только внешний наблюдатель), но я нашел это:

http://www.sics.se/sicstus/docs/4.0.7/html/sicstus/lib_002davl.html

когда я искал "сбалансированные деревья с простыми конечными картами". Он говорит об альтернативной реализации списков ассоциаций.

(Почему я подумал об этом: в Haskell, чисто функциональном языке, вместо списков ассоциаций или хеш-таблиц, обычно используют деревья для (постоянных) словарей или конечных карт. Lookups также O (log (N)). См. Data.Map для некоторых ссылок на реализацию карт со сбалансированными деревьями.)

Ответ 4

В SICStus Prolog используйте assoc или avl.

Ответ 5

Следующие комментарии касаются вашего вопроса в порядке, грубо говоря, от "более конкретного" до "более общего".

Сначала, обращаясь к вашему конкретному комментарию:

Я бы использовал хэш-таблицу/словарь, но насколько я знаю, это невозможно в Прологе.

Все серьезные реализации Prolog позволяют деструктивно изменять термины Prolog, используя, например, setarg/3. Использование arg/3 и setarg/3 дает вам O (1) доступ к каждому аргументу термина, чего достаточно для реализации хэш-таблицы точно так же, как и на других языках, если ваша система не устанавливает произвольные ограничения на атрибуты терминов.

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

Какие библиотеки? Я второй, что другие написал: вместо хэширующих библиотек используйте древовидные библиотеки, такие как library(assoc), library(avl) и т.д. Они не так эффективны, как хэши в среднем случае, но:

они часто достаточно эффективны
они масштабируются очень предсказуемо: наиболее важные операции всегда в O (log (n)).

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

Наконец, расшифровки расширений SWI-Prolog не соответствуют ISO, даже синтаксически и, следовательно, не переносятся в совместимые системы Prolog! См. Ulrich Neumerkel комментарии о том, как добавить инфиксную точку в ISO-совместимый способ.