Хэш-таблицы в прологе
Я решил головоломку в прологе на днях и понял, что если я использую другой язык программирования, я бы использовал хэш-таблицу/словарь, но насколько я знаю, это невозможно в прологе.
Итак, мой первый вопрос: есть ли прологи, которые поддерживают подобную словарю структуру данных с характеристиками производительности хеш-таблицы?
Во-вторых, мне пришло в голову, что, поскольку большинство прологов используют хэш-таблицу для хранения предикатов, я мог бы написать предикат оболочки для утверждения и отвода фактов, создавая интерфейс словаря, который будет использовать основную хеш-таблицу предикатов. Но могу ли я получить характеристики производительности хеш-таблицы, или добавит ли интерфейс накладные расходы, которые снизили бы производительность?
Ответы
Ответ 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:
Возможно, вы сможете повысить производительность за счет реализации предикатов на иностранных языках, например:
Ответ 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-совместимый способ.
