如何改进方案中的这种归并排序？

Question

我是一名 C++ 程序员，我写这段代码是为了看看我是否可以进行函数式思考:) 有什么改进的提示吗？

(define (append listOne listTwo)
  (cond
    ((null? listOne) listTwo)
    (else (cons (car listOne) (append (cdr listOne) listTwo)))))

(define (merge listOne listTwo)
  (cond
    ((null? listOne) listTwo)
    ((null? listTwo) listOne)
    ((< (car listOne) (car listTwo))
     (append (cons (car listOne) '())
             (merge (cdr listOne) listTwo)))
    ((= (car listOne) (car listTwo))
     (append (cons (car listOne) '())
             (merge (cdr listOne) listTwo)))
    (else (append (cons (car listTwo) '())
                  (merge listOne (cdr listTwo))))))

(define (mergesort lis)
  (cond
    ((null? lis) '())
    ((null? (cdr lis)) lis)
    (else (merge (cons (car lis) '())
                 (mergesort (cdr lis))))))

(mergesort '(99 77 88 66 44 55 33 11 22 0))

Answer 1

我看到的只有一个小改进：

(append (cons (car listTwo) '())
              (merge listOne (cdr listTwo))))

可以在任何地方简化为

(cons (car listTwo)
      (merge listOne (cdr listTwo)))

我认为你正在考虑类似的东西（用Python式的语法）：

[car(listTwo)] + merge(listOne, cdr(listTwo))

但是cons将一个项目直接添加到列表的前面，就像一个函数push，所以就像下面的代码：

push(car(listTwo), merge(listOne, cdr(listTwo)))

最终，额外的附加只会导致每个项目的双 con 单元分配，所以这不是什么大问题。

另外，我认为如果您使 mergesort 更加精美，以便它保持列表长度并在每一步对列表的两半进行排序，您可能会获得更好的性能。 不过，这可能不适合这样的学习示例。

就像是：

(define (mergesort l)
  (let sort-loop ((l l) (len (length l)))
    (cond
      ((null? l) '())
      ((null? (cdr l)) l)
      (else (merge (sort-loop (take (/ len 2) l) (/ len 2)))
                   (sort-loop (drop (/ len 2) l) (/ len 2)))))))))
(define (take n l)
  (if (= n 0)
      '()
      (cons (car l) (take (sub1 n) (cdr l)))))
(define (drop n l)
  (if (= n 0)
      l
      (drop (sub1 n) (cdr l))))

Answer 2

一般来说，mergesort 会进行大量的列表操作，因此最好通过“就地”对子部分进行排序来进行破坏性的操作。 您可以查看sort的实现是起源于 SLIB 的通用代码的示例。 （乍一看可能有点吓人，但如果您阅读评论并忽略旋钮和优化，您就会在那里看到所有内容。）

此外，您应该查看 SRFI-32 有关排序接口的扩展讨论。