Skip to content

Instantly share code, notes, and snippets.

@skeeto
Last active Sep 3, 2019
Embed
What would you like to do?
;;; Memoization benchmark -*- lexical-binding: t; -*-
;; Ref: https://github.com/skeeto/emacs-memoize
;; $ emacs -Q --batch -L path/to/memoize -f batch-byte-compile memoize-bench.el
;; $ emacs -Q --batch -L path/to/memoize -l memoize-bench.elc
;; Note: Benchmark requires at least 64-bit integers. Choose one of:
;; * Emacs >= 27
;; * Emacs <= 26 on 64-bit host
;; * Emacs <= 26 on 32-bit host with --with-wide-int
;; The `count-sums' function, an ideal target for memoization, computes
;; the number of ways to sum three numbers (A, B, C) to some target (N).
;; For example, there are 8 ways to sum 1, 3, 5 into 6:
;; 6 = 1+1+1+1+1+1
;; 6 = 1+1+1+3
;; 6 = 1+1+3+1
;; 6 = 1+3+1+1
;; 6 = 3+1+1+1
;; 6 = 3+3
;; 6 = 1+5
;; 6 = 5+1
;; Output on my machine:
;; count-sums-1 (1.558840815 298 1.0068730169999998)
;; count-sums-2 (0.000993427 0 0.0)
;; Takeaway: The memoize package is 3 orders of magnitude slower than
;; just doing it yourself!
(require 'benchmark)
(require 'cl-lib)
(require 'memoize)
(defun bench (f)
(princ
(format "%-16s %S\n" f
(benchmark-run 1
(cl-assert (= (funcall f 1 3 5 95) 2125576354395057369))
(cl-assert (= (funcall f 1 3 7 103) 2274358910569289778))
(cl-assert (= (funcall f 1 3 9 107) 1982808156511599680))
(cl-assert (= (funcall f 1 5 7 128) 1656941458726184233))
(cl-assert (= (funcall f 1 5 9 137) 1827027431869835658))
(cl-assert (= (funcall f 1 5 11 143) 1996711042862723685))
(cl-assert (= (funcall f 1 7 11 168) 1910877262550578250))
(cl-assert (= (funcall f 1 9 11 188) 2198774630014494641))))))
(defun count-sums-1 (a b c n)
(cond ((< n 0) 0)
((= n 0) 1)
((+ (count-sums-1 a b c (- n a))
(count-sums-1 a b c (- n b))
(count-sums-1 a b c (- n c))))))
(memoize 'count-sums-1)
(defun count-sums-2 (a b c n)
(let ((table (eval-when-compile (make-hash-table :test 'equal)))
(key (vector a b c n)))
(let ((result (gethash key table)))
(if result
result
(setf (gethash key table)
(cond ((< n 0) 0)
((= n 0) 1)
((+ (count-sums-2 a b c (- n a))
(count-sums-2 a b c (- n b))
(count-sums-2 a b c (- n c))))))))))
(defun simple-memoize (fun)
(let ((table (make-hash-table :test 'equal)))
(lambda (&rest args)
(let ((result (gethash args table)))
(if result
result
(setf (gethash args table)
(apply fun args)))))))
(defun count-sums-3 (a b c n)
(cond ((< n 0) 0)
((= n 0) 1)
((+ (count-sums-3 a b c (- n a))
(count-sums-3 a b c (- n b))
(count-sums-3 a b c (- n c))))))
(fset 'count-sums-3 (simple-memoize (symbol-function 'count-sums-3)))
(bench 'count-sums-1)
(bench 'count-sums-2)
(bench 'count-sums-3)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment