list - 关于列表：Erlang 中的后缀/2

Question

源代码：

suffix(Suffix, List) ->
    Delta = length(List) - length(Suffix),
    Delta >= 0 andalso nthtail(Delta, List) =:= Suffix.

像下面这样重写它怎么样：

suffix(Suffix, List) ->
    prefix(reverse(Suffix), reverse(List)).

如果Delta >=0，第一个遍历4次，第二个遍历3次，对吗？

Answer 1

第一个（来自stdlib lists.erl）将遍历两个列表两次，是的。另一方面，在第二次遍历时，所有列表单元可能都在 L2 缓存中，并且它不必分配任何数据。您的建议也有效，但必须在堆上构建两个反向临时列表，这在分配和初始化数据结构方面都有成本，并且平均会导致垃圾收集更频繁地发生。

如果您在 C（或任何类似语言）中考虑相同的问题：测试一个单链表是否是另一个单链表的后缀，那么为什么很难有效地完成它变得更加明显，特别是如果您想避免分配内存，并且不允许使用反转指针之类的技巧。

Answer 2

我不认为这是正确的。据我所知，length是一个内置函数，不需要遍历列表即可获得结果（这也是警卫测试中允许它的原因），andalso是一种快捷方式。如果第一项为假，则不评估第二项并直接返回假。