View mode: basic / threaded / horizontal-split · Log in · Help
April 13, 2009
Re: Associative arrays with void values
On Mon, 13 Apr 2009 01:45:00 -0400, bearophile <bearophileHUGS@lycos.com>  
wrote:

> dsimcha:
>> What if the key is a long?
>
> At the moment an AA like this:
> byte[long] aa;
> allocates 16 or more bytes/pair, so it needs the same memory as:
> long[long] aa;
>
> A built-in set can of course use only about 8 bytes (plus few empty  
> cells in the hash) for a:
> HashSet!(long)
>
> Bye,
> bearophile

The AA node types are currently implemented as a binary tree for collision  
resolution, so each node also needs at least 2 pointers for the child  
nodes.  Possibly a parent pointer, but I don't think so.

So T[long] aa will be 16 bytes + sizeof(T) for each node, assuming a  
pointer is 4 bytes.

But technically, there is always going to be cases where waste occurs,  
even without the void hack, depending on the resulting size of your  
nodes.  Imagine a 33 byte node, which will use up 64 bytes of space per  
node.  This is one of the reasons Tango and Dcollections have chunk  
allocators where a large chunk of nodes is allocated at once from the GC  
(or from malloc for non-GC types).

-Steve
April 14, 2009
Re: Associative arrays with void values
bearophile wrote:
> Benji Smith:
> 
>> Especially since an associative array should have a .keys property that 
>> returns a set.
> 
> I don't agree.  I think associative arrays should have .keys/.values/.items that return a lazy view that acts like a .set/.list/.list of pairs. Such "lazy views" don't actually store anything, they are very light. This design is now present in Python3, Java and I have done very similar things in my dlibs (named xkeys/xvalues/xitems in my dlibs, but xkeys isn't a set-like thing yet).

Actually I think we do agree. From an API perspective (rather than an 
implementation perspective), I think the .keys property should generally 
return a lazily constructed result (object? struct? I don't really 
care). But I think it should conform to some standardized notion of 
"set-ness" (interface? concept? again, I don't care).

HashSets are a perfectly acceptable implementation for me, as are Set 
interfaces, but I know some people won't like them, and those impl 
details aren't a big deal to me.

But whatever notion the language uses for its "Set" construct should be 
the same dohickey used by the AA .keys property.

>> (Incidentally, I also think the natural set operations, like 
>> intersection and mutual exclusion, are just as handy for maps as for sets.)
> 
> It's less semantically clean to define certain set operations on AAs, because for example you have to decide what to do when keys are equal but their values are not. You can avoid such semantic troubles altogether performing set operations just only on the lazy view of the keys.

You just have to define those operations on pairs rather than just on 
single values (for example, the union of two maps is naturally a multimap).

--benji
Next ›   Last »
1 2
Top | Discussion index | About this forum | D home