Graph::Function, a gem for graphing functions
When I do katas I often do several iterations with a focus on performance. I think this is probably pretty common. You start off with some quadratic solution, ponder a bit, and then try to get down to linear or n log n performance^{1}.
But there’s also stuff like, in Ruby at least, discovering the cost of dynamic Array allocation in the execution of your algorithm. In other words sometimes you forget your language has some abstractions that have real costs.
Although I’d like to also get better at algorithmic analysis from a purely formal place, in the meantime I’ve found graphing functions super useful. I found it so useful that I’ve written a gem, Graph::Function, to make it easier to pop a comparison into an exercise I’m working on.
Here’s an example of using the library with some exercise code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
require 'graph/function'
Graph::Function.as_gif(File.expand_path('../comparing.gif', __FILE__))
def bubble_sort(array)
n = array.length
loop do
swapped = false
(n1).times do i
if array[i] > array[i+1]
array[i], array[i+1] = array[i+1], array[i]
swapped = true
end
end
break if not swapped
end
array
end
def sort(array)
array.sort
end
Graph::Function::IntsComparison.of(method(:sort), method(:bubble_sort))
And here’s the graph we generated:
As you can see, implementing bubble_sort
yourself doesn’t run as fast as
Ruby’s own sort
. (Hopefully not too surprising.) But it was very easy to
generate a helpful graph to demonstrate that, right?
I hope you’ll get some utility out of this gem, and if you have any thoughts about its direction feel free to discuss it in the issues.

I’m realizing as I think about it very few of the exercises are ever worse performing than that. It’s rare to get an actual permutations problem that requires exponential time. Why is that? Perhaps just because NP problems are trickier to solve, and often only approximated. I think subset sum is the only problem in that class I’ve done yet. ↩