Charles Hixson
11/19/2003 5:21:00 AM
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?