May

18

Memoization in Ruby and Python

Filed Under Python, Quick Tips, Ruby | 14 Comments

Wikipedia defines memoization as “an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs.”. This typically means caching the returning value of a function in a dictionary of sorts using the parameters passed to the function as a key. This is done in order to reuse that returning value immediately without calculating it again, when the function is invoked with the same arguments. Even though we are trading space for time, it is often invaluable for speeding up certain recursive functions and when dealing with dynamic programming where intermediate calls are often repeated many times.

Using memoization in Ruby is very easy thanks to the memoize gem. The first step to getting started is therefore to install it:

$ sudo gem install memoize
Successfully installed memoize-1.2.3
1 gem installed
Installing ri documentation for memoize-1.2.3...
Installing RDoc documentation for memoize-1.2.3...

Now we can use the memoize method as illustrated in the example below:

require 'rubygems'
require 'memoize'
require 'benchmark'
include Memoize

def fib(n)
  return n if n < 2
  fib(n-1) + fib(n-2)
end

Benchmark.bm(15) do |b|
  b.report("Regular fib:") { fib(35) }
  b.report("Memoized fib:") { memoize(:fib); fib(35)}
end

In the first block we simply invoke fib(35), while in the second one we first invoke the method memoize(:fib) to memoize the method fib. Running this code on my machine prints the following:

                     user     system      total        real
Regular fib:    55.230000   0.160000  55.390000 ( 55.819205)
Memoized fib:    0.000000   0.000000   0.000000 (  0.001305)

We went from almost a minute of run time to an instantaneous execution. Optionally we could even pass a file location to the function memoize and this would use marshaling to dump and load the cached values on/from disk.

For Python we can write a simple decorator that behaves in a similar manner. In its simplest form it can be implemented as follows:

# memoize.py

def memoize(function):
    cache = {}
    def decorated_function(*args):
        try:
            return cache[args]
        except KeyError:
            val = function(*args)
            cache[args] = val
            return val
    return decorated_function

Or more efficiently:

# memoize.py

def memoize(function):
    cache = {}
    def decorated_function(*args):
        if args in cache:
            return cache[args]
        else:
            val = function(*args)
            cache[args] = val
            return val
    return decorated_function

When the memoized function has been invoked, we look in the cache to see if an entry for the given arguments already exist. If it does, we immediately return that value. If not, we call the function, cache the results and return its returning value.

Truth be told, the limit of this approach lies in the fact that since we are using a dictionary, only immutable objects can be used as keys. For example, we can use a tuple but are not allowed to have a list as a parameter. For the example within this article, this approach will suffice, but to take advantage of memoization when using arguments that are mutable, you may want to consider the approach described in this recipe.

We can now rewrite the Ruby example above in Python as follows:

import timeit
from memoize import memoize

def fib1(n):
    if n < 2:
        return n
    else:
        return fib1(n-1) + fib1(n-2)

@memoize
def fib2(n):
    if n < 2:
        return n
    else:
        return fib2(n-1) + fib2(n-2)	

t1 = timeit.Timer("fib1(35)", "from __main__ import fib1")
print t1.timeit(1)
t2 = timeit.Timer("fib2(35)", "from __main__ import fib2")
print t2.timeit(1)

Running this code on my machine prints the following:

9.32223105431
0.000314950942993

In Python 2.5’s case by employing memoization we went from more than nine seconds of run time to an instantaneous result.

Granted we don’t write Fibonacci applications for a living, but the benefits and principles behind these examples still stand and can be applied to everyday programming whenever the opportunity, and above all the need, arises.

Apr

5

Better Software 2009 and Pycon Italia Tre

Filed Under Python, Startup | 1 Comment

In May I will be presenting at two conferences in Italy. The first is called Better Software 2009; it’s dedicated to the world of software development, Agile methodologies, Web 2.0 and a bunch of other buzzword compliant technologies. This conference will be held on May 6 and 7 in sunny Florence. If you speak Italian and happen to be in Europe, you can register here. Italian conferences tend to be fairly cheap, so you’ll be able to attend one day for 160 Euros or both days for 280 Euros. The price is even lower if you are a student or your company is purchasing multiple tickets. Also the first ten readers who register with the following coupon 3DNMFKNM will receive a 10% discount (I don’t receive commission for this). At “Better Software” I’ll be giving a talk about the world of startups.

Pycon Italia 3If you don’t speak Italian, you may still be interested in the second conference which is being held at the same hotel in Florence from May 8 to the 10th. The main track of Pycon Italia Tre, is in fact, being simultaneously translated into/from English/Italian. I will be presenting a spin-off that’s geared towards Python, of the talk I’m giving giving at Better Software at this conference, which will feature the very provocative title “Getting rich with Python”. Most of the audience will be composed of Italian speakers, so I’ll be presenting in my mother tongue and a real-time English translation will be provided. I’ll be among some notable company at Pycon Italia, such as Guido van Rossum, Alex Martelli (Google), Raymond Hettinger, David Boddie (QT Software), Ariya Hidayat (QT Software) and Fredrik Lundh (aka effbot), who will be speaking publically about Unladen Swallow (Google’s LLVM-based upcoming project that’s geared towards drastically improving the speed of CPython) for the first time ever. With the exception of Alex (who like myself, will be speaking Italian and have his presentation translated in English), all of the names above will be presenting in English (with a translation in Italian to be provided for those who require it).

Whatever your language, if you are in Europe, Pycon Italia Tre is definitely worth attending, especially when you consider the ridiculously low admission price (€60 for non-students or €40 for students, including tax) - which includes two buffet lunches, four coffee breaks, free Wi-Fi access, a free T-Shirt, free gadgets and randomly selected prizes. Plus, there will be all sorts of social activities and opportunities to hang out. If you plan to attend, register now before all the tickets have sold out.

I hope to see, and have the chance to meet, you in Florence!

Mar

23

Ruby’s Biggest Challenge for 2009

Filed Under Python, Ruby | 39 Comments

According to the TIOBE index, Ruby is holding its own in the 11th position, sandwiched between Delphi and D. Meanwhile, its “cousin” Python has jumped up in rank and is currently the 6th most popular programming language in the world, beating out C#, JavaScript and Perl. Ruby’s exponential growth appears to have truly slowed down. Even if we disregard the TIOBE Index or view it as being entirely inaccurate, there are other factors that indicate a lull in Ruby’s popularity. For example, at the end of 2005, thanks to Rails, Ruby book sales surpassed Python and were up by a hefty 1552%. Yet, according to this post on the O’Reilly radar, Ruby was the language with the biggest decline in unit sales during 2008, dropping out of the top 10 languages and moving from a 5.39% market share in 2007 to just 3.51% in 2008.

So is this decline in interest for the language, Ruby’s biggest challenge to overcome in 2009? I don’t believe so. I’d venture to guess that most developers have heard of Ruby by now, and I think it’s fair to say that as a community, we’ve attracted a lot of attention towards Ruby over the past few years. The Ruby word is clearly out. As Ruby moves forward, organic growth is expected and the numbers above shouldn’t scare you in the least.

Ruby’s challenge for 2009 is not about adoption, marketing or - to adapt a term from the Christian vernacular - trying to convince other developers to accept Ruby into their hearts. The real challenge will be technical, namely moving away from the main Ruby 1.8 interpreter.

Historically, Ruby has been an exceptionally well designed programming language with a very lousy implementation. Some of the main issues surrounding MRI are common knowledge: memory hungry when compared to other scripting languages, extremely slow, lack of native threads, and lack of support for Unicode.

Ruby 1.9.1 resolves these issues though. As such, we as a community should really make an effort to get rid of our MRI baggage and move forward as quickly as possible to embrace Ruby 1.9.x. The payoff is an improved language with a faster and “less memory intensive” VM, as well as native threads (albeit with GIL) and support for multi-byte strings. There’s no reason to look at the past. A stable version is available and we should all be using it.

In practice, very few people have switched to Ruby 1.9. Some developers wrongly believe that Ruby 1.9 is just one intermediary step to Ruby 2.0, and as such it’s not meant to be used in production. Better communication could have avoided this common misconception. More importantly though, developers are not using Ruby 1.9 because there are very few libraries that work with it.

The Rails team is a notable exception, having placed a lot of effort into a release (2.3) that works completely with Ruby 1.9.1. But most libraries, gems and plugins won’t work with it, so inevitably Rails on Ruby 1.9.1 loses a lot of its initial appeal.

Unlike in the Python community where Python 3 is seen as an improvement to the language (Python 2.5/2.6 are perfectly fine for the time being) the Ruby community doesn’t have this sort of “luxury”. We finally have the chance to eliminate the root causes behind the harsh criticism that Ruby is sometimes subjected to, and to have a good implementation at our disposal. All we have to do is make a swift switch to Ruby 1.9.

To achieve this worthy goal I urge project owners to report compatibility with Ruby 1.9.1 information in their README files. I realize that this is open source and that doing so is a voluntary effort, but I truly think that Ruby 1.9.1 should be seen as a priority by the community as a collective whole. If you are not a project owner, you can still help by testing active libraries with Ruby 1.9.1 and informing the author of the library you test of your findings. Those who are able to, could also submit a patch that would enable those projects to work with the latest version of Ruby.

In truth, it wouldn’t be a bad idea to keep a list, perhaps within a wiki, of projects that have already been ported to Ruby 1.9 and that have been tested/confirmed as working. This switch to Ruby 1.9.1 can also act as a reset button when it comes to getting rid of many of the old, unmaintained, half-assed attempts from N years ago. Porting to Ruby 1.9.1 could act as a rough, implicit line of distinction between active and inactive projects.

I don’t know if this is an open letter to the Ruby community per se, but you could view it as such, as I feel that the topic of switching to Ruby 1.9.1 is one of vital importance for us Rubyists. If you agree with this point and assessment of the situation, please consider spreading the word, sharing your thoughts, and linking to this post.

When new developers come to the Ruby world, lets greet them with Ruby 1.9.x. In the long term, doing so will improve our growth as a community more than any marketing effort ever could (and the two efforts are not mutually exclusive either). Ultimately, Ruby’s biggest challenge may just be our greatest opportunity to improve.

Next Page →