lisp中的Quicksort显示lambda函数错误

Question

我为quicksort编写了以下代码,与C代码非常相似.但是在这里它只读取list的元素.之后它说分区函数应该是lambda函数.我是lisp的新手.请帮帮我.我的代码是: -

(print "Enter the elements of the array")
(setq k 10)
(setq A (make-array '(10)))
(setq i 0)
(loop
    (if (>= i 10) (return))
    (setq x (read))
    (setf (aref A i) x)
    (incf i)
)

 (defun quicksort(start end)
 (if (< start end)
    ((setq pindex (lambda (start end)))
    (quicksort(start (- pindex 1)))
    (quicksort((+ pindex 1) end))))
  )
(defun partition(start end)
(setq pivot (aref A end))
(setq pindex start)
(setq j 0)
(loop
    (if (>= j end) return)
    (if (< (aref A j) pivot)
        ((setq temp (aref A pindex))
        (setq pindex (aref A j))
        (setq (aref A j) temp)
        (incf pindex)))
    (incf j)
)
(setq temp (aref A pindex))
(setq (aref A pindex) pivot)
(setq (aref A end) temp)
)
(quicksort 0 10)

并且想知道这个lambda函数是什么.它是否仅仅是一个尚未定义的函数的匿名名称

Answer 1

我会一步一步地做这件事.首先,使用标准格式:

(print "Enter the elements of the array")
(setq k 10)
(setq A (make-array '(10)))
(setq i 0)
(loop
  (if (>= i 10) (return))
  (setq x (read))
  (setf (aref A i) x)
  (incf i))

(defun quicksort (start end)
  (if (< start end)
      ((setq pindex (lambda (start end)))
       (quicksort(start (- pindex 1)))
       (quicksort((+ pindex 1) end)))))

(defun partition (start end)
  (setq pivot (aref A end))
  (setq pindex start)
  (setq j 0)
  (loop
    (if (>= j end) return)
    (if (< (aref A j) pivot)
        ((setq temp (aref A pindex))
         (setq pindex (aref A j))
         (setq (aref A j) temp)
         (incf pindex)))
    (incf j))
  (setq temp (aref A pindex))
  (setq (aref A pindex) pivot)
  (setq (aref A end) temp))

(quicksort 0 10)

解决当前的问题:括号总是包围表单,它们不会自己对表单进行分组.

(print "Enter the elements of the array")
(setq k 10)
(setq A (make-array '(10)))
(setq i 0)
(loop
  (if (>= i 10) (return))
  (setq x (read))
  (setf (aref A i) x)
  (incf i))

(defun quicksort (start end)
  (if (< start end)
      (progn
        (setq pindex (lambda (start end)))
        (quicksort(start (- pindex 1)))
        (quicksort((+ pindex 1) end)))))

(defun partition (start end)
  (setq pivot (aref A end))
  (setq pindex start)
  (setq j 0)
  (loop
    (if (>= j end) return)
    (if (< (aref A j) pivot)
        (progn
          (setq temp (aref A pindex))
          (setq pindex (aref A j))
          (setq (aref A j) temp)
          (incf pindex)))
    (incf j))
  (setq temp (aref A pindex))
  (setq (aref A pindex) pivot)
  (setq (aref A end) temp))

(quicksort 0 10)

一些错误,一行一行:

(print "Enter the elements of the array")
(setq k 10)                                 ; warning: no variable K
(setq A (make-array '(10)))                 ; warning: no variable A
(setq i 0)                                  ; warning: no variable I
(loop
  (if (>= i 10) (return))
  (setq x (read))
  (setf (aref A i) x)
  (incf i))                                 ; warning: k never used

(defun quicksort (start end)
  (if (< start end)
      (progn
        (setq pindex (lambda (start end)))  ; this lambda always returns nil
        (quicksort (start (- pindex 1)))    ; START is not a function
        (quicksort ((+ pindex 1) end)))))   ; (+ PINDEX 1) is not a function

(defun partition (start end)
  (setq pivot (aref A end))                 ; warning: no variable PIVOT
  (setq pindex start)                       ; warning: no variable PINDEX
  (setq j 0)                                ; warning: no variable J
  (loop
    (if (>= j end) return)                  ; warning: no variable RETURN
    (if (< (aref A j) pivot)
        (progn
          (setq temp (aref A pindex))       ; warning: no variable TEMP
          (setq pindex (aref A j))
          (setq (aref A j) temp)
          (incf pindex)))
    (incf j))
  (setq temp (aref A pindex))
  (setq (aref A pindex) pivot)
  (setq (aref A end) temp))

(quicksort 0 10)

摆脱"无变量"警告. Setq不引入变量.大多数Common Lisp实现都做了一些有用的事情,这似乎有用,但它是未定义的行为.您可以使用defvar或声明这些变量是全局特殊的defparameter,但是您实际需要的是读取用户输入的函数,您可以使用该函数let进行本地绑定.它还返回读取数组而不是设置全局状态.我还选择使用K作为参数以获得一些灵活性. Finish-output 确保在输入第一个数字之前显示提示.

(defun read-integers (k)
  (print "Enter the elements of the array.")
  (finish-output)
  (let ((a (make-array (list k)))
        (i 0))
    (loop
      (if (>= i k)
          (return))
      (let ((x (read)))
        (setf (aref a i) x)
        (incf i)))
    a))

这仍然留有很大的改进空间,但至少它有效.

下一个:修理quicksort.由于它不使用partition任何地方,但体育空lambda表,我假设你想打电话到partition那里.我还修复了调用表单和缺少绑定:

(defun quicksort (start end)
  (if (< start end)
      (let ((pindex (partition start end)))
        (quicksort start (- pindex 1))
        (quicksort (+ pindex 1) end))))

它在一个全局数组上运行,你在其体内的任何地方都没有看到它.这非常令人困惑,使代码非常难以理解且无法维护.将数组作为参数给出更好,以便将其称为(quicksort (read-integers 10) 0 10).

为了提高性能,我们需要对它进行操作,这很不寻常,应该在docstring中提及.我返回数组,以便可以使用sort的常用语义.没有替代条款的IF更好地写为WHEN.

(defun quicksort (array start end)
  "Destructively sorts ARRAY in place."
  (when (< start end)
    (let ((pindex (partition array start end)))
      (quicksort array start (- pindex 1))
      (quicksort array (+ pindex 1) end)))
  array)

这仍然包含一个一个一个错误,但我partition现在看看.首先,解决通常的绑定问题:

(defun partition (array start end)
  "Chooses an arbitrary pivot element from array between START and END, then
destructively partitions the elements of ARRAY between START and END
in-place into those smaller than the pivot, then the pivot, then those
bigger than the pivot.  Finally returns the index of the pivot."
  ;; FIXME: doesn't work
  (let ((pivot (aref array end))
        (pindex start)
        (j 0))
    (loop
      (if (>= j end) (return))
      (if (< (aref array j) pivot)
          (let ((temp (aref array pindex)))
            (setf pindex (aref array j))
            (setf (aref array j) temp)
            (incf pindex)))
      (incf j))
    (let ((temp (aref array pindex)))
      (setf (aref array pindex) pivot)
      (setf (aref array end) temp))))

这是错的.请查看quicksort的工作原理.

提示:

• 你需要两个索引变量
• 你不应该在START和END之外引用数组的部分
• 提示:使用,而不是通过显式临时位置手动交换 rotatef
• 提示:position-if可能有用.在Hyperspec中查找.
• 提示:单独测试partition.当它工作,修复quicksort.