Just tested: with SBCL 1.1.13 on Debian 7.1 Wheezy (Linux) a ten-pairs hash-table is double as fast as a ten-pairs a-list. This is not for nit-picking, I only wanted to know how much the difference really is.
First I define a list of all keys:
Code: Select all
CL-USER> (defparameter *keys* '(a b c d e f g h i j))
*KEYS*
Then I define an association list containing all keys and some fixnum values:
Code: Select all
CL-USER> (defparameter *a-list*
'((a . 0) (b . 1) (c . 2) (d . 3) (e . 4)
(f . 5) (g . 6) (h . 7) (i . 8) (j . 9)))
*A-LIST*
Here I test if ASSOC finds all values:
Code: Select all
CL-USER> (mapcar (lambda (x) (cdr (assoc x *a-list*))) *keys*)
(0 1 2 3 4 5 6 7 8 9)
Now I run the test one million times on the *a-list*. I'm using
MAPC instead of
MAPCAR because MAPC doesn't need to allocate memory for the resulting list (= 0 bytes consed), so the result later can be compared with the hash-table result.
Code: Select all
CL-USER> (time (dotimes (n 1000000)
(mapc (lambda (x) (cdr (assoc x *a-list*))) *keys*)))
Evaluation took:
1.239 seconds of real time
1.240078 seconds of total run time (1.240078 user, 0.000000 system)
100.08% CPU
2,449,594,250 processor cycles
0 bytes consed
NIL
I make a hash-table and copy the key/value pairs from the association list into the hash-table:
Code: Select all
CL-USER> (defparameter *h-table* (make-hash-table :size 10))
CL-USER> (mapcar (lambda (x)
(setf (gethash (car x) *h-table*) (cdr x)))
*a-list*)
(0 1 2 3 4 5 6 7 8 9)
I test if GETHASH finds all values:
Code: Select all
CL-USER> (mapcar (lambda (x) (gethash x *h-table*)) *keys*)
(0 1 2 3 4 5 6 7 8 9)
Now I run the test one million times on the hash-table:
Code: Select all
CL-USER> (time (dotimes (n 1000000)
(mapc (lambda (x) (gethash x *h-table*)) *keys*)))
Evaluation took:
0.622 seconds of real time
0.628039 seconds of total run time (0.628039 user, 0.000000 system)
100.96% CPU
1,303,777,083 processor cycles
0 bytes consed
Result:
- Association list: 1.239 seconds
- Hash-table: 0.622 seconds
This may be different with other Common Lisp implementations, so you can use the code above and run it with your implementation.
- edgar