Passing blocks further down

(Matthias Luedtke) #1

Hello Rubyists,

at first I must say that after reading this newsgroups for some weeks now I'm happy to learn from so many smart and kind people in here. This is the place where you actually believe that programming is fun.

I'm implementing a red black tree and I'd like to let users of the class be able to traverse it by calling each. I managed to implement the class so far but I am unsure whether I use the right technique to pass the incoming block from each to the helper method traverse_inorder.

I cut the code down to the minimum, @root is of class Node which looks like it's supposed to be :slight_smile:

class RBTree

   # Visits each node in inorder
   def each(&block)
     traverse_inorder(@root){|x| block.call(x)}
   end

   private
   def traverse_inorder(x, &block)
     if not x.nil? then
       traverse_inorder(x.left){ |n| block.call(n) }
       yield x.key
       traverse_inorder(x.right){ |n| block.call(n) }
     end
   end
end

t = RBTree.new
t.each{ |node| puts node }

Invoking the call method explicitely on the block seems rather odd to me. Is it the only way?

Regards,
Matthias

(James Edward Gray II) #2

traverse_inorder(@root, &block)

:wink:

Hope that helps.

James Edward Gray II

···

On Aug 17, 2005, at 5:56 PM, Matthias Luedtke wrote:

    traverse_inorder(@root){|x| block.call(x)}

(Joel VanderWerf) #3

Sorry for late reply, but this is something useful to know about yield
vs. call. See below.

Matthias Luedtke wrote:

Hello Rubyists,

at first I must say that after reading this newsgroups for some weeks
now I'm happy to learn from so many smart and kind people in here. This
is the place where you actually believe that programming is fun.

I'm implementing a red black tree and I'd like to let users of the class
be able to traverse it by calling each. I managed to implement the class
so far but I am unsure whether I use the right technique to pass the
incoming block from each to the helper method traverse_inorder.

I cut the code down to the minimum, @root is of class Node which looks
like it's supposed to be :slight_smile:

class RBTree

  # Visits each node in inorder
  def each(&block)
    traverse_inorder(@root){|x| block.call(x)}
  end

  private
  def traverse_inorder(x, &block)
    if not x.nil? then
      traverse_inorder(x.left){ |n| block.call(n) }
      yield x.key
      traverse_inorder(x.right){ |n| block.call(n) }
    end
  end
end

t = RBTree.new
t.each{ |node| puts node }

Invoking the call method explicitely on the block seems rather odd to
me. Is it the only way?

Regards,
Matthias

You can also do this by chaining yields:

  class RBTree

    # Visits each node in inorder
    def each
      traverse_inorder(@root){|x| yield x}
    end

    private
    def traverse_inorder(x)
      if not x.nil? then
        traverse_inorder(x.left){ |n| yield n }
        yield x.key
        traverse_inorder(x.right){ |n| yield n }
      end
    end
  end

  t = RBTree.new
  t.each{ |node| puts node }

The idea is that yielding to a block is cheaper than constructing a Proc
object and sending it #call.

Here's a benchmark for some similar code (see below), but YMMV. It
compares the four possibilities (yield or call in the outer method,
yield or call in the inner method).

require 'benchmark'

def outer11(&bl)
  inner1(&bl)
end

def outer12(&bl)
  inner2(&bl)
end

def outer21
  inner1 {yield}
end

def outer22
  inner2 {yield}
end

def inner1(&bl)
  bl.call
end

def inner2
  yield
end

n = 100000

Benchmark.bmbm(10) do |rpt|
  rpt.report("outer11") do
    n.times {outer11{}}
  end

  rpt.report("outer12") do
    n.times {outer12{}}
  end

  rpt.report("outer21") do
    n.times {outer21{}}
  end

  rpt.report("outer22") do
    n.times {outer22{}}
  end
end

__END__

Output:

Rehearsal ---------------------------------------------
outer11 0.890000 0.010000 0.900000 ( 0.894500)
outer12 0.370000 0.000000 0.370000 ( 0.364880)
outer21 0.770000 0.000000 0.770000 ( 0.776638)
outer22 0.170000 0.000000 0.170000 ( 0.163393)
------------------------------------ total: 2.210000sec

                user system total real
outer11 0.490000 0.000000 0.490000 ( 0.491969)
outer12 0.400000 0.000000 0.400000 ( 0.396264)
outer21 0.760000 0.000000 0.760000 ( 0.764508)
outer22 0.160000 0.000000 0.160000 ( 0.161982)

···

--
      vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

(Matthias Luedtke) #4

James Edward Gray II wrote:

    traverse_inorder(@root){|x| block.call(x)}

traverse_inorder(@root, &block)

:wink:

Fair engouh, really straightforward. Thank you!

I'll not code when I'm too tired.
I'll not code...

:wink:

Hope that helps.

James Edward Gray II

Regards,
Matthias

···

On Aug 17, 2005, at 5:56 PM, Matthias Luedtke wrote:

(Brian Schröder) #5

Fair engouh, really straightforward. Thank you!

I'll not code when I'm too tired.
I'll not code when I'm too tired.
I'll not code when I'm too tired.
I'll not code...

:wink:

Hey, you know you can optimize this :wink:

puts("I'll not code when I'm too tired\n" * 100)

brian

···

--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/