代码之家 › 专栏 › 技术社区 › Andrew S.

用高级函数实现lisp中的二元搜索

binary-search common-lisp lisp

1

Andrew S. · 技术社区 · 7 年前

我试着写一个(高阶函数),它取一个向量和一个函数,并根据这个函数进行二元搜索,也就是说,如果它返回-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))))

2 回复 | 直到 7 年前

1

5

coredump 7 年前

(defun bin-search (ls fpred)

请使用有意义的名字,你有许多短名字或缩写,这是很难阅读。例如, ls list ,但显然你在研究向量,所以也许 vec vector ?

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

l 在同一let中定义,可以使用 let* 我 而不是第二次出现 (length ls)

       (labels (binsearch (ls fpred l m)

标签的语法是列表 (name (<args>) <body>) (labels ((binsearch (<args>) <body>)) ...

另外,你不需要通过考试 fpred binsearch 另一个。你可以参考 bin-search 的 fpred公司

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

当你写作的时候 #'fpred ,相当于 (function fpred) ,您正在寻找在 . 在这里,您要访问与变量命名 fpred公司 ,这样你就可以放下 #' 部分。

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

当你写作的时候 (binsearch (ls fpred ...)) ,这意味着: 呼叫 B搜索 长征 带参数 fpred公司 , ...

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

2

1

Rainer Joswig mmmmmm 7 年前

一切都修好了,现在可以用了。谢谢。

(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)))))

让 替换为 &aux
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