Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have written a program in Ruby which calculates the median of a streaming set of numbers dynamically. For each number that arrives, the median is calculated for all the numbers that have arrived so far.

The issue I am facing is that the program times out on some inputs, and, most likely, the reason is that I return a variable that is passed to a routine. I need to do this because this variable changes inside the routine and I can't pass by reference in Ruby.

Is there any workaround for this inability to pass by reference? I have seen the code involving "binding" but I found it clumsy. Why does Ruby not have a simple, straightforward pass-by-reference as do C++, C# and Java? I have pasted my code below.

I maintain two heaps max and min. The value in any node in the max (min) heap is at least as large (small) as the value in any node below it. Any arriving number is inserted into the max heap or min heap with the proviso that the difference in the number of nodes in the two heaps does not exceed 1, and that the heap property be preserved for both heaps. With this proviso, the median can be calculated from the root elements in the two heaps.

Node=Struct.new(:v,:l,:r)do
end


max=0
min=0

def count(m)
        m==0 ? 0 : 1 + count(m.l) + count(m.r)
end


def delete(d,type)

      if d==0 
          return 0
      end
      if type=="max"
          if d.l==0 && d.r==0
              return 0
          elsif d.l!=0 && d.r!=0
              if  d.l.v > d.r.v 
                  d.v= d.l.v 
                  d.l=delete(d.l,type)
              else
                  d.v= d.r.v
                  d.r= delete(d.r,type)
              end
          elsif d.l == 0
                 d.v= d.r.v
                 d.r=delete(d.r,type)
              else
                 d.v= d.l.v
                 d.l=delete(d.l,type)
              end
     else
          if d.l==0 && d.r==0
              return 0
          elsif d.l!=0 && d.r!=0
              if  d.l.v < d.r.v 
                  d.v= d.l.v 
                  d.l=delete(d.l,type)
              else
                  d.v= d.r.v
                  d.r= delete(d.r,type)
              end
          elsif d.l == 0
                 d.v= d.r.v
                 d.r=delete(d.r,type)
              else
                 d.v= d.l.v
                 d.l=delete(d.l,type)
              end
     end
return d
    end

def insert(v,type,t)

        if t==0
            return t=Node.new(v,0,0)
        end
            if type=="max"
                    if v>t.v 
                    tmp=t.v
                    t.v=v
                                t.l=insert(tmp, type,t.l)
            else
                                t.l=insert(v,type,t.l)
            end
            else
                        if v<t.v 
                    tmp=t.v
                    t.v=v
                                t.l=insert(tmp, type,t.l)
            else
                                t.l=insert(v,type,t.l)
            end
        end        
                return t

end



n=gets.chomp.to_i

n.times do
    v=gets.chomp.to_i
     if (k=count(max)-count(min))==1 
        if v<max.v
            tmp=max.v
            max=delete(max,"max")
            min=insert(tmp,"min",min)
            max=insert(v,"max",max)
        else
                        min=insert(v,"min",min)
        end
        p (max.v+min.v)/2.0
     elsif  k==0
        if max==0 || v<=max.v
                        max=insert(v,"max",max)
            p max.v/1.0
        else
                        min=insert(v,"min",min)
            p min.v/1.0
        end
     else
                if v>min.v
            tmp=min.v
            min=delete(min,"min")
            max=insert(tmp,"max",max)
            min=insert(v,"min",min)
        else
                        max=insert(v,"max",max)
        end
        p (max.v+min.v)/2.0
     end
end
share|improve this question
    
If you don't want to mess with binding, you can instead wrap your variable in an object and pass the object, which will enable pass by reference. All you need is something really simple like: "Class Wrapper \n attr_accessor :value \n end" – Zack Oct 4 at 17:26
1  
"Why does Ruby not have a simple, straightforward pass-by-reference as do C++, C# and Java?" – Java doesn't support pass-by-reference at all, it is strictly pass-by-value, always, no exceptions. (It has, in fact, the exact same semantics as Ruby in this regard.) C++ and C♯ support pass-by-reference, but you have to explicitly ask for it; the default is pass-by-value. – Jörg W Mittag Oct 8 at 23:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.