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

私が見る小さな改善点は1つだけです。

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

どこでも簡略化できます

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

あなたは（Python風の構文で）次のようなことを考えていたと思います：

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

しかし cons は、 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は多くのリスト操作を行っているため、サブ パーツを「その場で」並べ替えて破壊的に行う方がはるかに優れています。SLIB に由来する一般的なコードの例として、PLT スキームでの実装をsort見ることができます。(一見威圧的に見えるかもしれませんが、コメントを読んでノブや最適化を無視すると、そこにすべてが表示されます。)

また、並べ替えインターフェイスの詳細については、SRFI-32を参照してください。

于 2009-07-08T03:50:26.473 に答える