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?

 

[Bob Gustafson]

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

See for example

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

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

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

 

[Charles Hixson]

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

See for example

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

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