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

Or rather, here are a couple of images. Sweet, Innocent images of Apple keyboards. The first of which has been left blank, for your enjoyment; the second is a rendition of the Dvorak layout on OS X (as best as I can map it – it seems to be correct on my MacBook)

These images are fairly harmless.  They go from being harmless to useful if you drop one of them into “/Applications/Mavis Beacon/Resources/English.lproj/Keyboard.png”.  (Substitute the correct path to Mavis Beacon if necessary, and don’t forget to back up the original keyboard image.)

Ok, Part 2 went pretty well.  At least I’m now looking at the correct layout on screen.  I’ll do a bit more work to neaten it up at some point but for now I’m happy it’s there at all.  Now if only it were possible to remap the positions of the keys themselves.  Stay tuned.

Hope this was helpful.

Self, Software dvorak, hack, typing

In order to cast off the shackles of messy typing I grabbed a copy of Mavis Beacon 2008 for Mac- only to discover on installation that Dvorak support has been dropped since version 5.  The website has this to say:

 
After installing Mavis Beacon Teaches Typing® 16, you want to know if practice lessons for the Dvorak keyboard layout are available in the program. The remainder of this note provides additional information.

The Dvorak layout is an alternate keyboard layout. Mavis Beacon Teaches Typing® 16 does not include lessons for the Dvorak keyboard layout.
 

Notice an interesting use of past tense in this statement but I guess I should have done the research first.  Who’d have known the #1 typing software didn’t support Dvorak?

Here is part one of a solution to fix the problem.  Downloading mb_abcdvorak will give all the lessons (1 – 29) of A Basic Course in Dvorak already converted to The Mavis Beacon custom lesson format.  You can import these by going to the Media Center.  If you wish you can also download txt_adbdvorak which simply contains the text for the lessons.  All I’ve done is the boring work of conversion – Many Thanks to Dan Wood for producing the course.

This is all well and good but when you are actually running Mavis Beacon that little helper keyboard still shows qwerty layout.  How can one get to the stage of learning the Dvorak layout without learn it separately first?  In Part 2 I will provide an alternative keyboard graphic using the Qwerty layout.  (I will peobably also explain how to use this within Mavis Beacon unless the EULA explicitly states not to – but providing a picture of a keyboard violates no EULA!)

Further to that I will investigate changing the positions of the keys used by the animated fingers and highlights which appear in the software.

Self, Software dvorak, hack, typing