为什么在性能方面，复合术语优于列表？例如，
matrix(row(1,2,3),row(1,2,3),row(1,2,3))
更好的选择是
[[1,2,3],[1,2,3],[1,2,3],[1,2,3]]
3个回答
7
首先，明确一点：列表是一种复合术语。
要了解列表是什么，请使用write_canonical/1。例如，在使用GNU Prolog时：
| ?- write_canonical([1,2,3]).
'.'(1,'.'(2,'.'(3,[])))
关于内存中的表示，我建议参考Richard O'Keefe的书。虽然不同系统的细节可能有所不同，但是可以确定，在内存中表示术语
row(1,2,3)，需要以下内容：
- 一个内存单元用于functor/arity
- 三个内存单元用于参数
.(1, .(2, .(3, [])，在简单直观的内存表示中，您需要：
- 三个内存单元用于三个
'.'/2functors - 三个内存单元用于1、2、3
- 可能需要更多（例如用于
[]）。
一些简单的测试可以帮助您自己了解这些表示在您的系统中的内存消耗差异。
- mat
2
6
另一个（优秀的）答案没有提到的一点：
通过位置访问列表成员意味着您需要遍历列表。访问术语的参数应该在常数时间内可行。因此，对于随机访问，术语应更有效率。
简短的旁白：您可以尝试使列表遍历稍微快一些。但是，SWI-Prolog实现的nth0_det/3几乎让人绝望；）
您可能会对此主题感兴趣，特别是这个摘要，其中涉及列表和术语等内容。
以下是一些经验法则。
用例：
- 如果您预先知道有多少事物，请使用术语。
- 如果您可以拥有0个或多个相同的事物，请使用列表。
- 如果您需要查找表，则两者都不是最佳选择
效率：
- 如果您想要随机访问，请使用术语
- 如果您的算法在单链表上运行良好，则Prolog列表是完美的选择。
从最后一点可以得出结论：尝试找到使用链接列表而不是随机访问数组的算法。这并不总是可能的，但对于许多问题，您有选择。经典示例将是快速排序与归并排序：在Prolog中，归并排序肯定更快。
无论哪种方式，首先确保正确理解问题，然后再考虑效率。并确保在开始优化之前测量性能瓶颈。
选择最佳算法和数据结构当然意味着您需要了解自己的问题和可用工具。虽然与您的问题无关，但C ++的“标准模板库”的美妙之处在于，对于算法和数据结构，时间复杂度（“大O表示法”）是固有属性，而不是实现细节。
- user1812457
9
你确定这句话吗：“一个经典的例子是快速排序和归并排序：在Prolog中，归并排序肯定更快。”？ - repeat
1@repeat 在纯Prolog中对列表进行排序，我个人无法想出一个快速排序实现，它能接近我的归并排序实现。因此，这句话更多地揭示了我的问题，而不是其他任何事情。 - user1812457
1哈哈，只是认真地说 :) 但说实话...你已经彻底地搜索这些情况了吗？我还没有（尚未）。不管怎么样...与此同时，请安慰自己林纳斯的一句名言：“理论和实践有时会发生冲突。当这种情况发生时，理论总是失败。每一次”。 - repeat
这个问题可以升级从SO的评论层次到SO的问题层次吗？ - repeat
@repeat Prolog和排序的问题在于几乎没有实际理由不使用内置排序。特别是SWI-Prolog有
sort/4谓词，我找不到玩转纯Prolog排序的好借口。 - user1812457显示剩余4条评论
4
另一个方面是访问特定元素时的时间性能。使用列表可线性访问其元素。但对于形式为
但对于您提出的问题并没有确定的答案。最佳解决方案取决于您要解决的具体问题。例如，在所有参数应用操作可能比使用基于
functor(arg1, arg2, ..., argn, ...)的复合术语，我们可以使用标准的arg/3内置谓词以便对任何参数实现常量访问。即对于任何明智的Prolog实现，O(N)与O(1)相比。但对于您提出的问题并没有确定的答案。最佳解决方案取决于您要解决的具体问题。例如，在所有参数应用操作可能比使用基于
arg/3的解决方法更快。但这也将取决于所使用的Prolog系统。如果性能是主要关注点，则基准测试非常重要。只需避免在微观层面上进行测试，而应考虑如何在处理相关应用程序的所有部分中创建和访问术语。- Paulo Moura
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
[]和术语'.'/2，因此（浅层）第一个参数索引无法区分长度为1、2、3等的列表。支持列表：您的Prolog系统可能对复合术语的元数*有继承限制，因此在某些情况下，使用类似列表的结构可能需要表示大量元素的集合。Richard的书包含更多有关这两个方面以及其他方面的宝贵信息。 - mat