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

Simon Strandgaard wrote:

>On Thu, 20 Nov 2003 06:00:03 +0900, Charles Hixson wrote:
>
>  
>
>>Simon Strandgaard wrote:
>>
>>    
>>
>>>>>On Wed, 19 Nov 2003 14:21:19 +0900, Charles Hixson wrote:
>>>>>
>>>>>          
>>>>>
>>>>>>Does anyone have an implementation of a multi-dimensioned sparse
>>>>>>array?
>>>>>>  
>>>>>>            
>>>>>>
>>>I am curious to how many dimension you need?  3, 7, 50 ?
>>>
>>>Which kind of algorithm are you implementing?
>>>      
>>>
>[snip]
>  
>
>>column, row, and move number you could quickly determine which (if any) 
>>piece was on that square.  I'm actually considering many more than eight 
>>rows & columns, and more than 200 moves, and perhaps there'll be a third 
>>(unknown as yet) dimension.  Like, perhaps, in a game of Angband.  I 
>>    
>>
>
>
>How about just using a one-dimentional sparse array, and this many2one
>dimension converter ?
>
>
>server> ruby a.rb
>0
>4
>16
>63
>server> expand -t2 a.rb 
>class SparseMatrix
>  def initialize(*size)
>    @size = size
>    @data = nil
>  end
>  attr_accessor :data
>  def calc_index(*where)   # many2one dimension conversion
>    index = 0
>    where.each_with_index{|val, i|
>      index *= @size[i]
>      index += val
>    }
>    index
>  end
>  def [](*where)
>    @data[calc_index(*where)]
>  end
>end
>
>m = SparseMatrix.new(4, 4, 4) 
>m.data = (0..63).to_a   # TODO: use sparse matrix array instead
>p m[0, 0, 0] # 0
>p m[0, 1, 0] # 4
>p m[1, 0, 0] # 16
>p m[3, 3, 3] # 63
>server> 
>
>--
>Simon Strandgaard
>
That *is* an interesting basic approach.  Of course data would need to 
be a hash table, but it certainly gets around the worries about the 
multiplicity of hash tables using excessive memory.  I'd just need to 
set the size large enough (say around 191to allow for 4 dimensions being 
handled with a single word index...but that's too small for many uses, 
so I'd often need to use a Bignum rather than a Fixnum).  Unfortunately, 
for my main use I expect I'll need an index that goes upto "around" 
5,000,000, so Bignums it will need to be.  Still, a calculation is much 
faster than the indirect lookups that were being talked about, and the 
actual hash would only need to store the entries that were actually 
generated....MUCH nicer!  And that hash clearly won't generate instances 
just because you try to read them, another big plus.  AND it's easier to 
understand.  You're pretending to have the full array available, when 
you look it's there, if you store something, it's remembered.  Nice!  
The only advantage that the mesh had was that you didn't need to check 
the empty cells to move up and down in a column (or row), and that was 
counterbalenced by not being able to find the row unless you started at 
a known position, and needing linear access.

So good in fact that all I need to do is decide between a hash and an 
AVL tree.  I probably won't need sorted access, so that's a clear vote 
in favor of the hash (and it won't cost much to add later if I decide I 
need it, so that's another vote for the hash).    The one real problem 
is that resizing the array would be quite expensive, so I'll need to 
make sure that it's large enough when the addresses are first 
calculated.  Again Bignum indexes.  (But I *do* wish that AVL trees were 
built-ins with a clear literal representation ..  and all the hash 
operators implemented.  It's not the data structure that's 
problematical, it's the literal representation...something analogous to 
the way hash literals are represented.)