Wie dieser mergesort in Schema zu verbessern?

Question

Ich bin ein C ++ Programmierer, schrieb ich den Code zu sehen, ob ich funktionell denken kann :) Für Hinweise, es zu verbessern?

(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

Es gibt nur eine kleine Verbesserung, die ich sehe:

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

kann überall vereinfacht werden

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

Ich glaube, Sie waren wie an etwas gedacht (in Python-artige Syntax):

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

Aber Nachteile fügt ein Element direkt an der Vorderseite einer Liste, wie eine funktionelle push, so dass es wie dem folgenden Code ist:

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

Am Ende der zusätzliche Anfügen führt nur in Doppel cons Zellenzuweisung für jedes Element, so ist es keine große Sache.

Auch ich glaube, Sie könnten eine bessere Leistung, wenn man mergesort schicker gemacht, so dass es die Liste Länge unterhält und sortiert die beiden Hälften der Liste bei jedem Schritt. Dies ist wahrscheinlich nicht geeignet für ein Lernen Beispiel so, though.

So etwas wie:

(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

Im Allgemeinen mergesort wird eine Menge Liste Manipulationen zu tun, so ist es viel besser, Dinge zu tun zerstörend durch Unterteile „in-place“ zu sortieren. Sie können sehen, die Implementierung von sort in PLT Scheme zum Beispiel eines gemeinsamen Code, der in SLIB entstanden. (Es könnte auf den ersten Blick aussehen einschüchternd, aber wenn man die Kommentare lesen und die Knöpfe und die Optimierungen ignorieren, werden Sie sie alle dort sehen.)

Auch sollte man sich SRFI-32 für eine ausführliche Diskussion einer Sortieranlage Schnittstelle.