2

我是一名 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))
4

2 回答 2

4

我只看到一个小的改进：

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

可以在任何地方简化为

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

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

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

但是 cons 直接在列表的前面添加了一个 item，就像 function 一样push，所以它就像下面的代码：

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

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

另外，我认为如果你做得更漂亮，它可能会获得更好的性能，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))))
于 2009-07-07T15:00:12.060 回答
1

一般来说，mergesort正在做很多列表操作，所以通过“就地”排序子部分来破坏性地做事情要好得多。您可以在 PLT Scheme中看到一个公共代码的实现sort，它起源于 SLIB。（乍一看可能看起来很吓人，但如果你阅读评论并忽略旋钮和优化，你会在那里看到它。）

此外，您应该查看SRFI-32以获得对排序接口的扩展讨论。

于 2009-07-08T03:50:26.473 回答