Re: associative arrays
- Posted by "Carl R. White" <cyrek at BIGFOOT.COM> May 18, 2000
- 575 views
On Thu, 18 May 2000 16:25:59 +1200, Jiri Babor <J.Babor at GNS.CRI.NZ> wrote: >Associative arrays is the topic, as I promised earlier today. I call >them simply lists, because Rob kindly left the term vacant. I see I'm lagging behind again Minor quibble: The term 'list' may confuse Lisp/Prolog/Haskell programmers, and those who have implemented linked lists in other languages to get some level of sequence style arrays. >To my mind, there are only about three really simple designs possible. >The one used by Carl, basically just a sequence of alternating keys >and values. Obvious, very simple, but slow. Sounds just like me really doesn't it? The reason I implemented it that way was because I've been heavily influenced by using Perl recently, and basically that's how Perl stores associative arrays in memory. >I reverted to my original scheme: two separate 'parallel' subsequences >of equal length. It seems to be on average 20 to 50 % faster than the >second scheme. I considered that, but stupidly thought: "Oh, I'll need two sequences. We can't have that." For some unknown reason I forgot { {,,,} , {,,,} } !! [snip good stuff - see previous post] > global function join(... Another reason I implemented the aa type in such a simplistic way is that things like join() aren't necessary. The good old '&' operator suffices. Nevertheless, Jiri's code has grown on me (because mine isn't that good) so I'd like to suggest a couple of extras for lists.e: -- At the top of lists.e: without type_check -- We're fairly sure that the stuff in the library -- fits with the type spec, so there's no point checking while here. [global?] constant -- Readability Keys = 1, Data = 2 global type list(object assoc) if atom(assoc) then return 0 end if -- atoms are bad if not length(assoc) then return 1 end if -- {} is ok if length(assoc) != 2 then return 0 end if -- length must be 2 return length(assoc[Keys]) = length(assoc[Data]) end type global function invert(list assoc) -- Generate a reverse lookup list return {assoc[Data], assoc[Keys]} end function -- At the bottom of lists.e with type_check -- Turn it back on for safer outside code. Hope that's useful, Carl -- Wondering how he manages to irritate Jiri so much... -- The .sig got away again.