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
These show the expectations we have for our classes. Now lets look into the code.
Ruby makes the element very easy. We just define our accessors and move on. Our list will be a little more involved.
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.
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.
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