Charles Hixson
11/20/2003 12:34:00 AM
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.)