Last active
September 3, 2019 13:57
-
-
Save skeeto/424992df03a6cfa9997354bd1ccc1ae7 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;;; 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