Эффективная космическая реализация неизменяемой карты в Прологе?

Question

Это вопрос о структуре данных карты, которая сохраняет эффективную память при тяжелых неразрушающих манипуляциях.

контекст

Я пишу небольшую программу, в которой я генерирую "состояния" (которые являются просто терминами, содержащими данные) в предикате iterate/2 в соответствии с некоторой логикой, которая может быть проигнорирована для целей настоящего обсуждения.

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

Количество состояний, "виденных ранее", может быть значительным (несколько десятков тысяч). Тем не менее, нам разрешено время от времени "забывать" (большой процент) ранее увиденных записей. Это хорошо, так как мы можем надеяться, что общие требования к памяти будут ограничены.

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

Предположим, у нас есть такая структура данных карты.

• Для любого вновь сгенерированного состояния вычислите значение хеша (любыми средствами) из указанного состояния и вставьте пару (хеш, состояние) как (ключ, значение) в карту.
• Чтобы проверить, было ли состояние уже замечено ранее, вычислите его значение хеша и проверьте, существует ли запись, соответствующая этому значению хеша, на карте. (Для этого упражнения мы не учитываем возможность коллизий хешей)

Затем постоянно изменяемая структура данных карты передается между вызовами iterate,

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

Предикаты, связанные с картой, которые мы предлагаем, могут быть:

map_new(?Map)  

... объединить карту с пустой картой.

map_get(+Map,+Key,?Val)  

... объединить Val со значением, связанным с ключом Key в карте Map, или потерпеть неудачу, если Map не содержит такого ключа (разрешив Key быть переменной, можно реализовать перечисление посредством обратного отслеживания).

map_put(+Map,+Key,?Val,?OldVal,?NewMap)

... чтобы объединить карту NewMap с картой, полученной путем вставки пары (Key,Val) в карту Map. Если карта Map уже содержит запись с ключом Key, значение указанной записи унифицируется с OldVal.

map_rem(+Map,+Key,?OldVal,?NewMap) 

... объединить карту NewMap с картой, полученной путем удаления записи с ключом Key из карты Map. Значение, связанное с ключом Key на карте Map, объединено со OldVal. Сбой, если карта Карта не содержит ключ Key.

И мы будем использовать выше, как это:

iterate(Solution) :-
   map_new(Map),
   iterate(Map,Solution).

iterate(M,S) :-
   gen_fresh_states(ListFresh),
   gen_stale_states(ListStale),
   add_fresh_states(M,ListFresh,MM),
   del_stale_states(MM,ListStale,MMM),
   ( termination_check(MMM,S) -> true ; iterate(MMM,S) ).

куда

 add_fresh_states(M,ListFresh,MM),
 del_stale_states(MM,ListStale,MMM),

перебирать списки состояний ListFresh и ListStale ожидаемым образом, итеративно вызывая map_put/5 или же map_rem/4,

А также -> ; это предикат ->/2.

проблема

На данный момент нам нужно выбрать хорошую реализацию для карты. Нам не нужна структура, которая чрезмерно изменяется при удалении или добавлении одного элемента, чтобы базовая реализация могла сохранять операции копирования и, как правило, занимать мало места в куче, ссылаясь на подструктуры (например, поддеревья) карты. M всякий раз, когда MM построен из него во время map_put/5 или же map_rem/4,

(Например, я слышал, что Clojure использует эффективные реализации в этом смысле для некоторых из своих 4 [неизменяемых карт], но я не стал вдаваться в подробности.)

В SWI Prolog у нас есть реализация Assoc с поддержкой AVL-дерева. Это отлично подходит для быстрого поиска. К сожалению, деревья AVL могут сильно изменяться всякий раз, когда узел дерева вставляется или удаляется. Между фактическим расположением карт в куче может быть мало общего M, MM, MMM или любая карта между ними: куча, вероятно, быстро заполняется. Реализация assoc в Прологе, кстати. (/usr/lib64/swipl-7.2.3/library/assoc.pl), нет специального соуса, который входит в него.

Я ошибаюсь, полагая, что древовидные карты AVL не справятся с этой задачей?

В качестве альтернативы, есть ли какие-либо реализации карт (не обязательно в SWI Prolog), которые могут эффективно использовать субструктуру?

Я полагаю, что уже можно облегчить использование кучи с помощью "!" между подцелями iterate/2, Это сообщит среде выполнения, что обратного отслеживания не произойдет, и, таким образом, даст ей лицензию на уничтожение любых структур в куче, которые больше никогда не будут использоваться. Например, "!" после звонка del_state_states/3 потенциально делает MM имеет право на сборку мусора (я не знаю, действительно ли это работает, хотя).

Answer 1

Я ошибаюсь, полагая, что древовидные карты AVL не справятся с этой задачей?

По всей вероятности: да.

По моему опыту, library(assoc) является отличным выбором для многих задач, которые требуют доступа, как вы описываете. Я рекомендую вам попробовать!

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

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

Кандидатскую диссертацию Криса Окасаки " Чисто функциональные структуры данных" стоит посмотреть в таких ситуациях.