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

Discussion of Common Lisp

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

Postby Gopher » Mon Nov 25, 2013 8:14 pm

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?
Gopher
 
Posts: 18
Joined: Mon Nov 25, 2013 1:01 am

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

Postby Cass » Thu Nov 28, 2013 12:44 pm

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.
Cass
 
Posts: 5
Joined: Thu Oct 24, 2013 8:14 am

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

Postby marcoxa » Thu Nov 28, 2013 2:57 pm

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
Marco Antoniotti
marcoxa
 
Posts: 69
Joined: Thu Aug 14, 2008 6:31 pm

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

Postby Gopher » Thu Nov 28, 2013 5:11 pm

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?
Gopher
 
Posts: 18
Joined: Mon Nov 25, 2013 1:01 am

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

Postby marcoxa » Fri Nov 29, 2013 12:48 am

Sure.

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

MA
Marco Antoniotti
marcoxa
 
Posts: 69
Joined: Thu Aug 14, 2008 6:31 pm

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

Postby Gopher » Sat Nov 30, 2013 12:08 am

What is that "sure" in response to? Sure hash tables are less efficient, or sure I was misinformed?
Gopher
 
Posts: 18
Joined: Mon Nov 25, 2013 1:01 am

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

Postby edgar-rft » Sat Nov 30, 2013 4:39 am

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
edgar-rft
 
Posts: 154
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

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

Postby Gopher » Sat Nov 30, 2013 5:43 am

I see, thanks. I thought it was a much bigger number than ten. Even so, most of what I use alists for is smaller.
Gopher
 
Posts: 18
Joined: Mon Nov 25, 2013 1:01 am

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

Postby edgar-rft » Sat Nov 30, 2013 5:24 pm

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
edgar-rft
 
Posts: 154
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

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

Postby Gopher » Sun Dec 01, 2013 12:20 am

I see, thanks for your help.
Gopher
 
Posts: 18
Joined: Mon Nov 25, 2013 1:01 am


Return to Common Lisp

Who is online

Users browsing this forum: Bing [Bot] and 5 guests