Algorithmathon Day 1

Created: 12 July 2013  Modified:

Algorithms are an important part of programming that I so rarely use. Java, Ruby and most languages already take care the details for us. We just pull the class from the API and move on. Over the next several days we will attempt to code our own solutions using Ruby to write algorithms. I decided implement the venerable Single Linked List in Ruby. What Ruby code would be complete without RSpec to keep it inline. The algorithms in question will be to list the contents in forward and reverse order. You will find the code on GitHub

So first lets look at the RSpec

RSpec Results

bash$>  rspec

SingleLinkedListElement
  Class
    should have a 'next' method
    should have a 'data' method

SingleLinkedList
  Class
    should have method 'length'
    should have method 'add'
    should have method 'next'
    should have method 'list'
    should have method 'list_reverse'
  Instance
    should have a length of zero
    should have a length of four
    should not return nil when 'next()' is called
    should return 'one' when 'next().data' is called
    should return '["one", "two", "three", "four"]' when 'list()' is called
    should return '["four", "three", "two", "one"]' when 'list_reverse()' is called

Finished in 0.02251 seconds
13 examples, 0 failures

These show the expectations we have for our classes. Now lets look into the code.

single_linked_list_element.rb

class SingleLinkedListElement
  attr_accessor :next, :data
end

Ruby makes the element very easy. We just define our accessors and move on. Our list will be a little more involved.

single_linked_list.rb

require 'single_linked_list_element'

class SingleLinkedList
  attr_reader :length, :head, :tail, :current

  def initialize
    @length=0
  end

  def add(data)
    element = SingleLinkedListElement.new()
    element.data=data
    if @head.nil?
      @head=element
      @tail=element
      @current=element
    else
      @tail.next=element
      @tail=element
    end
    @length=@length+1
  end

  def next
    unless @current.nil?
      data = @current.data
      @current = @current.next
    end
    if block_given?
      yield data
    end
    data
  end

  def list
    last = @current
    @current = @head
    return_value = Array.new()
    while return_value.length < @length
      self.next {|data|
        return_value.push(data)
      }
    end
    @current = last
    return_value
  end


  def list_reverse
    last = @current
    @current = @head
    return_value = Array.new()
    reverse_by_recursion(return_value)
    @current = last
    return_value
  end

  private
    def reverse_by_recursion(values)
      local_element = self.next 
      unless local_element.nil?
        reverse_by_recursion(values)
        values.push(local_element)
      end
    end

end

Ruby’s closures allow us to write the code in the next and list methods. We can pass a block of code to the method which will populate our array for us. The list_reverse method uses recursion. Using the closure took 12 lines of code while using recursion took 15 lines of code. Let us further explore this and see if there is any time difference between the two options of solving the problem.

What about performance? Recursion seems to require less behind the scenes work and therefore might be faster. We can write an RSpec test to verify this.

single_linked_list_spec.rb

it "should take less time for list to run than list_no_recursion" do
  (1..1000).each { |a_number|
    @list.add(a_number.to_s)
  }

  start_time=Time.now
  @list.list_no_recursion()
  end_time=Time.now
  closure_time=end_time.to_f - start_time.to_f


  start_time=Time.now
  @list.list()
  end_time=Time.now
  recursion_time=end_time.to_f - start_time.to_f

  recursion_time.should > closure_time
end

This test turns out to be true! There is a measurable difference in favor of recursion. If we kick it up to 100000 we will see that recursion will give us a “stack level too deep” error. This is shown in the two following tests.

single_linked_list_spec.rb

it "should not raise error when using closure" do
  (1..100000).each { |a_number|
    @list.add(a_number.to_s)
  }

  lambda { @list.list_no_recursion()}.should_not raise_error
end

it "should raise error when using closure" do
  (1..100000).each { |a_number|
    @list.add(a_number.to_s)
  }

  lambda { @list.list()}.should raise_error
end

Thus using a closure with iteration allows us to handle larger data sets with a price on performance. Tail Call Optimization would likely solve this problem for us but it is not part of the Ruby specification and is not turned on by default in most Ruby Virtual Machines for performance reasons.

tags: Algorithm - Algorithmathon - RSpec - Ruby - Single Linked List
   Less Is More