如何改进这个mergesort的方案？

我是一名C++程序员，我写了这段代码，看看我能否在功能上思考:) 有没有什么提示可以改进它？如何改进这个mergesort的方案？

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

来源

2009-07-07 AraK

它看起来很标准:)这是另一个版本：https：//ironscheme.svn.codeplex.com/svn/IronScheme/IronScheme.Console/build/sorting.ss – leppie 2009-07-07 06:59:08

哦，谢谢，我会采取看看IronScheme :) – AraK 2009-07-07 09:07:03

我冒昧地设计你的代码。 – Svante 2009-07-07 09:21:35

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

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

到处都可以简化为

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

我想自己所想的东西一样（在Python式的语法）：

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

但是利弊直接添加项目到列表的前面，就像一个功能push，所以它就像下面的代码：

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

最终额外追加只会导致双cons单元分配每个项目，所以它不是一个大应对。

另外，我认为如果您制作mergesort fancier，那么它可能会获得更好的性能，因此它可以保持列表长度并在每个步骤中对列表的两半进行排序。不过，这可能不适合这样的学习示例。

喜欢的东西：

(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-07 15:00:12

一般来说，mergesort是做了很多的列表操作，因此它是好得多破坏性做事情的“就地”排序子部分。例如，你可以看到implementation of sort in PLT Scheme的例子是一个源于SLIB的公共代码。（它可能看起来很吓人，但如果您阅读了评论并忽略了旋钮和优化，您将在此处看到它。）

另外，您应该查看SRFI-32以了解排序的扩展讨论接口。

来源

2009-07-08 03:50:26

如何改进这个mergesort的方案？

回答

相关问题