可以简化此功能(使其更“快速")吗? [英] Can this function be simplified (made more "fast")?

问题描述

我想知道这是否是该功能最快的版本.

I was wondering if this is the fastest possible version of this function.

(defun foo (x y)
  (cond 
   ;if x = 0, return y+1
   ((zp x) (+ 1 y)) 
   ;if y = 0, return foo on decrement x and 1
   ((zp y) (foo (- x 1) 1)) 
   ;else run foo on decrement x and y = (foo x (- y 1))
   (t (foo (- x 1) (foo x (- y 1)))))) 

运行此命令时，通常会出现堆栈溢出错误，因此我试图找出一种无需使用计算机即可计算(foo 3 1000000)之类的方法.

When I run this, I usually get stack overflow error, so I am trying to figure out a way to compute something like (foo 3 1000000) without using the computer.

通过分析该函数，我认为它是在递归情况下嵌入foo的，从而导致(foo 3 1000000)溢出.但是由于您要递减y，步数是否等于y?

From analyzing the function I think it is embedded foo in the recursive case that causes the overflow in (foo 3 1000000). But since you are decrementing y would the number of steps just equal y?

从评论中删除了谎言

推荐答案

12年前，我这样写:

12 years ago I wrote this:

(defun ackermann (m n)
  (declare (fixnum m n) (optimize (speed 3) (safety 0)))
  (let ((memo (make-hash-table :test #'equal))
        (ncal 0) (nhit 0))
    (labels ((ack (aa bb)
               (incf ncal)
               (cond ((zerop aa) (1+ bb))
                     ((= 1 aa) (+ 2 bb))
                     ((= 2 aa) (+ 3 (* 2 bb)))
                     ((= 3 aa) (- (ash 1 (+ 3 bb)) 3))
                     ((let* ((key (cons aa bb))
                             (val (gethash key memo)))
                        (cond (val (incf nhit) val)
                              (t (setq val (if (zerop bb)
                                               (ack (1- aa) 1)
                                               (ack (1- aa) (ack aa (1- bb)))))
                                 (setf (gethash key memo) val)
                                 val)))))))
      (let ((ret (ack m n)))
        (format t "A(~d,~d)=~:d (~:d calls, ~:d cache hits)~%"
                m n ret ncal nhit)
        (values ret memo)))))

如您所见，我对小a使用显式公式，对大a使用备忘录.

As you can see, I am using an explicit formula for small a and memoization for larger a.

但是，请注意，此函数的增长速度如此之快，以至于试图计算实际值几乎没有任何意义.您会更快地用完宇宙中的原子-还是没有记忆.

Note, however, that this function grows so fast that it makes little sense to try to compute the actual values; you will run out of atoms in the universe faster - memoization or not.

这篇关于可以简化此功能(使其更“快速")吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！