Re: Map/Dict Efficiency

On 27/11/2013, at 7:16 AM, Alan Baljeu wrote:

>> Lookup is order (N), 
> while adding values, deleting values 
>> and merging with other maps has 
> order N. The main disadvantage 
>> is that changing values in large 
> maps is costly, both in terms 
>> of memory and time. 

The Erlang Frames proposal I wrote showed a method
where
 - lookup of M items takes O(M+N)
 - lookup of 1 item takes  O(log(N))
 - adding and deleting require copies, so are O(N)
 - merging M with N takes O(M+N)
 - the use of frames as "records" with a common set
   of keys can easily be optimised to store the
   keys just once, so the space cost is comparable
   to a compound term -- very important --
and presented actual benchmarks from a micro-VM
implementation.

Large maps can be handled by breaking them into
small ones.  I know the Erlang/OTP people were
looking at HAMTs, although I think they chose
something else for the release.  There was an
embedded Java system which implemented arrays
as N-way trees (where I recall N=16), not for
the sake of copying, but to be kinder to the
memory management subsystem.