Page 1 of 1

Defining setf behavior (Or is there an easier way?)

Posted: Mon Nov 25, 2013 8:14 pm
by Gopher
So, I notice I frequently type

Code: Select all

(cdr (assoc key list))
in my code to access the values of associative lists.

First, I'm surprised I haven't been able to find an easier way to do this. Surely accessing a value from an associative array is not a rare task. Am I missing something?

What I've ended up doing is making it into a function:

Code: Select all

(defun cadsoc (key lis) (cdr (assoc key lis)))
The problem with this is that I can't alter the value. If I use (cdr (assoc)) I can setf it to whatever I want, but setf doesn't know what to do with my function. How do I teach it?

Re: Defining setf behavior (Or is there an easier way?)

Posted: Thu Nov 28, 2013 12:44 pm
by Cass
Just learning myself, but might a hash table do what you want?

You can make them with:

(defparameter *hash-table* (make-hash-table))

Create new entries with:

(setf (gethash 'entry-key *hash-table*) value)

And fetch them back with:

(gethash 'entry-key *hash-table*)

Which will return the associated value and true if it's found, or NIL and false otherwise.

Re: Defining setf behavior (Or is there an easier way?)

Posted: Thu Nov 28, 2013 2:57 pm
by marcoxa
Using GETHASH does not change the basic issue.

The easy solution is to use a SEFT definition

Code: Select all

(defun (setf cadsoc) (v key alist)
   (let ((kv (assoc key alist)))
      (if kv (setf (cdr kv) v) (error "Key ~S not found in a-list." key))))
Now you can do:

Code: Select all

CL-USER 2 > (defvar l (acons 42 'a ()))
L

CL-USER 3 > al
((42 . A))

CL-USER 4 > (setf (cadsoc 42 al) 'qwerty)

CL-USER 4> al
((42 . QWERTY))
Once you have grokked SETF functions (and DEFSETF) you can move on to using hash tables, which, indeed may be better for your needs.

Cheers
--
MA

Re: Defining setf behavior (Or is there an easier way?)

Posted: Thu Nov 28, 2013 5:11 pm
by Gopher
Thanks, I actually already figured it out in the time it took for the original post to be approved.

Code: Select all

(defun cadsoc (key lis) (cdr (assoc key lis)))

(defun (setf cadsoc) (value key lis) (if (assoc key lis) (setf (cdr (assoc key lis)) value) (setf (cdr (last lis)) (cons (cons key value) ()))))
The great thing about this is if the key does not exist, the setf will create it.

As for hash tables, I considered it, but I thought I read somewhere that they're less efficient than associative arrays unless you have thousands of keys or something like that. Was I misinformed?

Re: Defining setf behavior (Or is there an easier way?)

Posted: Fri Nov 29, 2013 12:48 am
by marcoxa
Sure.

BTW. Your version behaves more like (SETF GETHASH). It's a design choice.

MA

Re: Defining setf behavior (Or is there an easier way?)

Posted: Sat Nov 30, 2013 12:08 am
by Gopher
What is that "sure" in response to? Sure hash tables are less efficient, or sure I was misinformed?

Re: Defining setf behavior (Or is there an easier way?)

Posted: Sat Nov 30, 2013 4:39 am
by edgar-rft
The real efficiency difference between association lists and hash-tables is implementation dependent, but as a rule of thumb you can say that association lists are ok for a number of up to ten key/value pairs. If you have more pairs then hash-tables usually are faster. Common Lisp provides the TIME macro where you can test yourself which one is better for your program.

- edgar

Re: Defining setf behavior (Or is there an easier way?)

Posted: Sat Nov 30, 2013 5:43 am
by Gopher
I see, thanks. I thought it was a much bigger number than ten. Even so, most of what I use alists for is smaller.

Re: Defining setf behavior (Or is there an easier way?)

Posted: Sat Nov 30, 2013 5:24 pm
by edgar-rft
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

Re: Defining setf behavior (Or is there an easier way?)

Posted: Sun Dec 01, 2013 12:20 am
by Gopher
I see, thanks for your help.