Hash-tables

errr...I would *think* the second would be faster since you're doing 1 lookup instead of 3. In a properly implemented hash table with a good hash function, lookup is O(1) with the size of the table.

If you're not sure, measure. Measure before optimizing to see if you even need to optimize, and measure after to make sure it actually makes it faster.

Heck, I tested it out. Adding up 1 random value not used in the fibonacci-function (fib (n x)), tested out the efficiency by looping from 1 to 100,000, with a constant x.

It seems like the second idea is 1.5 times faster than the first function, using these macros in LISP:

 Spoiler

Code:

(defmacro aif (test then &optional else) ; for defmemoiz1
    `(let ((it ,test))
        (if it ,then ,else)))

(defmacro with-gensyms (gensyms &body body)
    `(let ,(mapcar #'(lambda (s)
                    `(,s (gensym)))
                gensyms)
        ,@body))

(defmacro defmemoiz1 (fn val &body body)
    (with-gensyms (hash-lst lst elt hash get-last-hash)
    `(let ((,hash-lst (make-hash-table)))
    (labels ((,get-last-hash (hash args) ;; Creates hash if it doesn't exist. Returns value if it does.
                    (if (cdr args)
                        (,get-last-hash
                            (aif (gethash (car args) hash) it
                                (setf (gethash (car args) hash) (make-hash-table)))
                            (cdr args))
                        (gethash (car args) hash))))
(defun ,fn ,val
    (or
        (,get-last-hash ,hash-lst (list ,@val))
    (setf     ;; Supposed to get from the val-list the following
            ;; If args = (2 8 9 3), then this part should be (gethash 2 (gethash 8 (gethash 9 (gethash 3 hash-lst))))
        ,(labels ((recursive-hash (args)
            (list 'gethash (car args)
                (if (cdr args)
                    (recursive-hash (cdr args))
                    hash-lst))))
            (recursive-hash (eval `(reverse ',val))))
        ,@body)))))))


;; For multiple values
(defmacro defmemoize (fn val &body body)
    (with-gensyms (lst hash-code)
    `(let ((,lst (make-hash-table :test #'equal)))
        (defun ,fn ,val
        (let ((,hash-code (list ,@val)))
            (or
                (gethash ,hash-code ,lst)
                (setf (gethash ,hash-code ,lst)
                    ,@body)))))))

Then using them on the function:

 Spoiler

Code:

(defun fib (n)
    (if (<= n 2) ; first two = 1
        1
        (+ (fib (1- n))
           (fib (- n 2)))))

Just replacing defun with defmemoiz1 and defmemoize to make the functions memoizing. (Guess what, I used another macro to simplify redefining of the fibonacci-function. Sigh.)

For several values, time increased exponentially. For 8 different values, it took almost 4 times longer to calculate compared to the second idea. For 3, time barely changed. For one value, time was the same. (But then again, for one value, I make another kind of hash-table, which increases the speed noticeably.)