修改 lisp 中的快速排序以使用中间评估器过滤器

Question

我正在努力实现使用中间赋值器函数的快速排序；不是测试函数，而是一个赋值器，它替换数字在另一个上下文中表示的间接值。

我在所有情况下都遇到了一些问题，感觉就像碰壁了。我这样做的主要目的是根据距相机的距离对集合中的 3D 三角形进行排序（数组是唯一面的索引之一，评估函数查找给定索引的网格面，然后 returns距相机的距离），但为了简洁起见，我将在下面使用一个更简单的示例。这是 Common Lisp 中的 quicksort-* 代码：

(defun quicksort-* (arr lo hi &key (valuator #'identity))
  (declare (type (simple-array fixnum (*)) arr)
           (type fixnum lo hi)
           (type function valuator))
  (flet ((%partition (arr p r)
           (declare (type (simple-array fixnum (*)) arr)
                    (type fixnum p r))
           (let ((x (funcall valuator (aref arr p)))
                 (i (1- p))
                 (j (1+ r)))
             (loop do
                   (loop do
                         (decf j)
                         until (<= (funcall valuator (aref arr j)) x))
                   (loop do
                         (incf i)
                         until (>= (funcall valuator (aref arr i)) x))
                   (if (< i j)
                       (rotatef (aref arr i) (aref arr j))
                     (return-from %partition j))))))
    (when (< lo hi)
      (let ((p (%partition arr lo hi)))
        (quicksort arr lo p)
        (quicksort arr (1+ p) hi))))
  arr)

那么这到底会做什么？

给出

(defparameter *names* #("Earl" "Dudley" "Chuck" "Bob" "Alice"))

以及我们要排序的列表，目前随机打乱为

(defparameter *nameindices* '(2 4 0 1 3))

运行 quicksort-* on nameindices with a predicate function 'namevaluator':

(defun namevaluator (nameindex)
   (let ((sortednames (sort (copy-seq *names*) #'string>)))
      (position (aref *names* nameindex) sortednames :test #'string=)))

这样应该产生 #(4 3 2 1 0) 来反映降序排序的名称，对吗？

CL-USER> (quicksort
           *nameindices*
            0 (1- (length *nameindices*))
            :valuator
            #'namevaluator)
#(0 1 2 3 4)

嗯，不。但是，嘿，至少它仍然是排序的，即使是相反的。

当然，在 namevaluator 函数中将 #'string> 更改为 #'string< 应该会产生 #(4 3 2 1 0)，对吧？嗯...不，这就是答案：

#(1 2 3 4 0)

翻转 %partition 函数中的 >= 和 <= 符号并没有产生更好的效果（而且这可能不是一个太热门的想法）；它仍然会导致一个结果被排序，而另一个结果乱序。

我想在 %partition 中插入一个函数调用谓词测试，它最初只是简单地评估普通整数值以进行比较，结果会很简单 'Just Worked'。实际上，使用默认的#'IDENTITY 函数作为赋值器，它确实：

(let ((random-numbers (coerce (loop repeat 30 collect (random 1000)) 'vector)))
   (quicksort-* random-numbers 0 (1- (length random-numbers))))

> #(29 91 121 130 191 228 250 382 392 406 443 468 468 480 535 555 576 597 598 604 635 646 646 685 712 721 724 764 849 860)

也许答案就在我眼皮底下，只是我没看到？

Answer 1

(a) 在递归调用函数的地方使用名称 quicksort，但函数的名称是 quicksort-*。我错过了什么吗？

(b) 您在顶级调用中传递了自定义求值器，但在递归调用中没有这样做，因此对于那些 #'identity 是有效的。您可以尝试使用标签函数进行递归，这样您就不必费力地重述 :valuator.

修改 lisp 中的快速排序以使用中间评估器过滤器

modifying quicksort in lisp to use an intermediate valuator filter

sorting

common-lisp

quicksort