LISP检查列表是否对称而没有反向

Question

任何人都有任何想法如何这样做...反向太慢,我想避免使用该功能.

基本上我希望能够在'(abba)出现或'(abcdcba)之类的情况下返回true

对于不对称的东西是假的

Answer 1

我不确定为什么使用REVERSE效率不高; 你有没有找到解决方案？您只需遍历列表一次即可完成; 与(比如)查找列表的长度相同,然后您可以遍历两个列表进行比较.

如果你想成为一个小小的爱好者,你可以同时找到列表的长度并使用它反转它LOOP:

(defun fancier-palindrome-p (list)
  (let ((reversed '()) (length 0)) 
    (dolist (elt list)
      (incf length)
      (push elt reversed)) 
    (dotimes (i (floor length 2) t)
      (unless (eql (pop list) (pop reversed))
        (return nil))))) 

这允许您跳过一半检查.我认为这不值得额外的复杂性.您还可以使用乌龟和兔子在列表中向下移动以节省一半的费用,但代价是更复杂.

 (defun ridiculous-palindrome-p (list)
   (let ((reversed-front '()))
     (loop  
       :for tortoise :on list 
       :for hare :on list :by #'cddr 
       :until (null (cdr hare)) 
         :do (push (car tortoise) reversed-front)
       :finally  
         (return  
          (if (null hare) ; length is even 
            (equal tortoise reversed-front)
            (equal (cdr tortoise)  
                   reversed-front)))))) 

这些解决方案都没有比我更引人注目

(defun palindrome-p (list) (equal list (reverse list))

如果这确实是一个瓶颈,也许你最好使用向量作为序列表示来利用快速随机访问,如下所示:

(defun vector-palindrome-p (vector)
  (let* ((n (length vector)) (j n))
    (dotimes (i (floor n 2) (return t))
      (unless (eql (aref vector i) 
                   (aref vector (decf j)))
      (return nil)))))