4

假设我们有以下内容：

edge(a, 1, 10).
edge(b, 2, 20).
edge(c, 3, 30).
edge(d, 4, 40).

我想提取M这些事实的矩阵表示 ( )，这样

M = [[a,b,c,d],[1,2,3,4],[10,20,30,40]]

这是一个简单的解决方案：

edgeMatrix(M) :-
  findall(A, edge(A, _, _), As),
  findall(B, edge(_, B, _), Bs),
  findall(C, edge(_, _, C), Cs),
  M = [As, Bs, Cs].

但是，这种方法存在一些问题，即：

  1. 我们遍历数据库n次，其中n是参数的数量；和
  2. 这不能很好地推广到任意n。

所以问题是：在 Prolog 中实现这一目标的最惯用的方法是什么？

4

2 回答 2

5

关于什么：

edgeMatrix(M) :-
    findall([A,B,C],edge(A,B,C),Trans),
    transpose(Trans,M).

现在您可以简单地从模块中导入transpose/2矩阵，或者像在这个答案中那样自己实现一个（是的，我知道这很懒，但是重新发明轮子有什么意义呢？）。clpfd

如果我在 中运行它swipl，我会得到：

?- edgeMatrix(M).
M = [[a, b, c, d], [1, 2, 3, 4], [10, 20, 30, 40]].

这看起来完全像你想要的。

你当然可以说计算 仍然有一些计算开销transpose/2，但是收集阶段只完成一次（如果这些不仅仅是事实，而是子句的答案），这也可能很昂贵，而且我认为一个模块无论如何都会非常有效地实现子句。

于 2017-01-05T21:04:46.850 回答
2

我认为您不会找到一个既完全通用又效率最高的解决方案。这是 N = 3 的简单解决方案：

edges(Edges) :-
    Goal = edge(_A, _B, _C),
    findall(Goal, Goal, Edges).

edges_abcs_([], [], [], []).
edges_abcs_([edge(A,B,C)|Edges], [A|As], [B|Bs], [C|Cs]) :-
    edges_abcs_(Edges, As, Bs, Cs).

edges_abcs([As, Bs, Cs]) :-
    edges(Edges),
    edges_abcs_(Edges, As, Bs, Cs).

添加 100,000 个附加edge/3事实后，执行如下：

?- time(edges_abcs(M)).
% 200,021 inferences, 0.063 CPU in 0.065 seconds (97% CPU, 3176913 Lips)
M = [[a, b, c, d, 1, 2, 3, 4|...], [1, 2, 3, 4, 1, 2, 3|...], [10, 20, 30, 40, 1, 2|...]].

为了进行比较，以下是问题中实施的度量：

?- time(edgeMatrix_orig(M)).
% 300,043 inferences, 0.061 CPU in 0.061 seconds (100% CPU, 4896149 Lips)
M = [[a, b, c, d, 1, 2, 3, 4|...], [1, 2, 3, 4, 1, 2, 3|...], [10, 20, 30, 40, 1, 2|...]].

这是基于transpose/2Willem 的更通用的解决方案：

?- time(edgeMatrix_transpose(M)).
% 700,051 inferences, 0.098 CPU in 0.098 seconds (100% CPU, 7142196 Lips)
M = [[a, b, c, d, 1, 2, 3, 4|...], [1, 2, 3, 4, 1, 2, 3|...], [10, 20, 30, 40, 1, 2|...]].

因此，就推理数量而言，我的解决方案似乎是最好的：100,000findall/3个推理用于遍历列表，100,000 个推理用于遍历列表。该问题的解决方案对每个 有 100,000 个推论findall/3，但仅此而已。但是，它稍微快一些，因为它更节省内存：分配的所有内容都最终出现在最终解决方案中，而我的程序分配了一个包含 100,000 个edge/3术语的列表，然后必须对其进行垃圾收集。（在 SWI-Prolog 中，如果您打开分析器和/或 GC 跟踪，您可以看到垃圾收集。）

如果我真的需要它尽可能快并且可以推广到许多不同的 N 值，我会编写一个宏来扩展为问题中的解决方案。

编辑：如果取消“惯用”要求，我会求助于将edge数据库作为列表存储在 SWI-Prolog 全局变量中。在这种情况下，我的单通道实现将在没有findall/3开销且不会产生中间垃圾的情况下工作。

于 2017-01-06T12:32:20.293 回答