-
-
Now available
-
Follow me
-
Download DB2
-
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.
Nov
27
Resolving the gray window when running db2setup
Filed Under DB2, Quick Tips | 5 Comments
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.
Oct
27
Integrating TextMate and Pygments
Filed Under General, Mac, Python, Quick Tips, Ruby | 1 Comment
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:
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.
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 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):
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.