12 July 2013

Algorithmathon

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

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

Class
should have method 'length'
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.

``````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.

``````require 'single_linked_list_element'

def initialize
@length=0
end

element.data=data
@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
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
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.

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

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.

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

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

it "should raise error when using closure" do
(1..100000).each { |a_number|