Re: How to use associative arrays in Ada 2005?

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On 27 Nov 2006 11:53:43 -0800, Matthew Heaney wrote:

> Dmitry A. Kazakov wrote:
>>
>> That depends on each concrete case. Arrays of arrays have advantages and
>> disadvantages. It is to expect a performance penalty in terms of both space
>> and time for an hash of hash of hash vs. simple hash. Clearly, instead of
>> one look-up you are doing three.
> 
> Yawn.  A hash-table look-up is O(1).  It's like trying to argue that
> you'll lose weight by only eating 1 pea instead of 3 peas for dinner...

... asymptotically under certain conditions, which might be or not met in a
real case.

Also:

1. Insertion and deletion in sparse 3D arrays organized in hashes of hashes
might lead to an eager allocation and deallocation of subordinated hashes.
Shuffling memory is not a pea. In some cases it is a disaster.

2. Finding an optimal set of hash functions (and that is 1+n+n*m
functions!) might turn quite difficult, depending on how items are
distributed in 3D space. You might have a relatively evenly distributed
items in 3D, which awfully distributed in 2D and 1D planes.

3. You don't mention memory, for a good reason. Hashes are known space
eaters. And you have n**2 of them!

The bottom line is - I think a good advice to a student learning Ada, and
the Ada's way (tm) is to factor out a clean interface to his 3D array
first, and hide the implementation (be it a hash of hashes or anything
else). This might be obvious for Ada programmers, but people coming with
the background in other languages tend to think in terms of implementation.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de