Dave Roberts <·············@re-move.droberts.com> writes:
> I was editing a bit of my resolver library today and decided to finally deal
> with something I have been skirting for a while. Simply, what is the best
> way to create a nice mapping table from integers<->symbols. In my case, I
> want to map from symbols representing DNS types (A, MX, TXT, etc.) to the
> corresponding type codes. I need to do this both directions, from symbols
> to codes when creating a query, and from codes back to symbols when
> decoding the response. I have tried this a couple ways before this, but
> they always felt kludgy.
>
> First attempt was simple a-lists. Write two functions to use ASSOC and
> RASSOC and we're in business. Nicely data driven.
>
> But then I started to think speed. A-lists are not fast when the size is
> large.
You never mention arrays or hashtables. If the number space is small,
you can use an array to index your symbols by integer and stick the
integer in the symbol's plist. If the number space is large, use
integers as a hash key with the symbols as values. Keep with the
ingeger in the plist. Either way should give you O(1) time access
unless you put other stuff in the plist for the symbol.
> (define-mappers typecode symbol ((1 'A)
> (2 'NS)
> (3 'MD)
> (4 'MF)
> (5 'CNAME)
> (6 'SOA)
> (7 'MB)
> (8 'MG)
> (9 'MR)
> (10 'NULL)
> (11 'WKS)
> (12 'PTR)
> (13 'HINFO)
> (14 'MINFO)
> (15 'MX)
> (16 'TXT)
> (252 'AXFR)
> (253 'MAILB)
> (254 'MAILA)
> (255 'ALL)) 'UNKNOWN NIL)
(defvar *my-symbol-map* (let ((map (make-array 256 :initial-element nil)))
(setf (svref map 1) 'A)
(setf (symbol-plist 'A) '(1 A))
...
(setf (svref map 255) 'ALL)
(setf (symbol-plist 'ALL) '(255 ALL))
map))
This is a rather long hand way of saying it. Using a temporary plist
and a loop may save some typing. When done, you can do this:
(svref *my-symbol-map* index) => symbol
(car (symbol-plist 'symbol)) => index
I don't know if a p-list actually enforces the need for an even number
of elements or not. I haven't tried that. Anyway, is this anything
like what you were looking for?
--
I wouldn't mind the rat race so much if it wasn't for all the damn cats.
David Steuber wrote:
> You never mention arrays or hashtables. If the number space is small,
> you can use an array to index your symbols by integer and stick the
> integer in the symbol's plist. If the number space is large, use
> integers as a hash key with the symbols as values. Keep with the
> ingeger in the plist. Either way should give you O(1) time access
> unless you put other stuff in the plist for the symbol.
Yea, but the problem is that the space is semi-sparse. Hashtables always
seem so heavyweight to me. I'd use them for a non-constant mapping. For
constant mappings, the compiler can often do better with a jump table of
some sort.
> (defvar *my-symbol-map* (let ((map (make-array 256 :initial-element nil)))
> (setf (svref map 1) 'A)
> (setf (symbol-plist 'A) '(1 A))
> ...
> (setf (svref map 255) 'ALL)
> (setf (symbol-plist 'ALL) '(255 ALL))
> map))
>
> This is a rather long hand way of saying it. Using a temporary plist
> and a loop may save some typing. When done, you can do this:
>
> (svref *my-symbol-map* index) => symbol
> (car (symbol-plist 'symbol)) => index
>
> I don't know if a p-list actually enforces the need for an even number
> of elements or not. I haven't tried that. Anyway, is this anything
> like what you were looking for?
Yep, that would work, too. It's efficient on the number->symbol mapping.
You're still searching doing a linear search through a sparse space on the
reverse mapping, however.
--
Dave Roberts, ·············@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog
I stupidly wrote:
>
> Yep, that would work, too. It's efficient on the number->symbol mapping.
> You're still searching doing a linear search through a sparse space on the
> reverse mapping, however.
>
Nevermind. I see what you're doing with the plist. Yes, that would work with
roughly constant time. Good way to do it.
--
Dave Roberts, ·············@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog
> I don't know if a p-list actually enforces the need for an even number
> of elements or not.
According to the CLHS, a property list always has an even number of elements.
·············@swipnet.se (Peter Lewerin) writes:
> > I don't know if a p-list actually enforces the need for an even number
> > of elements or not.
>
> According to the CLHS, a property list always has an even number of elements.
I was able to set a symbol's plist to a single element list. So the
rule was not enforced. I guess a-list and p-list are really in the
eyes of the assoc/get methods. As it is called a p-list, I would
consider it bad practice to set it to an odd number of elements.
--
I wouldn't mind the rat race so much if it wasn't for all the damn cats.
David Steuber <·····@david-steuber.com> wrote
> I was able to set a symbol's plist to a single element list. So the
> rule was not enforced.
Yes, but if I try to use the symbol in any way (or even inspect it)
after that, Lispworks tells me that the p-list is malformed and enters
the debugger.