algorithm - 如何改进方案中的合并排序？

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

最终，额外的追加只会导致每个项目的双重 cons 单元分配，所以这没什么大不了的。

此外，我认为如果您使 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))))