(Guile)Scheme的逆向函数效率如何

Question

使用 Scheme 的 reverse 函数非常容易，例如在使用 (cons new-obj my-list) 而不是 (append my-list (list new-obj)) 创建一个相反顺序的列表之后。

但是，我想知道部分的效率如何。如果一个 Scheme 列表是一个 singly 链表（正如我假设的那样），这意味着遍历整个列表至少一次以到达最后一个元素，不是吗？这需要 reverse 以某种方式创建反向链接？

双向链表中的 OTOH 只需简单地从末尾遍历列表到开头，这样会更有效率。

我的问题是：如果我有这样一种情况，程序生成一个列表（以相反的顺序）并且在某个时候处理整个列表是否值得以它可以处理列表的方式实现该处理以相反的顺序，还是先简单地使用 reverse 就不会受到惩罚？

这是针对 Guile Scheme，具体来说是 Guile 1.8（如果它有所不同）。

Answer 1

将使用内置的reverse过程作为惩罚，时间复杂度为O(n)，时间复杂度为O(1) space 复杂度，看起来与此类似（是的，我们必须遍历列表直到最后，沿途创建反向链接）：

(define (reverse lst)
  (let loop ((lst lst) (acc '()))
    (if (null? lst)
        acc
        ; notice the tail recursion!
        (loop (cdr lst) (cons (car lst) acc)))))

另一方面，我不会太担心它，除非您正在操作的列表非常庞大，并且您的探查器表明 reverse 过程是一个瓶颈。

只需使用内置函数来简化您的代码 - 组合现有函数是函数式编程所鼓励的风格。在 Scheme 中，我们尝试以 tail-recursive 的方式处理列表，即使这意味着反向创建列表并且我们需要在最后调用 reverse，这是完全可以接受的。

Answer 2

想象一下简单的复制功能：

(define (copy1 lst)
  (let loop ((lst lst) (acc '()))
    (if (null? lst)
        (reverse acc)
        (loop (cdr lst) (cons (car lst) acc)))))

与使用追加的对比：

(define (copy2 lst)
  (let loop ((lst lst) (acc '()))
    (if (null? lst)
        acc
        (loop (cdr lst) (append acc (list (car lst)))))))

append和reverse都是O(n)，这意味着它们遍历了整个列表。 copy 的两个版本之间的区别在于带有 reverse 的版本在末尾对所有元素执行一次，而 append 版本为每个元素调用 append。这使得最后一个版本的复杂度为 O(n*n)，并且比第一个版本的复杂度 O(n) 效率低得多。如果列表很大，您很快就会注意到这种差异。

现在回答你的问题。您应该使用针对您的任务优化的数据类型。如果您总是制作一个列表，然后将其附加到末尾，则反向执行列表中的所有工作并等待 reverse 直到您需要它。您甚至可以围绕它进行抽象。

Answer 3

反转需要 O(n) 时间来创建 n 长的反转列表，因此需要 O( n) space 还有。您只需遍历原始列表一次即可反转它。

如果不再使用原始列表，它可能会被垃圾收集（什么时候？成为问题）并回收其内存，整体理论上 O(1) space成本；但是垃圾收集有其自身的成本。

所以，进行测试，如果您的列表很长并且您看到正在进行大量垃圾收集，请按照您的建议进行操作。它将或多或少地减少一半的时间和 space 要求（在代码库的那一部分）。

但是，如果列表构建和反转占用了您总时间的 0.0001% 和 space，将其减半不会有如此巨大的改进。

顺便说一下，单链表中没有反向链接。通过重复 consing.

(Guile)Scheme的逆向函数效率如何

How efficient is (Guile) Scheme's reverse function

scheme

guile

linked-list