Today, I am going to write a common lisp function that returns the entries in Catalan’s Triangle. The description is an easy recursive function: \(C(n,k) = 0\) when \(n<1\), or \(k<1\), or \(n<k\). And we have \[ C(n,k) = C(n-1,k) + C(n,k-1) \] otherwise. The base case is \(C(1,1)=1\).
If we were to implement this without memoization it would be very expansive to calculate the values of this function.
(defun dumb (n k)
(cond ((or (< n 1) (< k 1) (< n k)) 0)
((= k 1) 1)
(t (+ (dumb (1- n) k)
(dumb n (1- k))))))DUMBLet me test:
(time (loop for i from 1 to 12 collect (dumb 12 i)))Evaluation took:
0.008 seconds of real time
0.008000 seconds of total run time (0.008000 user, 0.000000 system)
100.00% CPU
20,438,732 processor cycles
0 bytes consed
(1 11 65 273 910 2548 6188 13260 25194 41990 58786 58786)So, I am going to re-implement it using a simple memoization trick:
(let ((table (make-hash-table :test #'equal)))
(defun catalan (n k)
(cond ((or (< n 1) (< k 1) (< n k)) 0)
((= k 1) 1)
(t (or (gethash (list n k) table)
(setf (gethash (list n k) table)
(+ (catalan (1- n) k)
(catalan n (1- k)))))))))CATALANLet us test:
(time (loop for i from 1 to 12 collect (catalan 12 i)))Evaluation took:
0.000 seconds of real time
0.000000 seconds of total run time (0.000000 user, 0.000000 system)
100.00% CPU
47,122 processor cycles
0 bytes consed
(1 11 65 273 910 2548 6188 13260 25194 41990 58786 58786)