3

Common Lisp のアルゴリズム クラスですべての割り当てを行うことに挑戦しました。私は Lisp の学習の初日に入りましたが、障害にぶつかりました。

割り当ては、任意のサブセット長に達したときに挿入に変換するマージ ソートを作成することです (Timsort)。挿入セクションは完全に機能しますが、マージの分割部分は、プログラムを 2 回分割する必要がある場合にのみ機能します。Lisp でリストが機能する方法に関係していることはわかっていますが、問題を特定するには新人すぎます。

無限ループにヒットすると思います...デバッグステートメントで実行すると、セットに要素が多すぎると出力されないため、わかりません。

私はここで、特定の回答を求めたり、誰かに私のコードを書いてもらったりすることを懇願しているわけではありません。たぶん、説明や正しい方向へのポイントが大いに役立つでしょう!

私のコード:

;; Insertion sort method call (returns sorted list)
(defun insert-sort (lst) ... )

;; Merge sort method call
(defun merge-sort (lst)
  (print 'Merge)
  (print lst)
  (if (< (length lst) 7) ; Check to see if list is small enough to insert sort
      (insert-sort lst) ; Do so
      (progn ; else
        (setf b (merge-split lst)) ; Split the list, store into b
        (setf (car b) (merge-sort (car b))) ; Merge sort on first half
        ;; --- I think it's happening here ---
        (setf (cdr b) (merge-sort (cdr b))) ; Merge sort on second half
        (merge 'list (car b) (cdr b) #'<)))) ; Merge the two lists together (using API)

;; Split a list into two parts
(defun merge-split (lst)
   (progn
     (setf b lst) ; Set b to first index
     (setf a (cdr lst)) ; Set a to the rest of the list
     (loop while a do ; Loop while a != null
           (setf a (cdr a)) ; Make a equal next list node
           (if a ; If it still exists
               (progn
                 (setf a (cdr a)) ; Inc a again
                 (setf b (cdr b))))) ; Also inc b (b should always be half of a)
     (setf a (cdr b)) ; Set a to the list after b
     (setf (cdr b) NIL) ; Delete link after b
     (cons lst a))) ; Return in a cons

注：これは私が書いたコードで、インターネットから入手したものではありません...おそらくわかりますが、笑

4

1 に答える 1

4

動的スコープの変数に悩まされています。最初に SETF を呼び出して a、b を設定すると、グローバルで動的スコープの変数が暗黙的に作成されます。それらを宣言するには、代わりに LET を使用してください。LET を使用すると、PROGN と同様に、実行する式のリストを含めることができるため、2 つの PROGN を LET に変更することでこれを修正できるというのが私のヒントです。立ち往生するためにこれ以上必要な場合はお知らせください。

于 2012-01-26T01:05:31.113 に答える