From: Charles Hixson <charleshixsn@...>
Date: 2003-11-20T03:43:24+09:00
Subject: Re: Multi-dimensioned sparse array ?

Austin Ziegler wrote:

>On Wed, 19 Nov 2003 14:21:19 +0900, Charles Hixson wrote:
>  
>
>>Does anyone have an implementation of a multi-dimensioned sparse
>>array?
>>    
>>
>
>What about using hashes?
>
>  msa = Hash.new { |h, k| h[k] = Hash.new }
>
>If you just use Numeric keys, there's little difference for your
>needs. You can subclass Hash to make it act a bit more like an Array
>under certain circumstances (e.g., #each would return values in
>key-order instead of a key-value pair; you could also do an ordered
>hash per [ruby-talk:20551] to potentially save sort times).
>
>For multi-dimensional auto-vivifying, you could do:
>
>  hash_maker = proc { |h, k| h[k] = Hash.new(&hash_maker) }
>  msa = Hash.new(&hash_maker)
>
>http://www.rubygarden.org/ruby?HashOfHashes
>
>-austin
>--
>austin ziegler    * austin@halostatue.ca * Toronto, ON, Canada
>software designer * pragmatic programmer * 2003.11.19
>                                         * 01.34.12
>  
>
How would you index along other than the first dimension?  But that's 
one of the main requirements.  (Currently I don't really need it to be 
ordered, but I do need to be able to index it along more than one 
dimension.  One idea I had was to insert every indexed cell into a 
sorted vector, and find the needed cell via binary search.  But finding 
the next cell along any particular index (except the last) would be an 
entire new search.  And since it's sparse this might need to be repeated 
numerous times.  Ugh!  The list mesh looks faster, even though it 
absorbe 2*n+1 units of memory for each cell used  (two pointers for each 
dimension.), and is itself quite slow.