OpenEuphoria

Re: associative arrays

• Posted by "Carl R. White" <cyrek at BIGFOOT.COM> May 18, 2000
• 574 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.