Categories
Software

Software Craftsmanship 2009

Last Thursday I attended the SC2009 conference at the BBC Media Centre in London. Here are a few notes (assuming I get round to finishing the post – I see I still have an unfinished draft about a session from XPDay2007).

MappingPersonal Practices (Ade Oshineye)

This was a simple exercise where everyone spent five minutes drawing a mind-map of the software development practices they find most important to them, then spent 90 seconds each listing and describing them. The intention was to then go round again and say which practices you’d heard others mention that you wanted to try, but time ran out.

Here’s my selection, converted to Graphviz to save you the pain of trying to decipher my handwriting:

Personal practices

Of the practices mentioned by others, the ones I noted down that I ought to try are speaking at conferences, learning other languages (I haven’t played with a new one for a while), getting feedback from others in the team and reading classic journal papers (conveniently Michael Feathers has just posted a list of recommended ones).

Ruby Kata & Sparring (Micah Martin)

Micah (who had come all the way from Chicago just for this conference!) described the coding kata, linking it to the martial arts practice from which the idea was taken. Trivia fact: the name of Micah’s company, 8th Light, is the literal translation of Hakkoryu, the school of Jujitsu that Micah followed.

He mentioned two different views of katas: Dave Thomas’s suggestion to practice solving the same problem many times and reflect on what you are learning, and Uncle Bob Martin’s approach where you watch a master solve the problem and mimic their process (the latter seems closer to the practice of kata in martial arts). Micah suggested that both of these are missing an important aspect of martial art kata: performance.

Performing a code kata in front of other craftsman gives you a purpose for practicing it. You can receive feedback, learn and address your weaknesses and measure your skill against others, and it shows respect for the craft.

Micah performed a code kata himself, implementing Langston’s Ant in Ruby and asking for a score out of ten at the end (most people gave seven or eight). Finally he mentioned sparring as another technique borrowed from martial arts, and talked about the Battleship tournament which he set up. Apparently this will be repeated soon, using Hangman as the problem to solve.

If you want to see more, there’s a video of Micah making the same presentation at RubyConf 2008, and also a screencast of the Langston’s Ant kata.

Three Paradigms: Taking An Extreme Position on Code Style in a Safe Environment (Keith Braithwaite)

The purpose of this session was to take a piece of contrived “enterprisey” code, make three separate refactorings on it and see what effect they had on the ease of making changes to the code. The refactorings were basically removing conditional logic, removing getters and setters, and making certain classes unmodifiable.

The example code was available in Java and C# (the so-called country-and-western languages – “We got both kinds…”). Unfortunately, like many people there my Java skills were a bit rusty (and my C# skills non-existent), so by the time I’d grabbed the code off one of the memory sticks that were floating round, set up a project in Eclipse, realised that I didn’t have junit.jar and found someone to copy it from, I didn’t really have enough time to complete any of the refactorings. I also spent a while puzzling over what the purpose of the UserDTO class was, as it seemed like it would have been easier to just pass User objects around. Turns out that the point was to show that there was no point (if you see what I mean). Fortunately I seem to have avoided being exposed to the kind of pattern-obsessed enterprise code where these useless nojos are considered good practice. It doesn’t surprise me though – to quote Keith, “Curly bracket languages make you stupid”.

I don’t think anyone got as far as finishing all the refactorings, or making behavioural changes to the resulting code, but there was some interesting discussion about ways to achieve the various refactorings (including one person who admitted to removing getters and setters by making the fields public!) It’s a shame there wasn’t a bit more time available.

Responsibility-driven Design with Mock Objects (Willem van den Ende & Marc Evers)

This was a quick introduction to the use of mock objects as a design tool (refreshingly a show of hands indicated that everyone present practiced TDD, and most used mocks), followed by a randori-style session (in Ruby, by popular vote) designing some classes for a simple adventure game.

As with the previous session, time constraints meant that we didn’t progress that far with the code, but there was a lot of discussion around various design decisions, which of course is the really valuable part of this kind of exercise. A lot of this was kicked off by Steve Freeman (co-inventor of mock objects, and co-author of the excellent Mock Roles, not Objects, where the proper use of mocks is explained), who piped up when someone suggested moving when there was some debate about the correct name for a method. From what I can remember, his comment was something along the lines of “No! Getting the right names for things is the whole point – if you aren’t going to do that, you might as well not bother!” I was reminded of the quote from Phil Karlton: “There are only two hard problems in Computer Science: cache invalidation and naming things.”

The main thing I took away from this session was some confirmation that the way I currently try to do TDD with mocks is fairly close to what seems to be considered good practice. Interestingly the number of people who agreed that the techniques shown were similar to how they currently used mocks was a fraction of the number that had earlier identified themselves as mock users, but unfortunately there wasn’t time to find out how their approaches differed.

My Defining Moments (Steve Freeman)

This was similar in a way to Ade’s, but instead of everyone talking for 90 seconds about their personal practices, a dozen or so volunteers talked for up to five minutes about a ‘breakthrough experience’ where they’ve learned something important, and how that breakthrough happened. Here are some of the ones I noted down (apologies if I’ve misrepresented anyone, but I only wrote down a few words for each and I may have forgotten the details):

Steve himself talked about when he was at DEC, where ‘everything just worked’. He described the best sysadmins he’d ever seen, who would, unasked, perform ‘random acts of helpfulness’. The main lesson he learnt from this was that despite the mediocrity found in most organisations, it was possible to be that good if you had the right people.

Micah described how some ways of working when he joined ObjectMentor hadn’t felt quite right to him, and his realisation that in the end you can’t impose one person’s standards on another: we all have to develop our own which we’re comfortable with.

Ade talked about his first project at ThoughtWorks. He described how his boss had shouted at him in a client meeting for describing himself as “just a developer”. His main point though was about working with a team of developers from Dixons, whose sole Java experience was a two-week course from Dan North. Obviously the lack of experience wasn’t ideal, but the fact that they’d learnt everything they knew from Dan meant that they only knew the right way to do things. For example if you suggested to them that something was too simple to need a test, they’d say “No, you have to start with a test!”

Willem van den Ende described an internship spent refactoring a hideous, bug-ridden, copy-and-pasted mudball of GUI code, which contained 40,000 lines of code and which no-one dared touch. In four months, by slowly removing duplication and cleaning up the code, he reduced it to a tenth of the size. He also found that he fixed most of the bugs without really trying, as a side-effect of removing duplication. The original code had taken two people three months to write.

Gojko Adzic talked about a project for the National Grid, where a graphical map view they’d added at the end of the project was by far the most popular feature of the software, despite the fact that the customer hadn’t asked for it. He highlighted the discrepancy between this and the common agile view that says you should only work on features (user stories) that the customer has explicitly asked for. My take on this would be that it’s part of the developers’ job to propose new or alternative solutions to the customer, but generally you should still get their agreement.

Finally John Daniels talked about a ‘lightbulb moment’ when moving from ADA to Smalltalk, where he suddenly understood what OO was really about. He said it was 20 years before he saw another language with a development environment as good as the Smalltalk one (something I’ve heard from others too).

I didn’t put my name down to talk, but for the record my defining moment would have actually have been a couple of events which have influenced my understanding and practice of TDD. From my initial one-test-per-method attempts at unit testing, reading about TestDox and RSpec introduced me to the idea of tests as specification. Then there were a couple of sessions from XPDay06, especially Are your tests really driving your development, which made me realise that my tests still weren’t expressing intent as well as they could have done. Finally the aforementioned Mock Roles, not Objects showed me the right way to use mocks and stubs.

Test-driven Development of Asynchronous Systems (Nat Pryce)

I’d already read the notes from this presentation, which Nat originally gave at XPDay08, but seeing the talk in person made it much clearer. I don’t think there’s much I can add to the notes.

General observations

Firstly, it was great to spend a day with a hundred-odd people who obviously cared about their work (not just their career) as software developers. The other thing that struck me was that, despite this not being explicitly an Agile or XP conference, it seemed to be taken for granted that practices like TDD and refactoring were basic necessities, not optional extras.

More randomly, there were far more non-Apple laptops in evidence than you would see at a Ruby conference or a Barcamp, presumably because a lot of delegates work for large companies and brought their work laptop. That said, most of the ones I saw seemed to be running Linux rather than Windows, but I wasn’t keeping count. More Java and .NET people too, although a fair proportion working in Ruby and other languages. On the phone front though, I don’t think I’ve ever seen so many iPhones in the same room! It seemed like every other person had one (even Ade, who was also showing off his Android phone, a Christmas present from his employer).

finally, a huge thank you to Jason Gorman and everyone else involved in organising the day, and to the BBC for hosting it.

Categories
Software

Chaining SSH Tunnels

[Update 18/3/2009: added single-tunnel example]

This post is mainly for my own benefit, because every time I need to do this I find I’ve forgotten how and need to look it up again.

Say you want to reach dest, but have to tunnel through foo because you don’t have direct access to port 22 on dest.

ssh -NL 65001:dest:22 foo &
ssh localhost -p 65001
Welcome to dest!
$

If you need to tunnel through multiple gateways to reach the machine you want to connect to, this is how to do it. Now let’s say you have to jump through foo, bar and wibble to get to dest.

ssh -NL 65001:bar:22 foo &
ssh -NL 65002:wibble:22 localhost -p 65001 &
ssh -NL 65003:dest:22 localhost -p 65002 &
ssh localhost -p 65003
Welcome to dest!
$

Obviously you don’t need to use ports starting with 65001, but can pick any convenient unused local ports.

You can use different usernames and SSH ports if necessary, eg if you have to connect to wibble as dave on port 222, that line becomes:

ssh -NL 65002:[email protected]:222 localhost -p 65001

Technorati Tags: , ,

Categories
General nonsense Rails Ruby

My (very!) small part in the Array#forty_two controversy

For those outside the Rails community who have no idea what I’m on about, some people got a bit upset about Rails 2.2 defining Array#second up to Array#tenth, so for example you can call foo.fifth instead of foo[4] (you can already call foo.first instead of foo[0]). One of the last changes to be committed before 2.2 was released was to slim the list down to just second, third, fourth and fifth, but adding Array#forty_two (the ultimate answer) instead.

dhh_tweet.png

commit_1.png

kerry_reply.png

dhh_reply.png

commit_2.png

Categories
Rails Ruby

Rails 2.2 Envycast Review

I’ve been a fan of the RailsEnvy guys (Gregg Pollack and Jason Seifer) ever since their “Hi, I’m Ruby on Rails” spoof of the “I’m a Mac” ads, and have been listening to their podcast ever since. I even got a mention on it once. Well that’s not strictly true – I wasn’t actually mentioned, but a patch I’d contributed to Capistrano was, which is close enough.

Recently, Gregg and Jason have branched out into screencasts, but I hadn’t actually watched one because (understandably) they charge for them, and I was too tight to cough up the cash. £1200 for a new MacBook, no problem. A fiver for a screencast? What am I, made of money?

Anyhow, when I saw that they were looking for people to review their Ruby on Rails Envycast, covering the latest goodness in Rails 2.2, I jumped at the chance to get a free copy. A wonderful example of cognitive bias, given that I wouldn’t have agreed to write a review just to be paid $16.

What do I get for the money?

The basic $9 gets you the screencast and a set of code samples to go with it, or for $16 they’ll throw in Carlos Brando’s Ruby on Rails 2.2 PDF too. Alternatively the PDF is available on its own, also for $9.

Video

The video is available in Quicktime or Ogg formats at a resolution of 569×480, as well as a version optimised for iPhones and iPods. Total running time is just under 45 minutes, and incredibly the first 39½ of those go by before Jason makes any claims about Rails’s scalability.

I don’t know whether it’s unique, but the Envycast style of having the presenters chroma-keyed onto the Keynote presentation generally works very well. The visuals themselves are professional, although sometimes the ‘sparkle’ effect is a bit overused for my taste. The presentation style is much as you’d expect if you’ve listened to the podcasts, with plenty of cheesy humour to keep things interesting. I think having two people present in a conversational style is a big help.

The screencast is split into sections, each covering the new features for a different component (ActiveRecord, ActiveSupport, ActionPack, ActionController, Railties, internationalization and performance). The Quicktime version (not sure about the others) has bookmarks, making it easy to jump to a particular section. The whole thing is set against a variety of city skylines to liven the background up a little – by the way guys, that’s Tower Bridge, not London Bridge.

Each new feature is introduced with an example, generally contrasting the ‘old’ way of doing something with the equivalent in 2.2. There’s enough detail to get the idea of what’s changed, without dwelling too long on each one. One tiny gripe with the code snippets on screen: the pedant in me hates seeing curly quotes in code, because I know if I typed puts ‘foo’ into irb instead of puts 'foo', it wouldn’t work.

Code samples

The screencast comes with a set of code samples to illustrate all the features discussed in the screencast. These take the form of sample classes with Test::Unit test cases, along with rakefiles to run them. The sample directory contains a frozen installation of Rails 2.2, so all you need to do to run them is add the appropriate values to database.yml. I had trouble running them initially because they were inside a directory with a space in its name, but other than that it all worked nicely.

PDF

The PDF that comes with the $16 bundle is by Carlos Brando, well-known for his free Rails 2.1 book. It’s available in the original Portugese, or translated to English by Carl Youngblood. The book weighs in at 118 pages, and as you would expect goes into more detail than the screencast. It claims to cover all the major changes in Rails 2.2 (I haven’t checked!), and contains clear descriptions with examples.

Conclusion

So is it worth it? On balance, I think the answer is yes, although I wonder whether they’d sell more at $5 rather than $9 – after all, I can buy (to pick an example at random) the entire Naked Gun trilogy on DVD for roughly the same amount, and Gregg and Jason aren’t that funny. The value is in collecting all the information in one place – you could trawl through the release notes and lighthouse tickets to get all the same information, but if you value your time at all, the screencast and PDF pay for themselves many times over.

Should you buy the PDF, the video or both? If you just want the hard facts, go for the PDF, but if you want to be entertained too (assuming you find the Rails Envy podcasts entertaining), get the video as well. The next episode, Scaling Ruby, is out now, and I might buy it just to see if Jason finally admits that Rails might actually be able to scale.

Technorati Tags:

Categories
Agile

Agile in 25 Words

I realise I’m a bit late to the party, but following the example of JP, psd, Eastmad and Casablanca, I thought I’d have a stab at the 25 words challenge. Not feeling sufficiently inspired to come up with anyhing original and profound, here’s my attempt at boiling the principles of agile software development down into 25 words:

With customers, deliver valuable software early and often. Welcome change. Talk. Trust people to self-organise. Maintain pace, quality, simplicity and good design. Iterate; reflect; improve.
Categories
git

Avoiding Merge Commits in Git

[Update, 18/8/2008] If you’ve shared the branch with anyone else, or are pushing it to a clone of the repository, do not rebase, but use merge instead. From the man page:

When you rebase a branch, you are changing its history in a way that will cause problems for anyone who already has a copy of the branch in their repository and tries to pull updates from you. You should understand the implications of using git rebase on a repository that you share.


Do you get annoyed by seeing things like this in your git history?

commit a0b46a7c57e37f5dc43373ba9167ad2da32c1ec5
Merge: c2d8046... 73e0e15...
Author: Fred Bloggs 
Date:   Tue Jun 17 17:30:49 2008 +0100

    Merge branch 'master' into new_feature

commit c2d8046c038d47940944e5b343d281b1d0c4d2b3
Author: Fred Bloggs 
Date:   Tue Jun 17 17:30:43 2008 +0100

    Added cool new feature

This happens when you use merge instead of rebase to keep a development branch up-to-date with master. Let’s watch what happens in each case.

The wrong way (merge)

You’re working on a cool new feature in your new_feature branch. You’ve committed two changes, and in the meantime there have been three other changes on master. Here’s the branch visualisation from gitk --all:

Before merge

You use merge to pull in those other three changes to your branch:

$ git merge master
Merge made by recursive.
 file_1 |    4 ++++
 1 files changed, 4 insertions(+), 0 deletions(-)

Now what this has actually done is added the changes from master as a new commit in new_feature. You can see this in the history:

myproj(new_feature) $ git log -1
commit cbc97a909641d3c325c6023a2459e556e62182e6
Merge: 024dc64... 0a71c4c...
Author: Kerry Buckley 
Date:   Wed Jun 18 18:52:48 2008 +0100

    Merge branch 'master' into new_feature

And also in the gitk graph:

After merge to branch

Now let’s say your new feature is all finished, so you merge it into master:

myproj(new_feature) $ git checkout master
Switched to branch "master"
myproj(master) $ git merge new_feature 
Updating 0a71c4c..cbc97a9
Fast forward
 file_3 |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)

Let’s see what that’s done to the history:

myproj(master) $ git log
commit cbc97a909641d3c325c6023a2459e556e62182e6
Merge: 024dc64... 0a71c4c...
Author: Kerry Buckley 
Date:   Wed Jun 18 18:52:48 2008 +0100

    Merge branch 'master' into new_feature

commit 0a71c4c90aee5eeb60d15f199c4f8151756a8ae8
Author: Kerry Buckley 
Date:   Wed Jun 18 18:48:19 2008 +0100

    Third change in master

commit 9970c0b72e7741804fc07bba50450b3d512e5572
Author: Kerry Buckley 
Date:   Wed Jun 18 18:48:10 2008 +0100

    Second change in master

commit c44af4dee449082adf6741540d2f9e70968cf41e
Author: Kerry Buckley 
Date:   Wed Jun 18 18:46:33 2008 +0100

    First change in master

commit 024dc64022932a5a7b56c4fd7c7cf4a59d72e825
Author: Kerry Buckley 
Date:   Wed Jun 18 18:45:15 2008 +0100

    New feature finished

commit eb4f05fb8ef8b93cf639b1e06528ef075f19f323
Author: Kerry Buckley 
Date:   Wed Jun 18 18:45:01 2008 +0100

    New feature partly done

commit b4ffa1d35f808cc38e5f74fb2592224dd6f0e027
Author: Kerry Buckley 
Date:   Wed Jun 18 18:44:02 2008 +0100

    Last commit before creating branch

Or graphically:

After merge to master

The problem here is that the merge has applied all of the commits which were on new_feature but not on master, including the merge commit. That’s just ugly.

The right way (rebase)

Now, from exactly the same point, we’ll use rebase instead:

myproj(new_feature) $ git rebase master
First, rewinding head to replay your work on top of it...
HEAD is now at a644c41 Third change in master
Applying New feature partly done
Applying New feature finished

Basically, as it says, this has rewound all your changes since the new_feature branch diverged from master, moved the branch point up to the tip of master, then replayed your changes on top. The effect of this is as if you had created the branch from the current latest master, so no separate merge commit is required. Again, gitk --all can confirm this visually:

After rebase

Now merge the changes into master exactly as before:

myproj(new_feature) $ git checkout master
Switched to branch "master"
myproj(master) $ git merge new_feature 
Updating a644c41..d7d2233
Fast forward
 file_3 |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)

No merge commit in the history this time, and a nice simple graph:

After rebase and merge

So there you have it. No excuse for polluting your history with merges any more!

Technorati Tags: , , ,

Categories
Enterprise Rails Ruby

Defending Ruby and Rails in the Enterprise

I consider myself fortunate that the previous two projects I worked on (the BT Web21C Portal and Mojo) were Rails-based (actually it wan’t just luck in the former case, as I had a part in selecting the framework). I love the expressiveness and flexibility of the Ruby language, the power and relative simplicity of the Rails framework, and the all-round awesomeness of tools like RSpec and Capistrano, and I don’t particularly relish the thought of going back to Java (although I’m told that Spring is much nicer than last time I used it).

At our recent release planning session, I was assigned to a new project, which involves (among other things) exposing a CLI-based configuration interface as a web service. In our initial discussions, the four of us more-or-less agreed on a few initial decisions:

  • The exposure should be REST. Fortunately the people developing the upstream system shared this opinion.
  • Rails is an ideal framework for RESTful web services.
  • Ruby seemed like a good fit for parsing the command responses too.
  • Asynchronous behaviour would be handled using queues (probably ActiveMQ).

Since we’d all been working on Rails projects when the new team was formed, we assumed that this wouldn’t be a particularly contentious route to go down, but unfortunately our director/architect/boss didn’t see things quite the same way. He had two main objections:

  • Rails may make sense for GUI applications, but why on earth would you use it for a service? All our other [SOAP] services are written in Java.
  • At some point the application will need to go into support, and we don’t have support/operations people with Ruby or Rails experience

I think the first point’s easier to address, as I’d argue it’s based on a misunderstanding: Rails isn’t really anything to do with GUIs, but is a framework for creating MVC web applications. Virtually all the heavy lifting Rails takes care of is in the controller and model areas, with the creation of the actual visible GUI being left to the developer to take care of with the usual mix of HTML, CSS and Javascript. The only thing Rails adds is the ability to insert dynamic content using ERB – similar to the role of JSP in Java EE.

A RESTful web service is, to all intents and purposes, the same as a normal web application, but (potentially) without the HTML. All the power that Rails brings to web application development is also harnessed when creating RESTful services.

The second point represents a much more fundamental strategy choice. If the company makes the decision that all development is going to use Java (the language as well as the platform), then we inevitably lose the flexibility to choose what may appear (in a local context) to be the right tool for the job. Personally I think that would be a shortsighted and ill-informed decision: if that were the strategy, we’d presumably all still be developing in C, or COBOL, or Assembler. Or we’d have gone bust. But then I’m not an architect (incidentally, according to Peter Gillard-Moss, that’s reason number 10 why I don’t deserve to be fired), so what do I know?

However, if Ruby is considered an acceptable technology choice for “normal” web applications, we’ll still need people with appropriate skills to support those, so the problem doesn’t go away. I suspect even for a Java specialist, supporting a well-written Rails application with good test coverage is probably easier than supporting some of the spaghetti-coded Java I’ve seen.

Anyway, our arguments obviously weren’t totally unconvincing, because we were given a couple of weeks to show what we could produce before getting a final decision. That time runs out on Monday, so if I’m unnaturally grumpy after that it’ll be because we’ve been told to chuck all our work so far away and start from scratch in Java. Or possibly FORTRAN.

Update, 16 June Well we made our case, and we get to stick with Rails. Celebration all round!

Categories
Software

Git quote of the day

From Amy Hoy on Slash7:

If svn is your sometimes catankerous but serviceable steed, git is like a chimera crossed with a unicorn with handy built-in saddle bags plus a sword.

Technorati Tags: , , , ,

Categories
Agile Enterprise Rants

On being beaten with carrots

CarrotsTraditional approaches to motivation tend to fall into one of two camps: the carrot (“do this and you’ll be rewarded”) or the stick (“do this or you’ll suffer the consequences”).

I guess I’m fortunate to work for a company (and in a country) where by and large there isn’t a culture of firing people who don’t meet performance targets – instead we have a system where an ever-increasing proportion of people’s pay packet is made up of a performance-related bonus, rather than a fixed salary.

So, how do you go about getting your bonus each quarter? Simple: just meet your agreed targets.

Of course, nothing in a large corporation can ever be that simple, so in practice there’s a complex tiered system of company, business unit, programme, project, team and individual targets, which are combined in a magic spreadsheet to generate how much bonus everyone gets. Each of these targets, and the performance against them, has to be agreed, monitored, quantified, audited and levelled. At each stage politics comes into play. Those that enjoy playing systems try to set targets they know they can achieve. People concentrate on meeting the letter of the objectives, possibly to the detriment of other activities, like helping colleagues or making process improvements.

Now step away from this corporate dystopia for a moment, into the world of Agile Software Development. A world where we value Individuals and interactions over processes and tools, and Responding to change over following a plan. A world where we strive to build projects around motivated individuals, give them the environment and support they need, and trust them to get the job done. Where working software is the primary measure of progress. Where at regular intervals, the team reflects on how to become more effective, then tunes and adjusts its behavior accordingly. Where the self-organising team, accountable directly to it customer or product owner, is responsible for its own delivery and processes.

Now, when agile teams in large organisations are forced to jump through the externally-imposed hoops of objectives, development action plans and post-implementation reviews (which add little visible benefit and take up time that could be spent delivering business value), is it any wonder that the carrot of performance-related pay feels like it’s more of a punishment than an incentive?

Technorati Tags: , , , ,

Public domain photo from Wikimedia Commons.

Categories
Software

Python II: Fibonacci Sequence

Tim’s second exercise (here’s the first):

Write a recursive function that calculates the value of Fibonacci numbers. These are your acceptance criteria:

  • Calculating fib(250) must return 7896325826131730509282738943634332893686268675876375
  • The function must use recursion. No intermediary data structures, etc.
  • The implementation must be written in pure python – no C extension modules, that’s cheating.
  • The function must calculate the 250th Fibonacci number in under one second.

    You will get extra points if:

  • You can also demonstrate a proof for the Reciprocal Fibonacci constant, meeting the following conditions
    • Your proof must also run in under one second
    • Your proof must not duplicate any of the concerns addressed by your original Fibonacci function implementation.
    • Your proof is allowed to call into the Fibonacci function though!

The Reciprocal Fibonacci constant is defined as:

P(F) = Sum[k = 1..infinity] 1/F(k) = 3.35988566…

Where F is a Fibonacci number

Here’s a couple of hints about things to look for:

  • Memoization
  • Function decorators

I haven’t tried the extra credit section yet, but this is what I came up with. Again, starting with a naive solution with some doctest tests:

#!/usr/bin/env python

"""
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5
"""
def fib(n):
	if n <= 2:
		return 1
	else:
		return fib(n-2) + fib(n-1)

def _test():
   import doctest
   doctest.testmod()

if __name__ == "__main__":
   _test()

Well that seems to work OK. Now, try adding a test for the 250th number:

>>> fib(250)
7896325826131730509282738943634332893686268675876375

And wait … and wait …

No, doesn't look like that's going to return any time soon. Of course when you look at what it's doing, the complexity's increasing in the order of 2n or something, which isn't good.

OK, I guess this is where memoisation comes in. After much head-scratching on the train this morning, I came up with this:

fibs = {}

def fib(n):
	if n <= 2:
		return 1
	elif fibs.has_key(n):
		return fibs[n]
	else:
		fibs[n] = fib(n-1) + fib(n-2)
		return fibs[n]

A little tweak to allow it to be called from the command line with the value of n passed as an argument, and here's the final version:

#!/usr/bin/env python
import sys

fibs = {}

def fib(n):
	if n <= 2:
		return 1
	elif fibs.has_key(n):
		return fibs[n]
	else:
		fibs[n] = fib(n-1) + fib(n-2)
		return fibs[n]

def _test():
  import doctest
  doctest.testmod()

if len(sys.argv) > 1:
	print fib(int(sys.argv[1]))
if __name__ == "__main__":
  _test()
fib(master) $ time ./fib.py 250
7896325826131730509282738943634332893686268675876375

real	0m0.280s
user	0m0.161s
sys	0m0.047s

Sorted!

Technorati Tags: , ,