From: Evan Phoenix <evan@...>
Date: 2006-03-11T01:31:56+09:00
Subject: Re: how to introduce reference objects into ruby

See below.

On 3/10/06, Geert Fannes <Geert.Fannes@ikanconsulting.com> wrote:
> The problem with the code you sent is that you have to go through ALL
> your matrix elements to get a certain row or column, which takes too
> long. Remember that this is a LARGE matrix (my current C implementation
> can handle 100M row and cols and 800M elements). Of course this will be
> too much for Ruby since its memory footprint is larger and its garbage
> collecter will burn a lot of cpu with this number of elements, but
> still, I want the Ruby implementation to contain also a lot of elements.
> It is not feasible to iterate through all elements for retrieving just
> one row or col. What I want looks more like:
>
> class SparseMatrix
>   def initialize()
>     @rows=Hash.new{|hash,key|hash[key]=Hash.new}
>     @columns=Hash.new{|hash,key|hash[key]=Hash.new}
>   end
>   def []=(i,j,value)
>     @rows[i][j]=value
>     @columns[j][i]=value
>   end
>   def getRow(i)
>     return @rows[i]
>   end
>   def getCol(j)
>     return @columns[j]
>   end
> end
>
> m=SparseMatrix.new
> m[10000,200000]=12.01
> m[10000,400000]=12.02
> p m.getRow(10000)
> p m.getCol(200000)
>
> Unfortunately, this code duplicates the content values of the matrix, it
> has a copy inside the @columns and one inside the @rows and these need
> to be maintained so they stay the same, which is programming and
> execution overhead.

This is sort of wrong. Remember that in ruby, like java, most things
are just pointers to objects. The only difference is Fixnums, Symbols,
and the boolean primitives. When you assign a Fixnum, the value is
encoded directly into the pointer. This saves everyone from having to
have thousands of instances of the object which represents the number
1.

You want a reference object because when you assign a Fixnum as the
element in the matrix, it gets stored directly in 2 pointers and
therefore are unrelated.

To get around this, as you stated, you could make, say a Call class
and store the call duration in an instance, and store the object the 2
places in the Hash's (really just storing 2 references to the same
object). Then when you update, say, information from the row, the
information at the column is also updated. Thats how ruby works.

Your statement about Ruby not being able to handle many different
references to the same object is blatantly incorrect. What made you
say it?

All in all, if you believe that you MUST use Fixnums only for memory
reasons, then, as Caleb stated, maybe you should just wrap your C
extension. All high level languages are going to give you the same
trouble (actually others probably even more trouble) when it comes to
how much memory is used to store an object.

I personally think you are just guessing that it will take up too much
room in ruby and that if you try and write it and test it, you'll be
pleasantly surprised.

 - Evan

>
> Geert.
>
> -----Original Message-----
> From: Hugh Sasse [mailto:hgs@dmu.ac.uk]
> Sent: Friday, March 10, 2006 3:32 PM
> To: ruby-core@ruby-lang.org
> Subject: Re: how to introduce reference objects into ruby
>
> On Fri, 10 Mar 2006, Geert Fannes wrote:
>
> > But things change when you want to implement a SPARSE matrix, i.e., a
> > matrix for which most of its elements are empty. E.g., I am analyzing
> > call-networks, data from a telecom firm that contains the call
> durations
> > for its customers, which can be represented with a matrix: element
> (i,j)
> > is the duration that j calls i. Since not everybody calls to
> everybody,
>
> # Untested code.
> # There may well be a faster way, but you don't need pointers to do
> # this.
> class Durations
>   def initialize()
>     @matrix = Hash.new
>   end
>
>   def insert(i,j,duration)
>     @matrix[[i,j]] = duration
>   end
>
>   def getrow(i)
>     return getline(0,1,i)
>   end
>
>   def getcol(i)
>     return getline(1,0,i)
>   end
>
>   private
>
>   # get horizontal or vertical line
>   def getline(a,b,i)
>     line = []
>     linehash = {}
>     @matrix.keys.each do |k|
>       linehash[k[b]] = @matrix[k] if k[a] == i
>     end
>     linehash.keys.sort.each do |index|
>       line << linehas[index]
>     end
>     return line
>   end
>
> end
>
> #       HTH
> #       Hugh
>
>
>


--
When I do good, I feel good;  when I do bad, I feel bad,
and that is my religion.
    -- Abraham Lincoln (1809 - 1865)