Это вопрос о структуре карты, которая сохраняет память при тяжелых неразрушающих манипуляциях.Пространственная эффективная реализация неизменной карты в Prolog?
Контекст
Я пишу небольшую программу, в результате чего я произвожу «состояния» (которые только термины, содержащий данные) в предикате iterate/2 по какой-то логике, можно пренебречь для целей настоящего обсуждения ,
iterate/2 рекурсивно выступает в хвостовой рекурсивной манере. При каждом вызове iterate/2 генерирует больше состояний и должен эффективно проверять, было ли ранее обнаружено какое-либо состояние.
Число штатов, «ранее замеченных», может быть значительным (несколько десятков тысяч). Тем не менее, нам разрешено время от времени «забывать о» (жирный процент) ранее замеченных записей. Это хорошо, так как мы можем надеяться сохранить общие требования к памяти в пределах границ.
Для эффективного выполнения «ранее увиденного» предиката интерфейс «карты», поддерживаемый соответствующей реализацией, кажется хорошим выбором (потому что можно эффективно реализовать поиск в картах).
Предположим, что у нас есть такая структура данных карты.
- Для любого вновь сгенерированного состояния вычислите значение хэша (любыми средствами) из указанного состояния и вставьте пару (хеш, состояние) как (ключ, значение) в карту.
- Чтобы проверить, было ли ранее обнаружено состояние, вычислите его значение хеша и проверьте, существует ли запись, соответствующая этому хеш-значению на карте. (Для этого упражнения мы пренебрегаем возможность хэш столкновений)
Когда-либо другая карта структура данных затем передается между сеансами iterate.
Это логический язык программирования, мы хотим сохранить общую идею работы в вечном математическом пространстве всех возможных структур, не подлежащих определению, где мы переходим от одной структуры к другой, как обезьяна, качающаяся с вино, вместо того, чтобы постоянно мутировать изменяющуюся во времени структуру данных, как и в императивном программировании. Мы просто надеемся, что сборщик мусора быстрее, чем мы!
Картографические связанные предикаты, которые мы предлагаем может быть:
map_new(?Map)
... унифицировать карту с пустой картой.
map_get(+Map,+Key,?Val)
... унифицировать Вал со значением, связанным с ключом Key в карте Карте или потерпеть неудачу, если карта не содержит такое ключ (Key, позволяя быть переменным, можно осуществить перечисления через возвраты).
map_put(+Map,+Key,?Val,?OldVal,?NewMap)
... унифицировать карту NewMap с картой, полученной путем вставки (Key, Val) Пара на карте Карта. Если Map Map уже содержит запись с ключевым ключом, значение указанной записи объединяется с OldVal.
map_rem(+Map,+Key,?OldVal,?NewMap)
... унифицировать карту NewMap с картой, полученной путем удаления записи с ключом Ключ от карты карты. Значение, связанное с ключом Ключ на карте Карта унифицирован с помощью OldVal. Ошибка, если карта Map не содержит ключевого ключа.
И мы будем использовать выше, как это:
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 мы имеем AVL-tree -backed реализация assoc. Это отлично подходит для быстрого поиска. К сожалению, деревья AVL могут сильно измениться всякий раз, когда узел дерева вставлен или удален. Не может быть много общего между фактическим расположением кучи карт M, MM, MMM или любой другой картиной: куча, вероятно, быстро заполнится. Реализация assoc находится в Prolog btw. (/usr/lib64/swipl-7.2.3/library/assoc.pl), в него нет специального соуса.
Я ошибаюсь в мышлении AVL на основе дерева карты не будут соответствовать задаче?
В качестве альтернативы, существуют ли какие-либо реализации карты (не обязательно в SWI Prolog), которые могут эффективно использовать подструктуру?
Я полагаю, что уже можно смягчить использование кучи, используя «!» между подлогами iterate/2. Это покажет время выполнения, что обратное отслеживание не произойдет, и, таким образом, дает ему лицензию на уничтожение любых структур на кучи, которые больше никогда не будут использоваться. Например, "!" после вызова del_state_states/3 потенциально может сделать MM подходящим для сбора мусора (я не знаю, действительно ли это работает).
Где именно, тогда? –
Хорошо, спасибо, ложь. Моя интуиция все еще слаба. –