Comment améliorer ce mergesort dans le schéma?

Question

Je suis un programmeur C++, j'ai écrit ce code pour voir si je peux penser fonctionnellement :) Des conseils pour l'améliorer?

(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

Il n'y a qu'une petite amélioration que je vois:

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

peut partout être simplifié à

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

Je pense que vous pensiez à quelque chose comme (dans la syntaxe Python-esque) :

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

Mais contre ajoute un élément directement à l'avant d'une liste, comme un push, il est donc comme le code suivant fonctionnel:

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

En fin de compte l'append supplémentaire résulte que dans l'allocation de double cellule de contre pour chaque élément, il est donc pas un grand traiter.

En outre, je pense que vous pourriez obtenir de meilleures performances si vous avez fait mergesort colombophile de sorte qu'il conserve la longueur de la liste et trie les deux moitiés de la liste à chaque étape. Ce n'est probablement pas approprié pour un exemple d'apprentissage comme celui-ci, cependant.

Quelque chose comme:

(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

En général, mergesort fait beaucoup de manipulations de la liste, il est donc préférable de faire les choses par le tri des pièces destructivement sous « en place ». Vous pouvez voir le implementation of sort in PLT Scheme par exemple d'un code commun, qui provient de SLIB. (Cela peut sembler intimidant à première vue, mais si vous lisez les commentaires et ignorez les boutons et les optimisations, vous verrez tout.)

De plus, vous devriez regarder SRFI-32 pour une discussion étendue d'un tri interface.