Prolog中的复合术语和列表

Question

为什么复合术语在性能方面优于列表？例如,

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]]

谢谢!

Answer 1

首先,要明确一点:列表是一种复合词.

要查看列表是什么,请使用write_canonical/1.例如,使用GNU Prolog:

| ?- write_canonical([1,2,3]).  
'.'(1,'.'(2,'.'(3,[])))

关于记忆中的表现,我推荐Richard O'Keefe的书.系统之间的细节不同,但您可以非常确定row(1,2,3)在内存中表示术语,您需要:

• 一个用于functor/arity的内存单元
• 参数的3个存储单元

对于.(1, .(2, .(3, [])直接内存表示中的术语,您需要:

• 3个存储单元用于三个'.'/2仿函数
• 3个存储单元为1,2,3
• 可能还有一些(例如[]).

从这一点来看,您已经看到使用列表在此表示中至少占用了大约两倍的内存.

您可以自己执行的一些简单测试将帮助您查看系统的这些表示的内存消耗差异.

Answer 2

另一个(优秀的)答案没有提到的东西:

按位置访问列表成员意味着您需要遍历列表.应该可以在固定的时间内访问术语的参数.因此,对于随机访问,术语应该更有效.

简而言之:您可以尝试使列表遍历更快.但是SWI-Prolog实现了nth0_det/3几乎绝望的气味;)

您可能对此主题感兴趣,尤其是 这个摘要讨论了列表和术语等.

遵循一些经验法则.

使用案例:

• 如果你事先知道你有多少东西,请使用一个术语.
• 如果您可以拥有0个或更多相同的东西,请使用列表.
• 如果你需要一个查找表,那么两者都不是最佳选择

效率:

• 如果您想随机访问,请使用术语
• 如果您的算法在单链表上运行良好,Prolog列表是完美的选择.

从最后一点开始:尝试查找使用链表的算法,而不是随机访问数组.它并非总是可行,但对于许多问题,您可以选择.经典的例子是快速排序与合并排序:在Prolog中,合并排序肯定更快.

无论哪种方式,首先要确保你做对,然后担心效率.并确保在开始优化之前测量性能瓶颈.

当然,选择最佳算法和数据结构意味着您需要了解问题和可用工具.与您的问题无关,但过去用于C++的"标准模板库"的优点在于,对于算法和数据结构,时间复杂度("大O表示法")是固有属性,而不是实现细节.