algorithm - 无休止地添加到 lisp 中的合并排序列表

Question

这是我在 lisp 中运行合并排序程序时发生的情况。

(MSORT '(1 2 3 4 5 6 7 8 9))

“堆栈溢出(深)”。

我很确定我经常用我的函数添加到列表中，但我不知道如何修复它。

(defun fhl(l) 
    (progn
            (setf msize (mod (length l) 2));; mod for size even check
            (setf size (- (/ (length l) 2) 1));;size of list -1 because we start on pos 1 in list
            (setf f (list (car l)));;size of list -1 because we start on pos 1 in list

            (if (eq msize 1) (setf size (+(floor size)1)));;if mod = 1 list is odd - .5 to round to whole number + 1 for more even spread
            (dotimes (i size) 
                    (setf f (append f (list (nth (+ i 1) l)))));; add next element in list size times
     f));;return new list


(defun shl(l)
    (progn
            (setf msize (mod (length l) 2));; mod for size even check
            (setf size  (/ (length l) 2));;size of list -1 because we start on pos 1 in list
            (if (eq msize 1) (setf size (+(floor size) 1)));;if mod = 1 list is odd - .5 to round to whole number + 1 for more even spread

            (dotimes (i size) ;; loop for i items 
                    (setf l (cdr l)))
     l))


(defun msort(l) 
            (if (null l)
                    '();;empty list
            )
            (if (= (length l) 1) l);;1 item
                    (progn
                            (setf f (fhl l))
                            (setf s (shl l))
                            (merge 'list (msort f) (msort s) #'<)

                    )

)

Answer 1

您的MSORT-函数具有三种主体形式:

(defun msort (l)
  (if ...)
  (if ...)
  (progn ...))

由于函数返回最后一个形式的值，所以两个 IF 实际上不做任何事情。它们的值只是被丢弃，PROGN 的值总是被返回。

要解决此问题，您应该使用 COND。正如评论中提到的那样，您还应该使用 LET 来定义局部变量。

(defun msort (l)
  (cond ((null l) '())
        ((= (length l) 1) l)
        (t (let ((f (fhl l))
                 (s (shl l)))
             (merge 'list (msort f) (msort s) #'<)))))

此外，我必须说函数 FHL 和 SHL 的命名非常糟糕。阅读代码的人应该能够理解函数的用途，而无需阅读其代码。我假设它们分别是“first half list”和“second half list”的首字母缩写词，因此您应该只使用这些名称。在 Common Lisp 中，通常更喜欢使用完整的单词作为名称(这也适用于变量)。

将两个函数用于拆分列表的任务也很糟糕，因为这两个函数依赖于另一个关于如何处理奇数列表长度的实现细节。最好将它们合并为一个功能。一个简单的实现是只使用一个 LOOP:

(defun split-list (list)
  "Split LIST into two halves. Returns a cons containing the halves."
  (loop with mid-point = (floor (length list) 2)
        for element in list
        for i from 0
        if (< i mid-point) collect element into first-half
          else collect element into second-half
        finally (return (cons first-half
                              second-half))))

这将返回一个 cons-cell 中的两半。然后，您可以使用 DESTRUCTURING-BIND 将它们绑定(bind)到 MSORT 中的变量中。您还可以使用 VALUES 将它们作为多个值返回，并使用 MULTIPLE-VALUE-BIND 来绑定(bind)它们，但我认为cons-cell(或列表)更好对于这种情况，因为不太可能有人只想要一半。

(defun mergesort (list)
  "Sort LIST using Mergesort-algorithm."
  (cond ((null list) '())
        ((= (length list) 1) list)
        (t (destructuring-bind (first-half . second-half) (split-list list)
             (merge 'list
                    (mergesort first-half)
                    (mergesort second-half)
                    #'<)))))