Multi-dimensioned sparse array ?

Discussion in 'Ruby' started by Charles Hixson, Nov 19, 2003.

  1. 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?
     
    Charles Hixson, Nov 19, 2003
    #1
    1. Advertising

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


    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)
    >
    >http://www.rubygarden.org/ruby?HashOfHashes
    >
    >-austin
    >--
    >austin ziegler * * Toronto, ON, Canada
    >software designer * pragmatic programmer * 2003.11.19
    > * 01.34.12
     
    Bob Gustafson, Nov 19, 2003
    #2
    1. Advertising

  3. Bob Gustafson wrote:

    >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.)
     
    Charles Hixson, Nov 19, 2003
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Sandros
    Replies:
    3
    Views:
    383
    GIMME
    Nov 5, 2004
  2. Gregg Woodcock
    Replies:
    15
    Views:
    490
    Joe Wright
    Dec 4, 2004
  3. Colin Steadman

    Can I add rows to an already dimensioned 2d array

    Colin Steadman, May 17, 2004, in forum: ASP General
    Replies:
    4
    Views:
    202
    dlbjr
    May 18, 2004
  4. Bill Birkett

    sparse multi-dimensional arrays

    Bill Birkett, Oct 3, 2006, in forum: Ruby
    Replies:
    4
    Views:
    115
    Jason Nordwick
    Oct 3, 2006
  5. Manish Tomar

    for in to iterate sparse Array

    Manish Tomar, Jul 10, 2007, in forum: Javascript
    Replies:
    4
    Views:
    192
    Dr J R Stockton
    Jul 13, 2007
Loading...

Share This Page