Хеш-таблицы в прологе - PullRequest
Новая
       50

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

27 голосов
/ 22 августа 2009

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

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

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

Ответы [ 5 ]

9 голосов
/ 23 августа 2009

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

Edit:

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

7 голосов
/ 23 ноября 2014

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

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

Синтаксис следующий:

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

Подробнее см. Dicts: структуры с именованными аргументами .

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

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

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

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

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

4 голосов
/ 25 августа 2009

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

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

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

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

3 голосов
/ 16 августа 2010

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

2 голосов
/ 15 февраля 2016

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

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

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

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

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

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

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

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

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

...