CODEWITHSUNDEEP
performancerecursionlispcommon-lisp
justBecca
justBecca

Reputation: 133

(Lisp) Can i make this more efficient?

Doing a count the change style problem and i wrote this recursive in lisp, i was wondering if anyone had any tips for making this more efficient? if the numbers get too big, its just starts to break and takes about 3 minutes to compute the equivalent of £10 of different combinations! Even pointing me in the right direction would be good, thanks!

(defun dollars (amount &optional (coins '(5 10 20 50 100 200 500 1000 2000 5000 10000)))
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= (length coins) 0) (> amount 30000)) 0)          
        ((zerop (mod amount 5))
         (+ (dollars (- amount (first coins)) coins)
            (dollars amount (rest coins))))))

Upvotes: 3

Views: 170

Answers (1)

malisper
malisper

Reputation: 1671

Let's look at a similar problem, calculating Fibonacci numbers.

(defun fib (n)
  (if (<= 0 n 1)
      n
      (+ (fib (- n 1))
         (fib (- n 2)))))

As n gets larger, the number of times the smaller Fibonacci numbers are calculated grows exponentially. In calculating F(10), F(5) is calculated a total of eight different times. In calculating F(15), F(5) is calculated a total of 89 different times! We can fix this problem by saving a value after we calculate it. Then, when we need to determine a value we have already calculated, just look it up. The following code does that.

(defparameter *calculated* (make-hash-table))

(defun fib (n)
  (or (gethash n *calculated*)
      (setf (gethash n *calculated*)
            (if (<= 0 n 1)
                n
                (+ (fib (- n 1))
                   (fib (- n 2)))))))

When given a number to calculate, if the code has already calculated it, it looks up its value, otherwise the code will calculate the value and store it. Now when we calculate F(15), F(5) is only calculated once since every other time it's value is just looked up in the hash-table. This gives a dramatic speedup since every Fibonacci number (from F(0) to F(15)) is only calculated once.

This is a technique called "dynamic programming", in which larger values are calculated from smaller values and the smaller values are calculated over and over again. The simple solution is to just store a value whenever it is calculated and check if a value has already been calculated. It should be straightforward to how you can apply this technique to your own code.

Upvotes: 6

Related Questions