From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00,DIET_1,
	REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4
X-Google-Thread: 103376,693e247f5dca709d
X-Google-Attributes: gid103376,public
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news2.google.com!news4.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!newsfeed00.sul.t-online.de!t-online.de!tiscali!newsfeed1.ip.tiscali.net!proxad.net!proxad.net!newsfeed.arcor.de!newsspool4.arcor-online.net!news.arcor.de.POSTED!not-for-mail
From: "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>
Subject: Re: How to use associative arrays in Ada 2005?
Newsgroups: comp.lang.ada
User-Agent: 40tude_Dialog/2.0.15.1
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Reply-To: mailbox@dmitry-kazakov.de
Organization: cbb software GmbH
References: <1164103903.240838.37230@j44g2000cwa.googlegroups.com>
 <u7ixorigx.fsf@earthlink.net>
 <1164152113.623461.130190@e3g2000cwe.googlegroups.com>
 <1164310051.811802.237400@l12g2000cwl.googlegroups.com>
 <14xluht6idlik$.1cxod3mnfvcfs.dlg@40tude.net> <upsbdhxlo.fsf@earthlink.net>
 <1164567954.228842.32980@h54g2000cwb.googlegroups.com>
 <1tt24us1dtxxk$.4j9ua533yewd$.dlg@40tude.net>
 <1164657223.760376.158200@j72g2000cwa.googlegroups.com>
Date: Mon, 27 Nov 2006 22:11:52 +0100
Message-ID: <1kxzfampqtgkz.6gzp3w8j002$.dlg@40tude.net>
NNTP-Posting-Date: 27 Nov 2006 22:11:50 CET
NNTP-Posting-Host: 481f4216.newsspool4.arcor-online.net
X-Trace: 
 DXC=OPRAG``L?4PHigV@eW57PQ4IUK<Cl32<Q4Fo<]lROoRQ4nDHegD_]RU_3D8NE8RS]UDNcfSJ;bb[UIRnRBaCd<M^4fZn^Hc0:RX?6Oomc@m<4]
X-Complaints-To: usenet-abuse@arcor.de
Xref: g2news2.google.com comp.lang.ada:7712
Date: 2006-11-27T22:11:50+01:00
List-Id: <comp.lang.ada>

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