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