3
\$\begingroup\$

I am relatively new to Ruby and am trying to get a handle on making my code more Ruby-esque. At the same time I am experimenting with the branch and bound algorithm to solve a problem that I outline in this blog post. I would also welcome any feedback on the quality of my implementation. The full source code is on my github here, but here is the code for the branch bound class:

require './widget'
require './requirements'
require 'benchmark'

class BranchBoundSearch
  @best_score = nil
  @best_combos = []

  def initialize(scorer, main_requirement_label, all_possible)
    @scorer = scorer
    @main_requirement_label = main_requirement_label
    @all_possible = all_possible
  end

  # Given a widget_array first calculate it's score, and add it as a branch in the
  # list of branches based on the quality of it's score. Better scores are first.
  # Branches that do not meet the size requirement are not added to the branches
  # array. This effectively kills that branch.
  def add_branch(widget_array, branches)
    score_hash = @scorer.get_score_hash(widget_array)
    score = @scorer.get_total_score(score_hash)
    added = false
    branches_index = 0

    if score_hash[@main_requirement_label] >= 0 
      while not added and branches_index < branches.length do
        if @scorer.get_better_score(score, branches[branches_index][1]) >= 0
            branches.insert(branches_index, [score_hash,score,widget_array])
            added = true
        end
        branches_index += 1
      end

      if not added
        branches.push([score_hash, score,widget_array])
      end
    end
  end

  # Branch and bound recursive search. Provided an in array which represents the
  # node which will be branched off of. Roughly, the function first creates a list
  # of potential branches which are ordered by the quality of their score.
  # Potential branches are then looped through, if a potential branch is viable the
  # function is called again with it as the root node. This continues until
  # exhaustion of all possiblities.

  def branch_and_bound(in_array)
    branches = []
    @all_possible.each do |widget|
      branch_array = in_array + [widget]
      add_branch(branch_array, branches)  
    end

    branches.each do |branch|
      score_hash = branch[0]
      score = branch[1]
      widget_array = branch[2]
      score_comparison = @scorer.get_better_score(score, @best_score)

      if score_comparison == 0 
        @best_combos.push(widget_array)
        continue_branch_investigation = true
      elsif score_comparison == 1
        @best_combos = [widget_array]
        @best_score = score
        continue_branch_investigation = true
      elsif score > 0 
          continue_branch_investigation = true
      end

      if continue_branch_investigation
        branch_and_bound(widget_array)
      end
    end
  end

  def get_best_score()
    return @best_score, @best_combos
  end
end

I'm also concerned about this specific code block:

best_score_90 = nil
best_set_90 = []
best_score_90_bb = nil
best_set_90_bb = []
best_score_400 = nil
best_set_400 = []
best_score_400_bb = nil
best_set_400_bb = []
time=Benchmark.bm(7) do |x|
  x.report("brute[90]:") do
    scorer = Scorer.new(requirements_90, :size)
    brute = BruteSearch.new(scorer, :size)
    possible_combos = brute.enumerate_possible([], all_widgets.dup)
    best_score_90, best_set_90 = brute.get_best_score
  end

  x.report("brute[400]:") do
    scorer = Scorer.new(requirements_400, :size)
    brute = BruteSearch.new(scorer, :size)
    possible_combos = brute.enumerate_possible([], all_widgets.dup)
    best_score_400, best_set_400 = brute.get_best_score
  end

  x.report("b&b[90]:") do
    scorer = Scorer.new(requirements_90, :size)
    bb = BranchBoundSearch.new(scorer, :size, all_widgets)
    bb.branch_and_bound([])
    best_score_90_bb, best_set_90_bb = bb.get_best_score
  end
  x.report("b&b[400]:") do
    scorer = Scorer.new(requirements_400, :size)
    bb = BranchBoundSearch.new(scorer, :size, all_widgets)
    bb.branch_and_bound([])
    best_score_400_bb, best_set_400_bb = bb.get_best_score
  end
end

puts "Best set [90] brute: " + widget_array_to_s(best_set_90)
puts "Score[90] brute: " + best_score_90.to_s

Thanks for the help!

\$\endgroup\$
  • \$\begingroup\$ A note from experience: if you ask to review so many LOC, chances are nobody will answer, too much work. Maybe you can reduce it to a method you're specially worried about. \$\endgroup\$ – tokland May 16 '13 at 21:01
  • 1
    \$\begingroup\$ This is just a style suggestion, but please do use the spacebar a little more. It is more "Ruby'esque" to write x = y and foo(bar, baz), instead of x=y, foo(bar,baz). Same with commented lines: # comment instead of #comment. Last tip: Generally speaking, array variables are plural nouns, so widgets instead of widget_array. This naming scheme is why Ruby's Array has a method called include?. The line widgets.include?(x) makes grammatical sense, while widget_array.include?(x) doesn't really. \$\endgroup\$ – Flambino May 16 '13 at 21:01
  • \$\begingroup\$ Small thing but you don't need to write return in get_best_score. Result of last evaluation is returned by default in Ruby. \$\endgroup\$ – Mike Szyndel Jul 14 '13 at 20:07
  • \$\begingroup\$ Is there any case when this will be false (or nil)? continue_branch_investigation \$\endgroup\$ – Mike Szyndel Jul 14 '13 at 20:22
1
\$\begingroup\$

One thing that will help a lot is using attr_accessor. You can use is so that you don't have so many instance variables littering your methods. You can also initialize best_score and best_combos and give them default values. (But generally, according to Sandi Metz, you should try to avoid passing in more than 4 arguments to any method.) Also, avoid if not. Opt instead for unless.

class BranchBoundSearch

  attr_accessor :scorer, :main_requirement_label, :all_possible, :best_score, :best_combos

  def initialize(scorer, main_requirement_label, all_possible, best_score=, best_combos)
    @scorer = scorer
    @main_requirement_label = main_requirement_label
    @all_possible = all_possible
    @best_score = nil
    @best_combos = []
  end
  # That way, you have access to scorer without calling @scorer.
  def add_branch(widget_array, branches)
    score_hash = scorer.get_score_hash(widget_array)
    score      = scorer.get_total_score(score_hash)
  ...
  unless added
    branches.push([score_hash,score,widget_array])
  end
  ...

That will get you at least some of the way, but you did post quite a bit of code.

\$\endgroup\$
0
\$\begingroup\$

Replace this

branches.each do |branch|
  score_hash = branch[0]
  score = branch[1]
  widget_array = branch[2]
  ...

with

branches.each do |score_hash, score, widget_array|
  ...

This one

if score_comparison == 0 
  ...
elsif score_comparison == 1
  ...
elsif score > 0 
  ...
end

with

case score_comparison
  when 0
    ...
  when 1
    ...
  else
    ...
end

You pass a param but there's no reason for it

add_branch(branch_array, branches)

because you may make branches an instance variable @branches.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.