gpt4 book ai didi

coding-style - 如何删除 Lisp 代码中的冗余?

转载 作者:太空宇宙 更新时间:2023-11-03 18:36:04 26 4
gpt4 key购买 nike

我试图在 Common Lisp 中实现快速排序,这是我目前所得到的:

(defun quick-sort (list)
(if (cdr list)
(let ((pivot (car list)))
(append (quick-sort (remove-if-not (lambda (n) (< n pivot)) list))
(remove-if-not (lambda (n) (= n pivot)) list)
(quick-sort (remove-if-not (lambda (n) (> n pivot)) list))))
list))

显然它有效,但我认为该代码中有太多重复。基本上,我们有 3 次:

(remove-if-not (lambda (n) (< n pivot)) list)

这三个调用的唯一不同之处在于 >对比=对比< .

因此我的问题是:如何去除冗余并使代码更易读、更紧凑?

当然我可以把东西提取到一个函数中,比如:

(defun which (operator pivot list )
(remove-if-not (lambda (n) (funcall operator n pivot)) list))

(defun quick-sort (list)
(if (cdr list)
(let ((pivot (car list)))
(append (quick-sort (which #'< pivot list))
(which #'= pivot list)
(quick-sort (which #'> pivot list))))
list))

但不知何故,我不太确定这是否是最佳方法。交出来还是觉得笨手笨脚pivotlist一次又一次。

我也有使用 flet 的想法,这使得函数的实际主体更具可读性,但只会将复杂性转移到其他地方:

(defun quick-sort (list)
(if (cdr list)
(let ((pivot (car list)))
(flet ((left () (remove-if-not (lambda (n) (< n pivot)) list))
(middle () (remove-if-not (lambda (n) (= n pivot)) list))
(right () (remove-if-not (lambda (n) (> n pivot)) list)))
(append (quick-sort (left))
(middle)
(quick-sort (right)))))
list))

还有其他方法吗?

最佳答案

如果将其编写为本地函数,则不必传递额外的参数,因为它们在范围内。

(defun quick-sort (list)
(if (rest list)
(let ((pivot (first list)))
(flet ((filter (operator)
(remove-if-not (lambda (n) (funcall operator n pivot)) list)))
(append (quick-sort (filter #'<))
(filter #'=)
(quick-sort (filter #'>)))))
list))

稍微紧凑一点的版本:

(defun quick-sort (list &aux (pivot (first list)))
(flet ((filter (operator)
(remove-if-not (lambda (n) (funcall operator n pivot)) list)))
(and list
(nconc (quick-sort (filter #'<))
(filter #'=)
(quick-sort (filter #'>))))))

由于 Common Lisp 支持多值,您也可以一次性将列表划分为一个函数并将列表作为值返回:

(defun partition (list pivot)
(loop for e in list
when (< e pivot) collect e into smaller else
when (> e pivot) collect e into larger else
when (= e pivot) collect e into same
finally (return (values smaller same larger))))

(defun quick-sort (list)
(if (rest list)
(multiple-value-bind (smaller same larger)
(partition list (first list))
(append (quick-sort smaller) same (quick-sort larger)))
list))

当新分配列表时,NCONC 是可能的。由于 REMOVE-IF-NOT 是非破坏性的(与 DELETE-IF-NOT 相比),NCONC 没问题。由于 LOOP 收集新列表,NCONC 再次正常。

这是对向量的实际简单就地快速排序。请注意,Quicksort 实际上就是这个意思。使用列表的版本并不是真正的快速排序。

(defun partition (array left right &aux (i (1- left))
(j right)
(v (aref array right)))
(loop do (loop do (incf i) until (>= (aref array i) v))
(loop do (decf j) until (or (zerop j)
(<= (aref array j) v)))
(rotatef (aref array i) (aref array j))
until (<= j i))
(rotatef (aref array j) (aref array i) (aref array right))
i)

(defun quicksort (array &optional (left 0) (right (1- (length array))))
(if (> right left)
(let ((i (partition array left right)))
(quicksort array left (1- i))
(quicksort array (1+ i) right))
array))

此版本基于 Sedgewick 的代码。

关于coding-style - 如何删除 Lisp 代码中的冗余?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34909372/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com