The Artima Developer Community
Sponsored Link

Ruby Buzz Forum
Kata Two Worked (continued) -- Recursive Binary Chop

0 replies on 1 page.

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic    
Flat View: This topic has 0 replies on 1 page
Jim Weirich

Posts: 351
Nickname: jimw
Registered: Jul, 2003

Jim Weirich is a long time software developer and a relatively recent Ruby enthusiast.
Kata Two Worked (continued) -- Recursive Binary Chop Posted: Jul 5, 2003 7:14 PM
Reply to this message Reply

This post originated from an RSS feed registered with Ruby Buzz by Jim Weirich.
Original Post: Kata Two Worked (continued) -- Recursive Binary Chop
Feed Title: { | one, step, back | }
Feed URL: http://onestepback.org/index.cgi/synopsis.rss
Feed Description: Jim Weirich's Blog on Software Development, Ruby, and whatever else sparks his interest.
Latest Ruby Buzz Posts
Latest Ruby Buzz Posts by Jim Weirich
Latest Posts From { | one, step, back | }

Advertisement
This is a continuation of the KataTwoVariation1 posting where we are trying different methods of implementing a binary search. In the first version we discussed an iterative approach and using loop invariants. In this second installment we cover the the recursive versions. (see Kata Two for background information)

Variation #2: Recursive

This is a standard recursive implementation of the algorithm we looked at in KataTwoVariation1. This version determines which half of the array contains our target value and recurses on the appropriate half of the array.

Code

Here’s the code …

  def chop_recursive(target, list, offset=0)
    if list.size <= 1
      (list[0] == target) ? offset : -1
    end
    mid = list.size/2
    if list[mid] > target
      chop_recursive(target, list[0...mid], offset)
    else
      chop_recursive(target, list[mid..-1], offset+mid)
    end
  end

  class TestChopRecursive < Test::Unit::TestCase
    alias chop chop_recursive
    include ChopTests
  end

Problems Encountered

In writing this version, I encountered the following issues …

  • I had a problem where I miscalculated the array fragment to recurse on. The miscalculation led to a recursive call where the size of the array wasn’t decreased, and led to infinite recursion.
  • Since a copy of the array is passed, we lose information on the position of the target value in the full array. I had to pass in the offset of the of start of the array fragment to correct for this.
  • I refactored the method to return nil (instead of -1) when the target value was not found. I decided that it didn’t help improve the logic in any way, so I put the -1 return value back in.
  • There was a performance bug where I searched both branches of the array (and then returned the one that matched).
  • The size==1 test really bugs me. I made several (unsuccessful) attempts to get rid if it. (But see the next item)
  • The original version of the recursive version started with …
      def chop_recursive(target, list, offset=0)
        return -1 if list.empty?
        return offset if list[0] == target
        return -1 if list.size == 1
        ...
    

    This version tests list[0] agains target at the entry to every recursive call. This is wrong. I should only test when the list is down to one element. This defect made it into the original posting and it wasn’t until I was reviewing the code for the CPS post that I discovered the error. It also might explain my discomfort with the list.size==1 test. It was actually the list.empty? test that was incorrect and the size check evolved to list.size <= 1.

Variation #3: Recursive with Explicit Limits

In variation 2, I decided to pass a copy of the sub-array in each recursive call. This is an expensive operation, but I was thinking that I could avoid passing around explicit limits this way. However, it turned out that I still needed to pass the offset, negating much of the advantage.

In variation 3 we will avoid makeing array copies by always passing the original array around. Instead of arrays, we will explicitly pass the hi/lo limits of the sub-array in the recursive call.

I think this version is not only more efficient than variation 2, it is also easier to read and understand.

Notice that the recursive call in this version takes 4 parameters, so I created a helper function (rchoplim) with the proper signature to do the recursion.

Code

Here’s the code …

  def chop_recursive_passing_limits(target, list)
    rchoplim(target, list, 0, list.size)
  end

  def rchoplim(target, list, lo, hi)
    if (hi-lo) <= 1
      list[lo] == target ? lo : -1
    else
      mid = (lo+hi) / 2
      if list[mid] > target
        rchoplim(target, list, lo, mid)
      else
        rchoplim(target, list, mid, hi)
      end
    end
  end
  class TestChopRecursiveWithLimits < Test::Unit::TestCase
    alias chop chop_recursive_passing_limits
    include ChopTests
  end

Problems Encountered

There were no problems encountered while implementing Variation 3. I think the simpler logic helped (plus I worked out a number of bugs in Variation 2).

Things to Come

In the next installment, we will explore a CPS (Continuation Passing Style) implementation.

Read: Kata Two Worked (continued) -- Recursive Binary Chop

Topic: Drb Over SSL and QuickCert Previous Topic    

Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use