Arc Forum | Alists vs table

Arc Forum

1 point by bOR_ 5737 days ago | 4 comments

http://arcfn.com/doc/assoc.html

Some advantages of association lists are that they can preserve order and preserve old values. Also, multiple association lists can share the same tail.

tables seem to have no trouble having multiple keys that have the same content as a tail, although the quoted text here seems to suggest that there is something like that.

Can anyone shed some light?

7 points by drcode 5737 days ago | link

I was confused by this as well, until I figured it out...

He's not talking about about CONTENT sharing a tail- He's talking about two association lists sharing their ENTIRE STRUCTURE...

Let's say you have a database made of key-value pairs and then need to fork it. The fork only contains one difference- One of the keys has to have a different value.

If the database is in a hash table, you're gonna have to clone the entire existing hash table. (They could share content, but the table, itself, needs to be a clone)

If the database is in an assoc list, the fork with the changed key can just have an extra pair for the new key, but then it can "borrow" the entire rest of the data from the other database. So virtually the entire database is shared between the two forks.

-----

3 points by almkglor 5737 days ago | link

Or use this instead: http://arclanguage.com/item?id=7365

-----

1 point by rincewind 5737 days ago | link

the lookup time in alists is O(n). What about proto-tables? Is the key hashed again for lookup in every prototype?

-----

1 point by almkglor 5736 days ago | link

O(M) where M is the depth of the find, or the nested prototype depth if it's not found.

Yes, the key is rehashed.

But really, the point is that proto-tables are quite a bit easier to use: you still retain the table lookup syntax tb.key

-----