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.

You drank the Kool-Aid and downloaded the awesomeness which is DB2 Express-C. Good job! Next you proceed to install it on Linux with sudo ./db2setup and boom, instead of a launchpad all you see is a gray window. Now what?

This problem is a known Java bug (resolved in Java 6) that shows up on Linux distros where Compiz effects are enabled. For example, this problem manifests itself in recent Ubuntu releases, including 8.10, where Compiz is enabled by default.

There are a couple of easy ways to solve this problem though. The first is to temporary disable these effects during the installation and turn them back on when you’ve finished installing. In Ubuntu, you can do this by clicking on the Appearance menu, Visual Effects tab and then selecting None. The second method is to run export AWT_TOOLKIT=MToolkit, before running sudo ./db2setup.

A new setup is in the works to solve this issue, but for the time being, you can use the workarounds above to install DB2 Express-C on Linux.

Like many, I don’t use TextMate just for coding. All of my posts are first drafted in my trusty editor before being published. One of the problems that I had, and that others probably face too, is the less than smooth process of publishing properly highlighted code in posts and HTML pages. A few solutions exist, including embedding gist snippets, using “Create HTML from Document” in TextMate, or adopting JavaScript libraries or WP plugins. But when it comes to highlighting code, for me Pygments is simply unbeatable.

Pygments is a Python library but ships as a command line tool as well. However, switching between TextMate and the command line is not as convenient as I’d like. So on the weekend I pulled out my big sharp razor and started yak shaving. The result of that brief session is a hack that delivers the integration of TextMate and Pygments, so that code can be easily converted to HTML in order to beautifully present it.

First, let’s see how I use it. When I select a snippet of Ruby code in TextMate and press ⌃⌥1 a snippet of code is transformed into the proper HTML. ⌃⌥2 is for Python snippets, ⌃⌥3 for any other language, and ⌃⌥4 for any language as well but with the option of adding line numbers. In practice, this means that I use 1 and 2 most of the time and these shortcuts are easy enough to remember. Note that this is not necessarily the best arrangement, but it works well for me. I could, if so inclined, associate all 4 commands to the same shortcut and be prompted by a menu every time this combination is pressed, obtaining something along the lines of the image shown below:

A possible prompt menu for Pygments

Should I ever forget these 4 shortcuts, I can take a quick look at the Text bundle menu shown below. I placed these commands under the Text menu, since they are globally available for textual formats, whether I’m composing HTML, Textile, Markdown or ReST; but this is entirely arbitrary and I suspect that many would consider the HTML menu instead or place a “Convert to HTML” entry in the menu of the specific language.

The Text menu

Ruby and Python deserve their own command because they are the languages whose code I publish the most, but pressing ⌃⌥3 (or 4) prompts a long list of languages to choose from as shown below (the image is cut to reduce its length):

The select a language dialog

The following are a series of steps that you can take to reproduce the same results as mine. The HTML required to present the code nicely in this section was generated from within TextMate. In other words, I’m eating my own dog food.

Step 1: If you haven’t done so already, install Pygments. You can get it from the official site.

Step 2: Within TextMate click on the menu entry: Bundles -> Bundle Editor -> Show Bundle Editor and click on the triangle to open up Text in the left pane.

Step 3: Click on the +- button in the lower left corner of the window and select New Command, then name the command Pygmentize Ruby (assuming that you want a command for Ruby).

Step 4: Ensure that each option for Save, Input, Output and Activation are the same as shown below (click to enlarge):

Step 5: Fill the Command(s) text area with the following code:

#!/usr/bin/env python

import os
import sys
from pygments import highlight
from pygments.lexers import RubyLexer
from pygments.formatters import HtmlFormatter

try:
    code = os.environ['TM_SELECTED_TEXT']
except KeyError:
    sys.exit()

formatter = HtmlFormatter()
print highlight(code, RubyLexer(), formatter)

Step 6: Repeat the process for Pygmentize Python, Pygmentize… and Pygmentize with line numbers… but select a different Activation key equivalent (replace 1 with 2, 3 and 4, respectively).

The command code for Pygmentize Python is as follows:

#!/usr/bin/env python

import os
import sys
from pygments import highlight
from pygments.lexers import PythonLexer
from pygments.formatters import HtmlFormatter

try:
    code = os.environ['TM_SELECTED_TEXT']
except KeyError:
    sys.exit()

formatter = HtmlFormatter()
print highlight(code, PythonLexer(), formatter)

For Pygmentize… use the following:

#!/usr/bin/env python

import os
import sys
from commands import getoutput
from pygments import highlight
from pygments.lexers import get_all_lexers, get_lexer_by_name
from pygments.formatters import HtmlFormatter

try:
    code = os.environ['TM_SELECTED_TEXT']
except KeyError:
    sys.exit()

available_languages = ", ".join(sorted('"'+lex[1][0]+'"' for lex in get_all_lexers()))
chosen_language = getoutput("""echo $(osascript <<'AS'
    tell app "TextMate"
        activate
        choose from list { %(languages)s } \
            with title "Pick a language" \
            with prompt "Select a language"
    end tell
AS)""" % {'languages':available_languages})
os.system("osascript -e 'tell app ""TextMate"" to activate' &>/dev/null &")

lexer = get_lexer_by_name(chosen_language.lower())
formatter = HtmlFormatter() # linenos=False
print highlight(code, lexer, formatter)

And finally for Pygmentize with line numbers… use the almost identical script below:

#!/usr/bin/env python

import os
import sys
from commands import getoutput
from pygments import highlight
from pygments.lexers import get_all_lexers, get_lexer_by_name
from pygments.formatters import HtmlFormatter

try:
    code = os.environ['TM_SELECTED_TEXT']
except KeyError:
    sys.exit()

available_languages = ", ".join(sorted('"'+lex[1][0]+'"' for lex in get_all_lexers()))
chosen_language = getoutput("""echo $(osascript <<'AS'
    tell app "TextMate"
        activate
        choose from list { %(languages)s } \
            with title "Pick a language" \
            with prompt "Select a language"
    end tell
AS)""" % {'languages':available_languages})
os.system("osascript -e 'tell app ""TextMate"" to activate' &>/dev/null &")

lexer = get_lexer_by_name(chosen_language.lower())
formatter = HtmlFormatter(linenos=True)
print highlight(code, lexer, formatter)

Step 7: Click on Text and by dragging and dropping arrange the menu to include the Pygmentize commands as shown below (click to enlarge):

Editing the Text menu

Step 8: At this point everything should work, whether you invoke the commands through a keyboard shortcut or through the Text menu. However, you will need to upload and include a Pygments stylesheet from within your site. To generate a stylesheet run the following from the command line:

pygmentize -S default -f html > pygmentize.css

In the above command, default is the name of the style. For example, the Python code you see in this article is styled with the style pastie (because I globally adopted that stylesheet for this site). For a comparison of the available styles check out this demo page.

Step 9: ????

Step 10: Profit!

I hope these hacked together commands can be useful to others. Feel free to customize them and improve upon them as it suits your needs.

UPDATE: I made a Pygments TextMate Bundle out of this.

Next Page →