Stuart Hacking

Just some stuff I thought about today. Here’s a fibonacci function expressed in Lisp:

It can be used to compute the fibonacci sequence:

It’s simplicity is elegant, but, frightfully inefficient. In fact, the recursive definition of fibonacci is often used as an example of an inefficient method. Let’s look at why it’s poor. When fibonacci is called for a value of n there are two possible paths the program can take:

1. If n <= 1 give back the value of n
2. otherwise return the sum of the previous two numbers in the sequence

So, if n is 0 or 1 then the value is simply 0 or 1 respectively. This is the base case of the function. In other words, from this piece of concrete knowledge, we can derive the remaining values. If n is any value higher than 1, then we need to actually compute what it is. Notice that this case requires fibonacci to be called another two times.

This imposes significant overhead on the machine. In addition to this, the results of these two function calls must be added together. That means we need to hold onto some space in memory to store the results. Simplistically, we refer to the number of significant function calls as the time complexity of the program, and the amount of memory required as the space complexity. Fibonacci sure is expensive.

Anyway, this got me to thinking. What is the main problem with fibonacci? It’s the fact that it must repeat a lot of its calculations. If we want to find the value of Fib(5), we must call Fib(4) and Fib(3). But wait: To find the value of Fib(4) we must call Fib(3). Hence, we do the same operation twice. What if we could tell the program to remember a value once it had been found? Wouldn’t this speed things up? Can this be done without sacrificing the simplicity of a recursive method?

Here’s a modified, partial fibonacci function:

This one is a little more involved, but don’t panic: It still does the same thing, in much the same way. It has an extra trick though: Before it attempts to compute the value of n, it check to see if it already has a value. It looks in a structure called a hash table (any type of lookup table should do). Think of this like a telephone directory. If you know someone’s name, you can look it up in a phone directory and it will tell you their number. In our hash table, if you know a value of n, you can look it up and find its fibonacci value. Of course, some fibonacci values won’t be listed just yet. If there is no value in the table, we continue with our normal process: If n <= 2 then return 1. If n is greater than 2 then we find it’s value by adding the previous 2 fibonacci numbers. Now we have one more change to make: Having just found this new value of Fib(n) we store it in the hashtable. This means we won’t have to do the hard work of finding it again later – It’s already there!

Now, this act of remembering our previous work means that we must use a bit more memory, but the gain is a remarkable improvement in speed. Today, memory is pretty cheap, so this is not a bad thing. Look at the method we used. We start with a function that must call itself with a smaller value in order to discover a new value. When we discover a new value, we store it in a table so that we can quickly find it later.

This could most likely be generalised for any function that follows this pattern. There’s another blog post for when I get time to look into that aspect of it. If this post was about the optimisation, the next will be about abstracting that into a common pattern.

I hope this was of some interest. It was just a little thing I thought about this afternoon then decided to try it out. After I tried it I thought it might make a quick, informal blog entry.

Update: It seems that I have inadvertently stumbled across the definition of memoization which was conceived in 1968! It’s fun to try something out and then learn about a formal definition of the same principle. The act of developing an example gives it more meaning. (Further reading: http://en.wikipedia.org/wiki/Memoization).

Programming Computers, Emacs, hack, lisp, memoization, Programming

Recently , I’ve come to rely on Emacs for more or less everything I do on a computer. Of course, in work there are some exceptions: We must use Outlook for emails (the bulk), various windows only business tools (the cruft), etc.

But, as far as possible I will use Emacs because I love the simplicity, speed and extensibility.

In particular, I have discovered org-mode which has now taken over my personal scheduling routine. Org-mode is a personal planner for emacs which allows the user to: Create todo lists, schedule items for certain dates, mark items complete, use checklists, add tables. It’s impressive the amount of features this small, text-based operating system can offer.

So here’s some quickie hacks I’ve started working at for org mode. My wishlist is as follows:

• [X] Store all org-mode schedules together
• [X] Custom org save function (facilitating above)
• [   ] Strip TODO/BUG/FIXME lines from source code and:
  • Store in org file called “<project name>”
  • insert links back to source file
  • add tags based on: language, filename, type

The third item is still in progress but I’ll explain my current org setup now and provide some expressions for the customisation:

;; Org Mode
(global-set-key "\C-cl" 'org-store-link)
(global-set-key "\C-ca" 'org-agenda)
(add-to-list 'auto-mode-alist '("\\.org$" . org-mode))
(setq org-log-done t) ;timestamp on completion

The first two lines create global keyboard shortcuts (key-bindings) which are available from anywhere within Emacs. ‘Ctrl-c l’ will store a link to a url or file, ‘Ctrl-c a’ will open your org-mode agenda (where you can view your calendar, appointments, todo items. This is the thing I have come to rely on )

the add-to-list command tells Emacs to use org-mode by default for any file with a .org extension. the last line sets the org-log-done variable to true: This means that when we mark a todo item as complete it will be timestamped with the completion date. I like this feature.

So that’s just a bit of simple customisation. Now I’ll add a couple of functions that take care of saving my tasks.

(setq org-mode-file-dir "~/.emacs.d/org-files")
(setq org-agenda-files (append (list org-mode-file-dir)
org-agenda-files))

These two functions set variables telling emacs where to find org-mode files containing agenda items. The first is my own private directory added to behave as a default location for saving.

(defun smh-org-mode-save-buffer ()
(interactive)
(if (equal nil (buffer-filename))
(let ((input (read-from-minibuffer "Org Topic: " (buffer-name))))
(write-file (concat org-mode-file-dir input ".org")))
(save-buffer)))

Next I added a custom save function which simplifies the process of saving. If the current buffer is not already linked to a file (buffer-filename is nil) then it will prompt for an Org Topic. I like to think of organising things by topic. The default topic will be the name of the buffer if you supplied one previously. When a topic is given it will store the file as .org in the org-mode-file-dir. One the other hand, if the buffer is already linked to a file it will simple save as normal.

(add-hook 'org-mode-hook
(lambda () (define-key 'org-mode-map "\C-x\C-s"
'smh-org-mode-save-buffer)))

Finally I created a mode-specific key binding: I do this by adding a hook to org-mode… This means whenever org-mode gets called the hooked functions will also be evaluated. I have redefined the ‘save’ keystroke for org-mode to call my custom save function.

This is what I have so far and I find it quite helpful for organising Tasks and Todos manually.  My next step is to analyse source code and look for TODO, BUG or FIXME lines and create org-mode files automatically.

Programming Emacs, GNU, hack, integration, lisp, Org-mode, Programming, Software

This is a test post using weblogger.el for Aquamacs 1.6*. If it works
I’ll probably use it as my main offline blogging client.

Aquamacs is a Mac port of the popular multi-purpose program
Emacs. Emacs is used for many purposes such as tetris, email,
calendar and organiser…. There are even rumours that it can be used
for editing text!

Self, Software cool, Emacs, fun, Software