Space-Prolog 中高效的不可变映射实现？
Space-efficient immutable map implementation in Prolog?
这是一个关于在大量非破坏性操作下保持内存高效的地图数据结构的问题。
上下文
我正在编写一个小程序，根据一些逻辑在谓词 iterate/2 中生成 "states"（它们只是保存数据的术语），出于当前讨论的目的可以忽略该逻辑.
iterate/2 以尾递归方式递归调用自身。在每次调用时，iterate/2 都会生成更多状态，并且必须有效地检查之前是否已经看到任何状态。
状态的数量"previously seen"可能相当可观（几万）。但是，我们可以不时地 "forget about"（一定百分比）以前看到的条目。这是一件好事，因为我们希望将整体内存需求保持在一定范围内。
为了有效执行 "previously seen" 谓词，由适当的实现支持的 "map" 接口似乎是一个不错的选择（因为可以有效地在映射中实现查找）。
假设我们有这样一个地图数据结构。
- 对于任何新生成的状态，从所述状态计算哈希值（通过任何方式），并将对 (hash,state) 作为 (key,value) 插入到映射中。
- 要检查一个状态之前是否已经看到，计算它的哈希值并检查地图中是否存在对应于该哈希值的条目。 （对于本练习，我们忽略哈希冲突的可能性）
然后在 iterate 的调用之间传递不断不同的地图数据结构。
这是一种逻辑编程语言，我们希望维持在所有可能的定义不可变结构的永恒数学 space 中工作的总体思路，我们从一个结构移动到下一个结构，例如一只猴子从藤蔓上荡来荡去，而不是像我们在命令式编程中那样不断地改变时变数据结构。我们只希望垃圾收集器比我们快！
我们提供的与地图相关的谓词可能是：
map_new(?Map)
...统一Map与空图
map_get(+Map,+Key,?Val)
...将 Val 与映射 Map 中的键 Key 关联的值统一，或者如果 Map 不包含这样的 Key 则失败（通过允许 Key 是一个变量，可以通过回溯实现枚举） .
map_put(+Map,+Key,?Val,?OldVal,?NewMap)
...将map NewMap 与map Map 中插入(Key,Val) 对得到的map 统一起来。如果map Map中已经包含key为Key的条目，则该条目的值统一为OldVal。
map_rem(+Map,+Key,?OldVal,?NewMap)
...将map NewMap 统一为从map Map 中去掉key 为key 的条目得到的map。 map Map 中key Key 关联的值与OldVal 统一。如果映射 Map 不包含键 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谓词。
问题
此时，我们需要为地图选择一个好的实现。我们不希望在删除或添加单个项目时过度更改结构，以便底层实现可以通过引用 map M 的子结构（例如子树）来保持复制操作和通常堆 space 低每当 MM 在 map_put/5 或 map_rem/4 期间从它构造时。
（例如，我听说 Clojure 对其某些 4[不可变映射] 使用了这种意义上的高效实现，但我没有仔细研究过。）
在 SWI Prolog 中，我们有 AVL-tree-backed implementation of assoc。这非常适合快速查找。不幸的是，每当插入或删除树节点时，AVL 树可能会发生很大变化。映射 M、MM、MMM 或介于两者之间的任何映射的实际堆上布局之间可能没有太多共同点：堆可能会迅速填满。 assoc 的实现在 Prolog 顺便说一下。 (/usr/lib64/swipl-7.2.3/library/assoc.pl)，里面没有特别的酱料。
我是不是误以为基于 AVL 树的地图无法胜任这项任务？
或者，是否有任何映射实现（不一定在 SWI Prolog 中）能够有效地重用子结构？
我想人们已经可以通过使用“！”来减少堆的使用了。在 iterate/2 的子目标之间。这将告诉运行时不会发生回溯，从而授予它销毁任何不会再次使用的堆上结构的许可。例如，一个“！”在调用 del_state_states/3 之后可能会使 MM 有资格进行垃圾回收（不过我不知道这是否真的有效）。
Am I mistaken in thinking AVL tree-based maps won't be up to the task?
很有可能：是。
根据我的经验，library(assoc) 对于您描述的许多需要访问权限的任务来说是 极好的 选择。我建议您试一试！
在实践中，对数开销通常非常可以接受，您也可以经常从头开始重新构建地图以删除不需要的元素。
另请注意，许多其他平衡树结构（红黑树等）也承认自然和 纯 Prolog 实现，如果 AVL 树变成 不适合你，我建议你检查一些纯粹的替代品。
Chris Okasaki 的博士论文 Purely Functional Data Structures 在这种情况下非常值得一看。
这是一个关于在大量非破坏性操作下保持内存高效的地图数据结构的问题。
上下文
我正在编写一个小程序，根据一些逻辑在谓词 iterate/2 中生成 "states"（它们只是保存数据的术语），出于当前讨论的目的可以忽略该逻辑.
iterate/2 以尾递归方式递归调用自身。在每次调用时，iterate/2 都会生成更多状态，并且必须有效地检查之前是否已经看到任何状态。
状态的数量"previously seen"可能相当可观（几万）。但是，我们可以不时地 "forget about"（一定百分比）以前看到的条目。这是一件好事，因为我们希望将整体内存需求保持在一定范围内。
为了有效执行 "previously seen" 谓词，由适当的实现支持的 "map" 接口似乎是一个不错的选择（因为可以有效地在映射中实现查找）。
假设我们有这样一个地图数据结构。
- 对于任何新生成的状态，从所述状态计算哈希值（通过任何方式），并将对 (hash,state) 作为 (key,value) 插入到映射中。
- 要检查一个状态之前是否已经看到，计算它的哈希值并检查地图中是否存在对应于该哈希值的条目。 （对于本练习，我们忽略哈希冲突的可能性）
然后在 iterate 的调用之间传递不断不同的地图数据结构。
这是一种逻辑编程语言，我们希望维持在所有可能的定义不可变结构的永恒数学 space 中工作的总体思路，我们从一个结构移动到下一个结构，例如一只猴子从藤蔓上荡来荡去，而不是像我们在命令式编程中那样不断地改变时变数据结构。我们只希望垃圾收集器比我们快！
我们提供的与地图相关的谓词可能是：
map_new(?Map)
...统一Map与空图
map_get(+Map,+Key,?Val)
...将 Val 与映射 Map 中的键 Key 关联的值统一，或者如果 Map 不包含这样的 Key 则失败（通过允许 Key 是一个变量，可以通过回溯实现枚举） .
map_put(+Map,+Key,?Val,?OldVal,?NewMap)
...将map NewMap 与map Map 中插入(Key,Val) 对得到的map 统一起来。如果map Map中已经包含key为Key的条目，则该条目的值统一为OldVal。
map_rem(+Map,+Key,?OldVal,?NewMap)
...将map NewMap 统一为从map Map 中去掉key 为key 的条目得到的map。 map Map 中key Key 关联的值与OldVal 统一。如果映射 Map 不包含键 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谓词。
问题
此时，我们需要为地图选择一个好的实现。我们不希望在删除或添加单个项目时过度更改结构，以便底层实现可以通过引用 map M 的子结构（例如子树）来保持复制操作和通常堆 space 低每当 MM 在 map_put/5 或 map_rem/4 期间从它构造时。
（例如，我听说 Clojure 对其某些 4[不可变映射] 使用了这种意义上的高效实现，但我没有仔细研究过。）
在 SWI Prolog 中，我们有 AVL-tree-backed implementation of assoc。这非常适合快速查找。不幸的是，每当插入或删除树节点时，AVL 树可能会发生很大变化。映射 M、MM、MMM 或介于两者之间的任何映射的实际堆上布局之间可能没有太多共同点：堆可能会迅速填满。 assoc 的实现在 Prolog 顺便说一下。 (/usr/lib64/swipl-7.2.3/library/assoc.pl)，里面没有特别的酱料。
我是不是误以为基于 AVL 树的地图无法胜任这项任务？
或者，是否有任何映射实现（不一定在 SWI Prolog 中）能够有效地重用子结构？
我想人们已经可以通过使用“！”来减少堆的使用了。在 iterate/2 的子目标之间。这将告诉运行时不会发生回溯，从而授予它销毁任何不会再次使用的堆上结构的许可。例如，一个“！”在调用 del_state_states/3 之后可能会使 MM 有资格进行垃圾回收（不过我不知道这是否真的有效）。
Am I mistaken in thinking AVL tree-based maps won't be up to the task?
很有可能：是。
根据我的经验，library(assoc) 对于您描述的许多需要访问权限的任务来说是 极好的 选择。我建议您试一试！
在实践中，对数开销通常非常可以接受，您也可以经常从头开始重新构建地图以删除不需要的元素。
另请注意，许多其他平衡树结构（红黑树等）也承认自然和 纯 Prolog 实现，如果 AVL 树变成 不适合你，我建议你检查一些纯粹的替代品。
Chris Okasaki 的博士论文 Purely Functional Data Structures 在这种情况下非常值得一看。