1. Indexed vs associative data structures?
- Posted by GreenEuphorian May 17, 2014
- 1509 views
A recent post by krg pointed out that the difference between Euphoria's sequences and Lua's tables lies in the fact that the former are indexed, whereas the latter are associative.
I have a vague idea of the term associative (as in "associative arrays", which I know), but I am not quite sure I get its full meaning and implications. As for the the term "indexed", I guess it simply refers to the indexing of arrays and of Euphoria's sequences.
Could someone please elaborate on the respective pros and cons of associative vs indexed data structures? In what cases are indexed structures (as used in Euphoria) better than associative structures, and viceversa?
Also, was there not a plan to introduce something like associative arrays in Euphoria too, so that we could have var1=var2."xyz" ?
Thanks
2. Re: Indexed vs associative data structures?
- Posted by jimcbrown (admin) May 17, 2014
- 1465 views
As for the the term "indexed", I guess it simply refers to the indexing of arrays and of Euphoria's sequences.
That's pretty much it. An index into an array is always an integer, it always has a constant starting point (that is, it always starts from either zero or one), and it is contiguous (so no skipping indexes).
I think in Euphoria you can use a floating point number as an index into a sequence, but what happens is that the floating point is converted into an integer first.
I have a vague idea of the term associative (as in "associative arrays", which I know), but I am not quite sure I get its full meaning and implications.
Instead of an index, you have a key. Also, the keys do not have to be contiguous and they typically can be any data type (sometimes there are restrictions like it has to be a sortable object or something).
Could someone please elaborate on the respective pros and cons of associative vs indexed data structures? In what cases are indexed structures (as used in Euphoria) better than associative structures, and viceversa?
Arrays are the fastest, hands down. They also use less memory than an associative array, which also has to store the keys.
Conceptually, they also solve different problems. An array (or list, or sequence) is just a collection of objects, not necessarily in any particular order, that you want to keep together. An associate array keeps things sorted and associates a key to a value, so you can look up values by their key. It's kind of like a dictionary, where you look up a word (the key) and find its definition (the value).
Also, was there not a plan to introduce something like associative arrays in Euphoria too, so that we could have var1=var2."xyz" ?
Yes. I don't know if there were plans to add syntax sugar around it, though.
3. Re: Indexed vs associative data structures?
- Posted by BRyan May 17, 2014
- 1483 views
There are examples in the archive.
Go Here to first zip entry:
http://rapideuphoria.com/cgi-bin/asearch.exu?dos=on&win=on&lnx=on&gen=on&keywords=associative
4. Re: Indexed vs associative data structures?
- Posted by ne1uno May 17, 2014
- 1395 views
map?
edit: map already mentioned. Jim hid map.e in a link I overlooked.
5. Re: Indexed vs associative data structures?
- Posted by krg May 19, 2014
- 1400 views
Sorry for not elaborating on the differences - I thought my post was long enough!
Jim has said it all, but I'll just add the following.
Indexed data structures are very fast to access and manipulate (especially when doing slices), and use very little memory. Euphoria's sequences are so elegant that I keep wanting to port them to other languages!
Lua, awk and Rexx use associative arrays as their only data structure. It works great, except that you sacrifice speed and memory when all you need is a simple contiguous array of values.
Maps (associative arrays) in Euphoria 4.x are handy, especially when doing things like HTTP header processing.
HTH
