Posts

About

Crystal vs Ruby - Part 3 (Knapsack Problem)

September 24, 2015

Introduction

In part 1 I introduced the Crystal programming, compared its compilation process to Ruby’s, and showed off its speed. In part 2 I compared how typing works in Ruby vs Crystal and explored some unique aspects of Crystal. In this post I will talk about implementing a solution to the knapsack problem in both Crystal and Ruby.

Knapsack Problem

After seeing how fast Crystal was for a computing fibonacci numbers compared to Ruby and learning more about how Crystal works, I decided to implement a brute force solution to the knapsack problem for both languages. In doing this I had several goals in mind. First I wanted to see what it was like to write larger programs using Crystal. I also wanted to see what it was like porting code from Ruby to Crystal since they are similar. Next I wanted to see what kind of testing frameworks are available for Crystal. Finally I wanted another example to show of the speed of Crystal.

I first started by implementing a brute force solution to the knapsack problem in Ruby. There isn’t anything too interesting about it. The basic idea of the brute force solution is to find all subsets of items that have a combined weight less than or equal to the knapsack’s weight, compute the profit for each of these, and then find the most profitable subset. You can see the implementation along with rspec tests here.

To try an see what it was like to port Ruby code into Crystal, I started my Crystal implementation by copying and pasting everything from Ruby. Next I investigated testing frameworks. Crystal actually has a testing framework called spec built in. It is very similar to Rspec 2 with describe, it, should, and other you may be use to. Since I was use to Rspec I decided to just stick with it. I also came across another testing library called spec2 which is almost exactly like Rspec 3 including let, expect, and others you may be familar with.

After I had my tests in place I was able to run them and see what problems my copy and pasted code had. First problem I ran into is that Crystal does not support keyword arguments which is unfortunate but and easy fix. Next I had an Item object held an id, weight, and value for each item. I had to change attr_reader in Ruby to the macro getter to generate getter methods for these instance variables. Next I had to give some types to some empty arrays since their types could not be inferred. So best_set = [] had to be changed to best_set = [] of Item. Finally Ruby has a nice built in method called combination for arrays that find all subsets of an array of a certain size. Unfortunately Crystal does not have this yet, so I had to implement my own.

def subsets_of_size(array, size)
    subset_helper(array, size, 0, [] of Item, [] of Array(Item))
end

def subset_helper(array, size, current_index, subset, accl)
    if size == subset.length
    accl << subset
    elsif current_index < array.length
    subset_with_current = subset.dup
    subset_with_current << array[current_index]
    subset_helper(array, size, current_index + 1, subset_with_current, accl)
    subset_helper(array, size, current_index + 1, subset, accl)
    end
    accl
end

I was also able to clean up some ugly injects used to sum weights and values of arrays of items using Crystal’s sum method.

Ruby

def sum_weight(subset)
    subset.inject(0) { |weight, item| weight + item.weight }
end

def sum_values(subset)
    subset.inject(0) { |values, item| values + item.value }
end

Crystal

def sum_weight(subset)
    subset.sum(&.weight)
end

def sum_profit(subset)
    subset.sum(&.value)
end

Overall it was very easy to port my Ruby implementation over to Crystal. The full Crystal solution can be seen here

After all that work and implementation, it was time to benchmark the two to see if Crystal is still faster than Ruby for larger programs. I benchmarked both implementations with sets of items of sizes 5, 10, 15, and 24. In all four tests Crystal was the clear winner. These benchmarks were done using ruby 2.2.0 and crystal 0.7.5.

Number of Items Ruby Time Crystal Time
5 0.2936 s 0.0050 s
10 0.1808 s 0.0095 s
15 0.2342 s 0.0874 s
24 68.6674 s 34.3023 s

Written by Jacob Oakes
I am a software architect who enjoys learning new things, clean code, and automated tests.