具有更高级别功能的 lisp 中的二进制搜索

Question

我正在尝试编写一个（高阶函数），它接受一个向量和一个函数，并根据该函数进行二进制搜索，即如果它 returns -1，我们需要降低，对于 1 -- 更高，对于 0 我们找到了正确的位置。我想到了这样的东西，但似乎我在将函数作为参数传递时做错了：

(defun bin-search (ls fpred)
 (let ((l (length ls))
       (x (aref ls (floor (length ls) 2))))
       (labels (binsearch (ls fpred l m)
                (case (funcall #'fpred (aref ls m))
                 (-1 (binsearch (ls fpred l (floor (- m l) 2))))
                 (0 (return-from binsearch m))
                 (1 (binsearch (ls fpred m (+ m (floor (- m l) 2)))))))
 (binsearch ls fpred 0 l))))

编译器说变量 FPRED 已定义但从未使用过。怎么了？

Answer 1

(defun bin-search (ls fpred)

请使用有意义的名称，您有很多短名称或缩写，难以阅读。例如，ls 让我想到了一个列表，它可以简单地命名为 list，但显然你正在使用矢量，所以也许 vec 或 vector?

 (let ((l (length ls))
       (x (aref ls (floor (length ls) 2))))

如果要重用同一个let中定义的长度l，可以用let*代替，写l代替第二次出现的[=23] =].

       (labels (binsearch (ls fpred l m)

标签的语法是 list 绑定 (name (<args>) <body>)，因此您需要添加另一对括号，例如 (labels ((binsearch (<args>) <body>)) ...

此外，您不需要将 fpred 作为参数传递，它不会从一次调用 binsearch 更改为另一次调用。您可以从本地函数中引用 bin-search 的 fpred 参数。

                (case (funcall #'fpred (aref ls m))

当你写 #'fpred 时，相当于 (function fpred)，你在 函数命名空间 中寻找 fpred。此处您想要访问与名为 fpred 的变量关联的函数，因此您可以删除 #' 部分。

                 (-1 (binsearch (ls fpred l (floor (- m l) 2))))

当你写 (binsearch (ls fpred ...)) 时，这意味着：用一个值调用 binsearch，这个值是通过调用函数 ls 和参数 fpred 获得的，...... ..。括号很重要，这里需要去掉。

                 (0 (return-from binsearch m))
                 (1 (binsearch (ls fpred m (+ m (floor (- m l) 2)))))))
 (binsearch ls fpred 0 l))))

Answer 2

已修复（据说）所有内容，现在可以使用了。非常感谢。

(defun bin-search (vec fpred)
 (let* ((l (length vec)))
  (labels ((binsearch (vec l m)
            (case (funcall fpred (aref vec m))
             (-1 (binsearch vec  l (+ l (floor (- m l) 2))))
             (0 (return-from binsearch m))
             (1 (binsearch vec m (+ m (floor (- m l) 2)))))))
     (binsearch vec 0 (floor l 2)))))

改善：

let 而不是 let*
内部函数的名称已更改
return-from不需要

已申请：

(defun bin-search (vec fpred)
  (let ((l (length vec)))
    (labels ((bin-search-aux (vec l m)
               (case (funcall fpred (aref vec m))
                 (-1 (bin-search-aux vec l (+ l (floor (- m l) 2))))
                 ( 0 m)
                 ( 1 (bin-search-aux vec m (+ m (floor (- m l) 2)))))))
      (bin-search-aux vec 0 (floor l 2)))))

let 替换为 &aux arg -> 减少一级缩进
vec不需要传

已申请：

(defun bin-search (vec fpred &aux (l (length vec)))
  (labels ((bin-search-aux (l m)
             (case (funcall fpred (aref vec m))
               (-1 (bin-search-aux l (+ l (floor (- m l) 2))))
               ( 0 m)
               ( 1 (bin-search-aux m (+ m (floor (- m l) 2)))))))
    (bin-search-aux 0 (floor l 2)))))

测试：

CL-USER > (bin-search #(1 2 3 4 5 6 7 8 9)
                      (lambda (x)
                        (if (< x 7) 1 (if (> x 7) -1 0))))
6

具有更高级别功能的 lisp 中的二进制搜索

Binary search in lisp with higher level function

lisp

common-lisp

binary-search