Multi-dimensioned sparse array ?

[Charles Hixson]

Does anyone have an implementation of a multi-dimensioned sparse array?

The only implementation that I can think of involves a mesh of
list-nodes, and it looks to me like a lot of the operations would be
quite slow.

A sketch of my idea is:

class MuSpArray2 # a two dimensioned sparse array
def initialize()
@names = {}
@x = []
@y =[]
end

def names (n)
names[x] = names.size + 1 unless names[x]
names[x]
end

def add(x, y, val)
ndxx = names(x)
ndxy = names(y)
## now I've got index values, so I need to check if they've been
entered already,
## if so I must find the index position, otherwise I need to add then
index in (at the end, probably)
## then I must construct a node like [nxtX, nxtY, val] and place it
into the mesh
etc.

But of course there are lots of other operations, like slices. And I
would expect to need to extend this to more than two dimensions, etc. I
can't use the normal matrix class, because it's a sparse matrix. But I
expect to need to be "appending" one matrix onto another, and there may
be interleavings. Also I'll need to be able to find pref as well as
next. Etc. So this approach would work....but the code would probably
be too slow to use at any size at all. (Also note that with this
implementation I would never dare forget a name. Probably not a big
restriction, but worth noting.)

With all the limitations, if I were satisfied with a 2-D solution I'd
probably parameterize the array indexes "somehow" (being able to both
scan down a row and across a column causes difficulties) and turn it
into a one dimensional vector. But with more than two dimensions this
appears to be less feasible.

Any suggestions?

[Austin Ziegler]

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)

[url]http://www.rubygarden.org/ruby?HashOfHashes[/url]

-austin
--
austin ziegler * [email]austin@halostatue.ca[/email] * Toronto, ON, Canada
software designer * pragmatic programmer * 2003.11.19
* 01.34.12

[Bob Gustafson]

There is a lot of work already done on sparse matrix computer math.

See for example

[url]http://www-users.cs.umn.edu/~saad/software/SPARSKIT/sparskit.html[/url]

That code could be translated to Ruby, or, to retain speed, the
'C' or Fortran code could be wrapped with a Ruby interface.

Whatever works.

BobG


On Wed, 19 Nov 2003 02:02:29 -0500, 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)
>
>[url]http://www.rubygarden.org/ruby?HashOfHashes[/url]
>
>-austin
>--
>austin ziegler * [email]austin@halostatue.ca[/email] * Toronto, ON, Canada
>software designer * pragmatic programmer * 2003.11.19
> * 01.34.12

[Robert Klemme]

"Austin Ziegler" <austin@halostatue.ca> schrieb im Newsbeitrag
news:200311192229.932403@PADD...

> 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)

Another option: use a single Hash, *no* hash nesting and arrays as keys:

irb(main):012:0> multDim = Hash.new(0)
=> {}
irb(main):013:0> multDim[[1,12]]=4
=> 4
irb(main):014:0> multDim[[1,12]]=6
=> 6
irb(main):015:0> multDim[[3,12]]=5
=> 5
irb(main):016:0> multDim[[1,3]]=34
=> 34
irb(main):017:0> multDim[[1,12]]
=> 6
irb(main):018:0> multDim[[88,66]]
=> 0
irb(main):019:0>

Which of the two has better performance depends on the nature of algorithms
you want to do on the matrix.

If you subclass Hash and add some methods you can add dimension checks for
the keys, some fancy iteration stuff, create vectors on the fly and whatever
methods you need for the matrix...

Regards

robert

> [url]http://www.rubygarden.org/ruby?HashOfHashes[/url]
>
> -austin
> --
> austin ziegler * [email]austin@halostatue.ca[/email] * Toronto, ON, Canada
> software designer * pragmatic programmer * 2003.11.19
> * 01.34.12
>
>

[Charles Hixson]

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)
>
>[url]http://www.rubygarden.org/ruby?HashOfHashes[/url]
>
>-austin
>--
>austin ziegler * [email]austin@halostatue.ca[/email] * 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.

[Charles Hixson]

Bob Gustafson wrote:

>There is a lot of work already done on sparse matrix computer math.
>
>See for example
>
>[url]http://www-users.cs.umn.edu/~saad/software/SPARSKIT/sparskit.html[/url]
>
>That code could be translated to Ruby, or, to retain speed, the
>'C' or Fortran code could be wrapped with a Ruby interface.
>
>Whatever works.
>
>BobG
>
>...
>

Thanks for the link. Whee! Fortran. Betcha it's Fortran77 too.
Well, Fortran's fast, and has nice matrix handling, but otherwise, ugh!
(Though I have kept peeking at Fortran>=90, just because. But no decent
compiler yet, and I don't really expect one, as most people have lost
interest.)

[Simon Strandgaard]

>>On Wed, 19 Nov 2003 14:21:19 +0900, Charles Hixson wrote:

>>
>>

>>>Does anyone have an implementation of a multi-dimensioned sparse
>>>array?
>>>

[snip]

> 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.

I am curious to how many dimension you need? 3, 7, 50 ?

Which kind of algorithm are you implementing?

--
Simon Strandgaard

[Austin Ziegler]

On Thu, 20 Nov 2003 02:42:16 +0900, Robert Klemme wrote:

> "Austin Ziegler" <austin@halostatue.ca> schrieb im Newsbeitrag

>> 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 }
>> hash_maker = proc { |h, k| h[k] = Hash.new(&hash_maker) }
>> msa = Hash.new(&hash_maker)

> Another option: use a single Hash, *no* hash nesting and arrays as
> keys:

I believe that Mr Hixson requires slices. This wouldn't be possible
with array-keys.

-austin
--
austin ziegler * [email]austin@halostatue.ca[/email] * Toronto, ON, Canada
software designer * pragmatic programmer * 2003.11.19
* 15.34.36

[Austin Ziegler]

On Thu, 20 Nov 2003 03:43:24 +0900, Charles Hixson wrote:

> Austin Ziegler wrote:

>> hash_maker = proc { |h, k| h[k] = Hash.new(&hash_maker) }
>> msa = Hash.new(&hash_maker)
>>
>> [url]http://www.rubygarden.org/ruby?HashOfHashes[/url]

> How would you index along other than the first dimension? But
> that's one of the main requirements.

Using the above:

hash_maker = proc { |h, k| h[k] = Hash.new(&hash_maker) }
msa = Hash.new(&hash_maker)
msa[0] # => {}
msa[0][5] # => {}
msa # => {0=>{5=>{}}
msa[5][3][2] = 3 # => 3
msa # => {5=>{3=>{2=>3}}, 0=>{5=>{}}}

The first pitfall that you'll have is:

msa[0] = 3
msa # => {5=>{3=>{2=>3}}, 0=>3}

The second pitfall is on the HashOfHashes page.

-austin
--
austin ziegler * [email]austin@halostatue.ca[/email] * Toronto, ON, Canada
software designer * pragmatic programmer * 2003.11.19
* 15.36.49

[Charles Hixson]

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?
>>>>
>>>>
>>>>

>[snip]
>
>

>>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.
>>
>>

>
>I am curious to how many dimension you need? 3, 7, 50 ?
>
>Which kind of algorithm are you implementing?
>
>--
>Simon Strandgaard
>

It's actually basically a lookup algorithm at this point, but I'd rather
not be too specialized. If you want a simple visual idea, imagine that
you're representing the pieces on a chess board. One representation
could have columns, rows, and move-number, such that if you knew the
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
realize that none of these examples are done quite this way, for rather
obvious reasons. One would clearly need to pack the representation
tightly for storage...but that's no big problem, as when it's being
stored one doesn't need to move between rows & columns. The packing and
unpacking operations can afford to be relatively slow.

The end goal of the structure is to be included in an AI program which I
haven't yet designed, much less built. But I'm looking for useful
pieces that I can build before starting. E.g. I know that I'll need a
B+Tree. And I suspect that I'll need the data structure to have
multiple indexes, so a simple B+Tree approach won't work. (This is
nearly unrelated to the multi-dimensioned sparse array.) Anyway, I
don't know how many dimensions I'll need, but probably no more than four
large ones (where large means to big to be a reasonable enumeration in C).

If this approach proves too difficult, I'll probably settle for using a
packed representation, with reasoning being done using an unpacked fixed
size array (perhaps 500 X 500 x 10 or 100 X 100 X 100 X 10) that I might
call the foeva, but as you can see it would quickly get too large to be
useful. Another approach would be to do all of the detail work in, say,
D (Digital Mars D), a language that is in many ways similar to Ruby, but
is an expansion from C that differs from either C++ or Objective C.
(Objective C is another possibility, but I've never learned it even as
well as I've learned D -- which is still being written.)

[Charles Hixson]

Austin Ziegler wrote:

>On Thu, 20 Nov 2003 03:43:24 +0900, Charles Hixson wrote:
>
>

>>Austin Ziegler wrote:
>>
>>

>>>hash_maker = proc { |h, k| h[k] = Hash.new(&hash_maker) }
>>>msa = Hash.new(&hash_maker)
>>>
>>>[url]http://www.rubygarden.org/ruby?HashOfHashes[/url]
>>>
>>>

>
>
>

>>How would you index along other than the first dimension? But
>>that's one of the main requirements.
>>
>>

>
>Using the above:
>
> hash_maker = proc { |h, k| h[k] = Hash.new(&hash_maker) }
> msa = Hash.new(&hash_maker)
> msa[0] # => {}
> msa[0][5] # => {}
> msa # => {0=>{5=>{}}
> msa[5][3][2] = 3 # => 3
> msa # => {5=>{3=>{2=>3}}, 0=>{5=>{}}}
>
>The first pitfall that you'll have is:
>
> msa[0] = 3
> msa # => {5=>{3=>{2=>3}}, 0=>3}
>
>The second pitfall is on the HashOfHashes page.
>
>-austin
>--
>austin ziegler * [email]austin@halostatue.ca[/email] * Toronto, ON, Canada
>software designer * pragmatic programmer * 2003.11.19
> * 15.36.49
>

It seems like I *MUST* be misunderstanding the hash of hashes concept.
But it looks to me as if given:
msa.default = nil
then
msa[2] == nil #as it wasn't defined above
and therefore
msa[2][3] === nil[3]
but nil[3] isn't defined.

So I ran a test on:
# test.rb

hash_maker = proc { |h, k| h[k] = Hash.new(&hash_maker) }
tst = Hash.new(&hash_maker)

tst[3][2] = "able"
x = 3
y = 2
print tst[x][y][3], "\n" # ==>101
#!!!That was a bit of a surprise! And I still don't understand it.
(101.chr == 'e'?!)
# --Later: Of Course. That's an index into the returned string!

#!!!OTOH, it looks like as long as I don't make *ANY* errors it may work.
#!! But I don't understand either it, or how much space it consumes
print "<<#{x}, #{y}>>:#{tst[x][y]} \n"
print "<<#{x}, #{y-1}>>:#{tst[x][y-1]} \n"
==><<3, 2>>:able
==><<3, 1>>:
So that works out correctly. I may need to fake ranges, but are cells
generated if I read them instead of writing to them? If so this isn't
useable, as it will take up too much space. Otherwise....It may just be
the best solution possible. (I can throw a class wrapper around it, so
the interface isn't a problem...much)
Unfortunately, at this point I added the line:
tst.default = nil
right after the declaration.
Whoops! Now tst[3][2] = "able" throws the error that I expected.
I guess that could be fixed by defining the <=> to set default to nil
before testing and back to hashmaker before exit. So I'm starting to
understand the implementation...but not the space constraints yet.

[Simon Strandgaard]

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

[Charles Hixson]

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.)

[Robert Klemme]

"Charles Hixson" <charleshixsn@earthlink.net> schrieb im Newsbeitrag
news:3FBBD914.7050602@earthlink.net...

> 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?
> >>>>
> >>>>
> >>>>

> >[snip]
> >
> >

> >>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.
> >>
> >>

> >
> >I am curious to how many dimension you need? 3, 7, 50 ?
> >
> >Which kind of algorithm are you implementing?
> >
> >--
> >Simon Strandgaard
> >

> It's actually basically a lookup algorithm at this point,

Then I'd really consider the "Hash with Arrays as keys" approach (see my
other post). Lookups should be quite fast.

Regards

robert