Распространение слияний Common Lisp - PullRequest
Новая
       23

Распространение слияний Common Lisp

3 голосов
/ 26 января 2012

Я поставил перед собой задачу выполнить все задания в своем классе алгоритмов в Common Lisp.Я в первый день изучения lisp и столкнулся с препятствием.

Задача - создать сортировку слиянием, которая преобразуется в вставку при достижении произвольной длины подмножества (Timsort).Секция вставки работает отлично, но разделенная часть слияния работает только тогда, когда программа должна разделиться дважды.Я знаю, что это связано с тем, как списки работают в 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

Примечание: это код, который я написал, а не получил из Интернета ..Вы, наверное, можете сказать, хотя ха-ха

1 Ответ

4 голосов
/ 26 января 2012

Вас укушают динамические переменные.При первом вызове SETF для установки a, b вы неявно создаете глобальные переменные с динамической областью действия.Вместо этого используйте LET, чтобы объявить их.LET позволяет вам включить список выражений для выполнения, как PROGN, так что я подсказываю, что вы можете исправить это, изменив 2 PROGN в LET.Дайте мне знать, если вам нужно больше, чем это, чтобы отклеиться.

...