October 21, 2010

Conditional breakpoints can cause side-effects.

Posted in Debugging tagged , , , at 8:11 am by davy803

I had the strangest bug the other day.  One part of code just suddenly stopped working, a variable was being set to the wrong value somehow but I could not find where it was being set.  I reverted back to a working copy from source control, chalking it up to one of those random mysteries.  Still not working.  Rebooted, did a clean checkout.  Still nothing.  At this point I was very frustrated.  I removed a breakpoint and it suddenly started working again.  It was the strangest thing.

Then I realized what happened.  I had set a conditional breakpoint, but instead of setting to condition to “foo == bar” I had set it to “foo = bar” so it was assigning the value.  Doh!

July 1, 2009

Unit Test vs Integration Tests

Posted in Chefbook at 12:31 am by davy803

I’m finding that I prefer having a mix of integration tests to just having strictly unit tests.  Unit tests are great for helper method or things that’re used all over the place, but often times there are one-off methods that don’t perform directly affect the end result, they’re just one way of achieving a specific functionality, a means to an end and not the end itself.
One of the things that’s nice about integration tests is that they test the what, not the how.  You can write integration tests based off a functional spec.  If a user moves a file to another folder we just want to know that it’s no longer in the originating folder and that it is in the destination folder.  The integration test doesn’t care how this is achieved.  If you later decide to refactor the method, the integration should still be valid.
Unit tests do have the benefit of being able to track down a problem more easily to a particular method, but I feel often times that’s not really necessary, more of a convinience.  With good debugging tools you should be able to step through and find the problem.
One issue I found initially with using Visual C# Express instead of one of the paid versions of Visual Studio is the lack of plug-in support like TestDriven.NET that lets you run tests under debug.  A good workaround to that I discovered is just create a test console app project (I just put it in the solution, and when I’m trying to debug some broken tests, just set that as the startup project) and run the Setup method followed by the specific test method you want to debug.  It’s a little ghetto but I found i works really well, much better than doing old school debugging (i.e. sprinkling gratuitous amounts of Console.WriteLine’s everywhere. (Then forgetting to remove them later)
I still do a mix of unit tests and integration tests, but I don’t really make as much of a distinction between them as some people.  I break one of the rules of strictly unit testing, which is 1 assertion per test.  I prefer to just extend a test rather than create a whole new one that does mostly the same thing.  For instance I have a long string of undo and redo tests all in the same test.  I do some stuff, undo it, redo it, do some more, and undo it all and put in appropriate asserts in between them to make sure that it behaves correctly each step of the way.
I’ve also strayed a little from strictly test-driven development.  I sometimes write the method first and sometimes the test first, but always write tests and methods pretty close to each other.  If you write all the code first it becomes really hard to get the motivation to write 50 tests for all that code, and often you get sloppy about what gets tested.
A pattern I’ve fallen in to which seems to work pretty well for me is that if I’m writing new functionality I write the method first.  If I’m altering existing functionality I write the test first.  It’s more for convinience than anything else. I don’t think it results in better code than purely test first, but I don’t think it makes it too much worse either.  I do lose out on the ability to verify that my test is actually testing the right thing (i.e. it fails before the code is written to make it pass)  A green test could mean that the code under test works.  Or it could mean that it’s not actually testing the code you think it is.
One important thing I do is if I think of a tricky scenario where a a bug could be introduced (such as a strange input that I might not account for) I always write the test case for that first.
The tests (whether you choose to call them unit tests or not) have been invaluable though.  They caught a lot of bugs when I was adding some functionality (such as undo/redo support) as well as when refactoring to make sure I didn’t subtly change the behavior.

I’m finding that I prefer to have a mix of integration tests with my unit tests rather than just strictly unit test.  A lot of people try to differentiate the two, and maybe for really large projects it does matter, but for smaller projects I find the distinction to be rather moot.   Here’s some other discussion about the difference between unit tests and integration tests.

One of the things that’s nice about integration tests is that they test the what, not the how.  You can write integration tests based off a functional spec.  If a user moves a file to another folder we just want to know that it’s no longer in the originating folder and that it is in the destination folder.  The integration test doesn’t care how this is achieved.  If you later decide to refactor the method, the integration should still be valid.

Unit tests do have the benefit of being able to track down a problem more easily to a particular method, but I feel often times that’s not really necessary, more of a convinience.  With good debugging tools you should be able to step through and find the problem.

One issue I found initially with using Visual C# Express instead of one of the paid versions of Visual Studio is the lack of plug-in support like TestDriven.NET that lets you run tests under debug.  A good workaround to that I discovered is just create a test console app project (I just put it in the solution, and when I’m trying to debug some broken tests, just set that as the startup project) and run the Setup method followed by the specific test method you want to debug.  It’s a little ghetto but I found i works really well, much better than doing old school debugging (i.e. sprinkling gratuitous amounts of Console.WriteLine’s everywhere. (Then forgetting to remove them later)

I still do a mix of unit tests and integration tests, but I don’t really make as much of a distinction between them as some people.  I break one of the rules of strictly unit testing, which is 1 assertion per test.  I prefer to just extend a test rather than create a whole new one that does mostly the same thing.  For example this is how my undo/redo test looks like:

[Test]
public void ChangesToAnIngredientShouldBePartOfRecipeUndoStack()
{
    var ing1 = new Ingredient();
    recipe.AddIngredient(ing1);
    recipeVM = new RecipeViewModel();
    var ingVM2 = new IngredientViewModel();
    recipeVM.RecipeModel = recipe;
    recipeVM.AddIngredient(ingVM2);
    ingVM2.Name = "BoB";
    ing1.Name = "Phil";
    Assert.True(recipeVM.Undo()); //Undo BoB namechange
    Assert.AreEqual("Phil", ing1.Name); //Phil shouldn't be undone because it wasn't performed on VM
    Assert.AreEqual(string.Empty, ingVM2.Name);
    Assert.True(recipeVM.Undo()); //Undo Add Ingredient
    Assert.False(recipeVM.Ingredients.Contains(ingVM2));
    Assert.False(recipeVM.Undo()); //Undo stack should be empty
    Assert.True(recipeVM.Redo()); //Redo Add Ingredient
    Assert.Contains(ingVM2, recipeVM.Ingredients);

    Assert.True(recipeVM.Redo()); //Redo BoB namechange
    var ingVM3 = new IngredientViewModel();
    recipeVM.AddIngredient(ingVM3);
    ingVM3.Name = "Jean";
    ingVM3.Amount = 3;

    Assert.True(recipeVM.Undo()); //Undo amount Change 3
    Assert.AreEqual(0, ingVM3.Amount);
    Assert.AreEqual("Jean", ingVM3.Name);
    Assert.AreEqual("BoB", ingVM2.Name);
    Assert.Contains(ingVM3, recipeVM.Ingredients);

    Assert.True(recipeVM.Undo()); //Undo name Change 3
    Assert.AreEqual(string.Empty, ingVM3.Name);
    Assert.AreEqual("BoB", ingVM2.Name);
    Assert.Contains(ingVM3, recipeVM.Ingredients);

    Assert.True(recipeVM.Undo()); //Undo add ingredient
    Assert.AreEqual("BoB", ingVM2.Name);
    Assert.False(recipeVM.Ingredients.Contains(ingVM3));

    Assert.True(recipeVM.Undo()); //Undo name Change 2
    Assert.AreEqual(string.Empty, ingVM2.Name);
    Assert.Contains(ingVM2, recipeVM.Ingredients);

    Assert.True(recipeVM.Undo()); //Undo add ing2 2
    Assert.False(recipeVM.Ingredients.Contains(ingVM2));

    Assert.False(recipeVM.Undo()); //Undo stack should be empty
}

Okay, I’ll be the first to admit it looks pretty ugly but the test has a clear purpose which is to test a large series of undo and redo operations and verify that the data is correct each step of the way, and not only verifies that an undo or redo operation worked, but also that a string of such operations works.

I’ve also strayed a little from strictly test-driven development.  I sometimes write the method first and sometimes the test first, but always write tests and methods pretty close to each other.  If you write all the code first it becomes really hard to get the motivation to write 50 tests for all that code, and often you get sloppy about what gets tested.

A pattern I’ve fallen in to which seems to work pretty well for me is that if I’m writing new functionality I write the method first.  If I’m altering existing functionality I write the test first.  It’s more for convenience than anything else. I don’t think it results in better code than purely test first, but I don’t think it makes it too much worse either.  I do lose out on the ability to verify that my test is actually testing the right thing (i.e. it fails before the code is written to make it pass)  A green test could mean that the code under test works.  Or it could mean that it’s not actually testing the code you think it is.

One important thing I do is if I think of a tricky scenario where a a bug could be introduced (such as a strange input that I might not account for) I always write the test case for that first.

The tests (whether you choose to call them unit tests or not) have been invaluable though.  They caught a lot of bugs when I was adding some functionality (such as undo/redo support) as well as when refactoring to make sure I didn’t subtly change the behavior.

June 29, 2009

Regarding (my version of) the Model-View-ViewModel Pattern

Posted in Chefbook at 10:26 pm by davy803

Today I’m going to be discussing the Model-View-ViewModel (MVVM) pattern that is widely used in WPF (and Silverlight) applications. I say my version of the pattern because there seems to be some debates over the details of the pattern implementation, but I suppose that’s the case with most design patterns.

Working on the UI now and utilizing the MVVM (Model-View-ViewModel) pattern and loving it so far.  What I feel separates it from some of the other patterns such as MVC (Model-View-Controller) and MVP (Model-View-Presenter) patterns is the fact that the ViewModel is completely decoupled from the View.
I’m more familiar with MVP than I am with MVC, and one of the problems I had with it was that it tried to abstract away the View by using an interface, which works in theory, but in practice a View rarely ever changes without requiring an interface change.  Then if you wanted to have more than one View share a Presenter (say you have a screen with the full blown options, as well as one with just a limited subset of those) you’d have to put in stubs that do nothing into the simple View to match all the interfaces.  If you wanted to display th same data in a different way (say a slider instead of a dropdown box) you’ have have separate methods in the Presenter to account for each one, and modify the interface to support both.  (In this simplified example I’m sure you could come p with a way to abstract the interface so that you can pass in an index or selected value from the presenter instead of explicitly setting it for each control, but you get the picture)
With the MVVM pattern, the ViewModel is not dependent on the view.  I can operate completely independent of the View, which for one makes unit testing a breeze.  In fact, you don’t even need a mock object for the view because it all acts independent of the existence of a view.  You can even create a console app using the same ViewModel (You’d just be ignoring most of the UI related properties).
Somewhat of a downside of the MVVM pattern is that since the view is in charge of its own display logic, that part doesn’t get unit tested.  That logic however is often easier to verify through blackbox testing (just using the app) and usually consists of things that are discovered fairly early on in acceptance testing.
MVVM is often claimed as a pattern developed specifically for WPF.  While that may be true, I feel it’s a very generally applicable pattern for any GUI frontend.  WPF provides more powerful databinding that makes it easier to apply, but the ViewModel could easily be reused with manual binding.  The key point is that it doesn’t tell the view how to display it.  It raises events to which the view can choose to respond to or not.  It provides data that the view can choose to display or ignore.  The view has the flexibility to display what it wants, how it wants.

Working on the UI now and utilizing the MVVM pattern and loving it so far.  What I feel separates it from some of the other patterns such as MVC (Model-View-Controller) and MVP (Model-View-Presenter) patterns is the fact that the ViewModel is completely decoupled from the View.  (Actually it looks like the MVP pattern is “retired” and is split into the Supervising Controller and the Passive View pattern, which is the variant of MVP that I’m familiar with)

I’m more familiar with MVP than I am with MVC, and one of the problems I had with it was that it tried to abstract away the View by using an interface, which works in theory, but in practice a View rarely ever changes without requiring an interface change.  Then if you wanted to have more than one View share a Presenter (say you have a screen with the full blown options, as well as one with just a limited subset of those) you’d have to put in stubs that do nothing into the simple View to match all the interfaces.  If you wanted to display the same data in a different way (say a slider instead of a dropdown box) you’ have have separate methods in the Presenter to account for each one, and modify the interface to support both.  (In this simplified example I’m sure you could come up with a way to abstract the interface so that you can pass in an index or selected value from the presenter instead of explicitly setting it for each control, but you get the picture)

With the MVVM pattern, the ViewModel is not dependent on the View.  Instead of a presenter telling the View “Update the progress bar to 38%”, a ViewModel says  “Hey, they current progress is 38%” (by raising an event) and the view can display that however it wants, using a progress bar, or a text message, or changing colors (or ignoring it completely).

Additionally, the ViewModel can operate completely independent any View, which for one makes unit testing a breeze. You don’t even need a mock object for the view because it can act independent of the existence of a view.  You can even create a console app using the same ViewModel (You’d just be ignoring most of the UI related properties).

Somewhat of a downside of the MVVM pattern is that since the view is in charge of its own display logic, that part doesn’t get unit tested.  That logic however is often easier to test by just running the app and usually consist of superficial errors whose effects are seen immediately instead of subtle errors deep down that aren’t detected until much later and often times the subtle errors manifest themselves in side-effects that can be quite distant from the source of the error.

MVVM is often claimed as a pattern developed specifically for WPF.  While that may be true, I feel it’s a very generally applicable pattern for any GUI frontend.  WPF provides more powerful databinding that makes it easier to apply, but the ViewModel could easily be reused with manual binding.  The key point is that it doesn’t tell the view how to display it.  It raises events to which the view can choose to respond to or not.  It provides data that the view can choose to display or ignore.  The view has the flexibility to display what it wants, how it wants.

June 11, 2009

And… We’re Back

Posted in Chefbook at 8:24 am by davy803

Several things.  I’ve moved the repository to new hosting and it will no longer be under GPL (the current code base still on Google Code will remain there and under GPL, but I won’t be making any modifications there).  I haven’t drafted up a a new license yet, but the general premise will be that it is available for viewing for learning purposes, but neither it nor any derived works may be redistributed in any form without explicit consent.  You may link to the repository.  That being said, the definitive license when it’s drafted will be included in the repository, but that’ll be be basic overview of it.  The new repository is available for read-only access here: http://chefbook.svn.beanstalkapp.com/chefbook/trunk/

Now that that’s out of the way, I’ve been quite busy and have undergone quite a few changes.  First off, I’m no longer using a “real database” and instead I’m using XML as my datastore.  The performance shouldn’t be too bad for the amount of data that’s going to be there and it’s a lot more flexible than SQLCE as far as being able to change things later easily (wrote a custom serializer which was easier than I expected.  It’ll also be semi-human readable; whether or not that’s important is debatable.

May 7, 2009

Defensive Coding, When And When Not To.

Posted in Uncategorized at 8:30 am by davy803

I’ve always been a supporter of defensive programming, which is the practice of accounting for errors and allowing for a program to continue in spite of them.  At first glance it seems to make sense, after all, having a program crash is among the worsts things for user experience.  It’s even spawned such patterns as the Null Object pattern to reduce the need to return null and thus cause errors.  

So why is there a new movement that advocates against defensive programming? I was confused myself, and as I looked into it, it seems there’s even different definitions on what defensive programming is.

The issue came up for me when I was writing a method to retrieve an entry from the database by Id.  My initial thoughts were to program defensively: what if there is no entry in the database by that id?  Well I’ll just return null and let the calling code handle it, which will do whatever it needs to do, whether show a message to the user that it wasn’t found or if it’s showing a list of items, just exclude the item from the list.

Then I started thinking deeper.  Why would the entry not be found in the database?  The user has no direct access to the database (well technically they could open the .sdf file, but that’s not something they can “accidentally” do and in which case they knowingly screwed up their own data).  All access to the database both lookup and retrieval is done through a single class, and there is no direct querying of the database.  This is further wrapped in a finite set of actions that may be performed by a user.  The only possible way for an entry to not be found is a result of a programming error in my code.

 When put that way, it makes a lot more sense that an error should be thrown, so I know about it and can get to the bottom of what caused this.  Using defensive programming in this scenario (depending on who you talk to, some consider this a misuse of the term defensive programming, and I would agree, nonetheless, it is often misused in this manner) would just hide the error.  I don’t know what caused it, was it the program being mistaken in thinking that an entry with that Id was there in the first place, or was the data some how corrupted and now that entry that’s supposed to be there was lost?  This is an error that I need to be aware of.

So when is it appropriate to use defensive programming?   One should program defensively whenever user input can cause an error.  Trying to parse an integer from a textbox?  You better make sure that you account for them entering a non-integer value and proceed accordingly.  Ways to do this include telling them (hopefully nicely) that they must enter in a numeric value, having per-key validation, or even going as far as to recognize “five” instead of “5”.  Whatever you do, as far as user input goes, you have to assume that anything that they are physically capable of inputting they will.  Even things that you don’t think they’re capable of inputting (non-ascii characters, malicious code, anything at all) they might still be able to enter.

The other time is also a similar in nature, but not quite the same is when relying on something that is inherently unreliable.  If such cases come up (and they do) then the source is out of your control.  This might be a 3rd party library, a network connection, files on disk (which one might consider a form a user input, but I digress) or something else that you have no control over, then you have no choice but to program defensively.

Defensive programming is a crutch.  It’s saying that you have no control over how something will behave and so you have to try to take into account the mistake and work around it.  Sometimes this is necessary.  The TCP protocol is one of my favorite examples.  IP (not IP Address) is an inherently unreliable connection.  Hardware and physics dictate this, and as software developers we have no control over the laws of Physics.  Accordingly TCP tries it’s very best to ensure that a stable connection where all packets are guaranteed to arrive, undamaged, and in order.  None of these things are guaranteed to happen, but TCP fixes any errors that occur along the way.  In an ideal world they would be sent in perfect order, all delivered, and in perfect condition, but the laws of the physical world tell us that they cannot guarantee this.  But as Joel Spoklsy points out, even TCP can’t protect us from everything.  If the network cable is unplugged, no amount of defensive programming is going to allow us to recieve our data.  We need to account for this and proceed accordingly.

Defensive programming is good when applied to the appropriate situation, but if used incorrectly can hide errors that should not be hidden.  Before deciding on whether to apply defensive programming, first consider the nature of each error.  Is the source of the error something you are in control of?  If so maybe defensive programming isn’t the answer and you should be busy making sure that error can’t occur in the first place, and the first step to fixing an error is to know it exists.  If the source of the error is out of your control, then you’ll just need to make the best of it and defend against those errors accordingly.

April 29, 2009

Unit Tests, Extension Methods, and Lambda Expressions, Oh My!

Posted in Chefbook tagged , , , , , , at 10:29 am by davy803

After taking a little detour into Python, I’m back to working on Chefbook.

First of all, I must say I’m very happy with my experience with test driven development.  As I mentioned in my first post about TDD, I’m not following the exactly process of writing and passing one test at a time.  Instead I write out all the tests I can think of for an entire class based on the functional specification.  I also write out method stubs beforehand for two reasons.  First, I like having a compiling codebase and the red underline squigglies for compile errors bothers me.  The second reason is so I get IntelliSense (Visual Studio’s auto-complete) which makes typing method names easier and less error prone.  Also since it resolves to known methods I can rename them easier later using Visual Studio’s rename feature.

The first thing that occurred to me when I wrote tests first was that it’s a lot easier to write tests that are easy to code, than it is to write code that’s easy to test.  Some of my previous attempts with writing unit tests were a bit rough because the it was hard to get code under test in isolation.  The second thing is that if you write tests first, you don’t have any preconceived notions of how the code works, all you know and need to know is what the method is supposed to do.  A lot of times when I was writing unit tests afterwards, I ended up just rewriting the code in the test, because I already saw the code and had a preconceived notion on how it was going to work.  When writing unit tests, how it works is not important, it’s what it does that matters.  Writing tests before writing code lets you break the temptation to write tests that pass because you know how the code is written.

What I also discovered, was that even though I wrote “all” the tests before starting on any code, I quickly discovered that there were more conditions that needed to be tested than I originally thought.  What ended up happening is that I would get all the tests on a method to pass and feel pretty good about it.  Then as I’m trying to get a different test to pass, I’d find out in the process of debugging that the first method wasn’t designed as thoroughly as it needed to be (because all the designed behaviors are tested).  Let’s look at an example to explain what I mean.

The Category class has an AddRecipe method that does exactly what it says, it adds a given recipe to that category.  The problem was that there was nothing to prevent the same recipe from being added to a category more than once.  That wasn’t part of the design because it didn’t occur to me that that scenario could come up.  Well, now when you delete a category, it automatically does all the cleanup work removes itself from all of its recipe’s list of categories.  As it was looping through the list of recipes, it tried to remove itself twice from the same recipe because the same recipe was in the list twice.  Here it threw an exception because, following the fail fast strategy, I throw an ArgumentException if you try to remove a category from a recipe that doesn’t have that category listed.  This lead to adding a unit test (thus changing the design, because the tests are the design in TDD) to ensure that if you try to add a recipe more than once, there will still only be one instance of the recipe in the category.

Another thing from fail fast is that I end up checking all arguments for null if it doesn’t make sense for it to be null.  There are instance where it’s allowed, for instance a category can have no parent if it’s the root category.  What ended up happening was that I ended up littering methods with ugly null checks and argument validation code like the following:

public void AddRecipe(Recipe recipeToAdd)
{
    if (recipeToAdd == null)
    {
        throw new ArgumentNullException("recipeToAdd");
    }
    if (!recipes.Contains(recipeToAdd))
    {
        recipes.Add(recipeToAdd);
    }
    if (!recipeToAdd.categories.Contains(this))
    {
        recipeToAdd.categories.Add(this);
    }
}

Luckily, C# 3.0 added Extension Methods that allows us to cleanup this code.  I’ll explain how it works shortly, but here is what this code looks like using the extension methods I added.

public void AddRecipe(Recipe recipeToAdd)
{
    recipeToAdd.ThrowIfNull("recipeToAdd");
    recipes.AddIfNew(recipeToAdd);
    recipeToAdd.categories.AddIfNew(this);
}

Looks much nicer, but how does it work?  Did I add a ThrowIfNull method to the Recipe class?  Isn’t that a big hassle to add that method everywhere it’s needed?  No, it’s not because I didn’t add it to Recipe, I actually added ThrowIfNull to the object class.  How did I do that you ask?  Well ok, I made a little fib.  I didn’t really add it to the object class.  But I can use the method as if I did.  Here’s what the ThrowIfNull method looks like:


namespace Chefbook.HelperMethods
{
    public static class ParameterValidation
    {
        public static void ThrowIfNull(this object valueToCheck, string parameterName)
        {
            if (valueToCheck == null)
            {
                throw new ArgumentNullException(parameterName);
            }
        }
        //More methods here
    }
}

As you can see, the method is in a separate class altogether. It is a static class and the method is a static method, meaning that it’s not a instance method.  But we just called the method on an instance variable.  Technically we didn’t, that’s just the magic of extension methods.  Notice that the this keyword is in front of the first parameter of the method.  This indicates that it’s an extension method.  Extension methods are syntax shortcuts, nothing more.  When I say:

someObject.ThrowIfNull("someObject");

That’s actually just a shortcut for saying:

ParameterValidation.ThrowIfNull(someObject, "someObject");

While it’s true that it may not be much shorter, the way the syntax flows makes it easier to understand and more natural.

There other extension method I have is AddIfNew.  Let’s take a quick look at that:

public static void AddIfNew<T>(this ICollection<T> collection, T itemToAdd)
{
    if (!collection.Contains(itemToAdd))
        collection.Add(itemToAdd);
}

If you’re unfamiliar with generics, this might be a little confusing to understand at first.  Check out this article for a quick intro to generics in C# if you need to.  Basically what generics give you is the ability specify the type of an object when you create an object and to constrain the type of parameters or return values.  In the example above, this is an ICollection of type T.  What T is isn’t important here, as long as the parameter itemToAdd is also of that same type T.  You’ll notice when I called the extension method I didn’t need to specify the type when I used it:

recipes.AddIfNew(recipeToAdd);

Instead of:

recipes.AddIfNew<Recipe>(recipeToAdd);

This is because I’m calling the method on recipes which was already declared as List<Recipe> so it knows that T is based on that.  (List implements IList which implements ICollection.) 

There’s one more extension method I’d like to show.  I added the method because the fact that the Parent of a Category is allowed to be null is problematic, in that I need to check if Parent is null before I can perform any kind of action on it.  It’d be nice if I could write a one-liner to do that like we did above.  But how do we do that if we don’t know what it is we need to do?  Delegates to the rescue!  Delegates are a complex topic and explaining them fully is beyond the scope of this post.  If you want to learn more about delegates, I recommend this article.  Suffice it to say that delegates are a way to pass methods as variables. 

There’s two built-in classes that encapsulate delegates so they’re somewhat easier to use (they can get quite clunky using them manually).  The first one which I used is Action, which takes 0 to 4 parameters and returns no value.  The second is Func which does the same thing except it returns a single value.  Let’s take a look at the method here:

public static void PerformIfNotNull(this object valueToCheck, Action actionToPerform)
{
    if (valueToCheck != null)
        actionToPerform();
}

It takes a parameter of type Action and then checks if the object is null and performs the action if it’s not null.  If we wanted the Action to take one parameter, then it’d look like this:


public static void PerformIfNotNull<T>(this object valueToCheck, 
    Action<T> actionToPerform, T param)
{
    if (valueToCheck != null)
        actionToPerform(param);
}

Notice we need to pass in the argument for actionToPerform as a separate parameter (param).  Notice also we use T to specify the type of the paramter.  By the way, “T” isn’t a special name or anything, it’s just a naming convention for generics  What’s important is that it’s declared as a generic type in the method signature by putting in inside brackets.  If we wanted the method to return a value we could use Func instead of Action and it’d look like this:

public static TResult PerformIfNotNull<T, TResult>(this object valueToCheck,
    Func<T, TResult> actionToPerform, T param)
{
    return actionToPerform(param);
}

Notice we declared an additional generic type, TResult.  We need to specify the return type for a Func, and we do that by declaring it both in the method signature and in the return type.  Now this method doesn’t really do anything useful, since we’re just calling a function to call another function, but just explaining the syntax for the sake of example because that was something I had trouble with for a while.

Now that we see how the method is declared, let’s see how it would be used.  We are assuming the first example of PerformIfNotNull (the one that takes an Action that takes 0 arguments and returns void).

public Category Parent
{
    get { return parent; }
    set
    {
        parent.PerformIfNotNull(delegate()
                    { this.parent.subcategories.Remove(this); });
        this.parent = value;
        value.PerformIfNotNull(delegate() { value.AddSubcategory(this); });
    }
}

Here we introduce a concept called anonymous methods.  I won’t discuss them too much in here but this is a great article for learning about anonymous methods in C#.  You’ll recall that our extension method takes an argument of type Action, which is a method that takes 0 arguments and returns nothing.  Here we are using the delegate keyword to create a new nameless method.  It takes no arguments because there is nothing inside the delegate() parentheses.  If we wanted a delegate that takes an int as a parameter, we would use delegate(int i), and then we could use i within the anonymous method.  One thing to note that is great about anonymous methods is that they are declared inside the scope of the parent method, so it has access to all the instance variables: parent, and this, as well as the local variable value which is automatically created for us by the set method.  If we were to use a normal method (which we could) we would need to pass in the variables we needed to use as parameters.  Actually if you read the article I linked above, you’ll see that there’s a lot of magic going on under the hood to make it possible to use local and class variables in anonymous methods, but for the most part we can just pretend that the methods exist in a more local scope which always inherits variables in a higher scope.

So what does this method do?  Well, when we set a new parent, we want to remove this category from the old parent so that we aren’t listed as a subcategory anymore.  But remember since we allow Parent to be null if it’s the root category, we need to check if parent is null before we try to remove ourself from it.  Then we want to add ourself to the new parent but again only if it’s not null, so we use our PerformIfNotNull method again.

There’s actually another shortcut for anonymous methods which I’m actually going to use.  Let’s just see what it looks like before I explain it:

set
{
    parent.PerformIfNotNull(() => this.parent.subcategories.Remove(this));
    this.parent = value;
    value.PerformIfNotNull(() => value.AddSubcategory(this));
}

We’ve replaced the delegate keyword with just an empty set of parentheses, and we use a little arrow thing.  Also notice we got rid of the inner curly braces and semicolon from the previous example.  What this means is that we’re defining a method that takes 0 parameters.  This is really just a minimal use of lambda expressions to shorten the syntax slightly, but lambda expressions are more powerful than that.  This article describes lambda expressions pretty well and gives a little more insight into what you can do with them.

Before wrapping up, I mentioned earlier that we wanted to do some parameter validation and throw exceptions if the parameters passed in weren’t valid.  Well it sure would be nice if we could unit test that.  Well we can.  Let’s take a look at two of our tests.

 

[Test]
public void ChangeCategoryTest2()
{
    var cat1 = new Category(root);
    var cat2 = new Category(root);
    Assert.Throws<ArgumentException>(() => testRecipe.ChangeCategory(cat2, cat1));
}

[Test]
public void ChangeCategoryNullTest1()
{
    var cat2 = new Category(root);
    Assert.Throws<ArgumentNullException>(() => testRecipe.ChangeCategory(cat2, null));
}

 

The first one should throw an ArgumentException because ChangeCategory is supposed to move the recipe from the first category to the second and testRecipe isn’t in cat2.  For the 2nd test we throw an ArgumentNullException because one of the categories passed in was null.  I upgraded to NUnit 2.5 which is in Beta3 right now.  The reason is because of the new cleaner syntax for asserting that an exception is thrown.  Previously you’d have to declare an attribute on the test that it expects an exception, but that just means that that exception is thrown anywhere in the test.  To capture an exception being thrown specifically from one method call, we need to either use the new Assert.Throws syntax in NUnit 2.5 or we need to put an ugly try/catch block around the code in question.  This post describes how the different ways of capturing an exception in NUnit can be done.  (Just a note, the last example with getting the parameters of an exception didn’t work for me, so maybe it was changed, since it’s still in Beta right now.)  You’ll notice I pased in the method as a lambda expression.  You’ll see lambdas beng used fairly often in the codebase.

 If you want to look at the code from this post you can either look at it here or check out revision 14 from the svn repository.

April 26, 2009

Detour into Python and optimizations (Part 2)

Posted in Python tagged , , , , at 6:45 pm by davy803

In my last post, I showed you my first implementation of  a simple word game using an A* algorithm.  I also mentioned that I managed to optimize it by two orders of magnitude.  It’s also worth noting that which direction you go in matters a fair amount.  For example, in the test I showed at the end of my last post, I was converting from “poets” to “verse”  and that took 189 seconds.  However if I go the other way and tried to convert from “verse” to “poets” it only takes 24 seconds.  I’m fairly certain it has to do with the branching factor and the number of different words that can be made from each one.  I tried to first see the branching factor of each the initial branch, but in this instance they both returned 4 words, so it didn’t make any difference other than the slight overhead of the first check being slower.

From that information it seems that the expensive branching is further down the line, and we’d have to keep going down until we find it and then switch directions.  Alternatively, it seems like it might be a good candidate for a Bidirectional Search, but that seems a little more complex than I’d like for a simple program, and the slowness is well isolated to a specific call within the algorithm, so let’s focus on optimizing that.

Let’s get started and look at the first optimization made:

The first thing I noticed was that that len is called 32 million times.  Looking at our distance method we see that len is called twice for input validation:

def distance(word1, word2):
    if len(word1) != len(word2):
        raise ValueError("Word length do not match")
    matches = 0
    for i in range(len(word1)):
        if word1[i] == word2[i]:
            matches += 1
    return len(word1) - matches

Now if I were developing a library for external use, it might be good to leave the check there for the sake of fail fast, but for a one-off program that I know verifies the input before it’s passed to the function, it’s unnecessary, and better left for either a debug assert (which I haven’t learned how to do yet) or unit tests.  What happens if I remove those 2 lines and try again?

Result(1):
(poets:verse) 187.18 -> 154.42 (22%, 22%) 
(verse:poets)  23.79 ->  18.74 (27%, 27%)

The format I’ll be using is shown above where “Results(1)” means it’s the first optimization, times are in seconds, and the first % is percent improvement from the previous version, and the second % is percent improvement from the initial version in my first post.  

A respectable improvement for a simple change.  But there’s another spot that we do unnecessary checking:

def getchildren(word, wordlist):
    return [ w for w in wordlist if len(word) == len(w)
            and distance(word, w) == 1 ]

For every word in the wordlist we check if that word has the same length as the word we’re finding children of.  Well we already know that they are because we filtered out wordlist before we passed it to the AStar function.  So let’s take out that check, which give this:

def getchildren(word, wordlist):
    return [ w for w in wordlist if distance(word, w) == 1 ]
Result(2):
(poets:verse) 154.42 -> 101.82 (52%, 84%) 
(verse:poets)  18.74 ->  13.91 (35%, 80%)

Now that seems may seem a little surprising at first if you remember that getchildren is only called about 1000 times compared to the 5 million times distance is called, but the list comprehension is actually a foreach loop, so for each time getchildren is called, len is called twice for EVERY word in wordlist.

The next optimization is something I mentioned in the last post that seemed obvious in hindsight but didn’t strike me until this stage in the optimization game.  And that is the fact that our distance method counts the number of letters that are the same and then subtracts it from the total length.  What we want is the letters that are different so we can just do that directly:

def distance(word1, word2):
    difference = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            difference += 1
    return difference

That eliminates a single call to len and a subtraction operator, but every little thing counts right?  Well it does when you’re doing it 5 million times.  Here’s the results:

Result(3):
(poets:verse) 101.82 -> 79.30 (28%, 136%) 
(verse:poets)  13.91 -> 11.92 (17%, 100%)

We’ve doubled the initial speed, which is great.  It’s still a fair bit slower than I’d like though.  I was at a bit of a loss as to where I should optimize from here, so I asked the great people over at Stackoverflow and got a lot of good advice and suggestions (I recommend you check it out after reading this post).  It was pointed out that there’s a reason they left out the standard for loop that most other popular languages have, and even though you can fake it with the range method, it’s more “Pythonic” to iterate through the actual list.  

I didn’t consider this before because well I had to iterate through the letters of 2 words at once.  Turns out Python has a way to deal with this: the zip(list1, list2) method (where a “list” here just means any collection that’s iteratable, which I was happy to find out includes strings).  What zip does is it takes 2 lists and creates a list of tuples.  To show you what I mean, this is the result of zip(“ABC”, “abc”):

[(‘A’, ‘a’), (‘B’, ‘b’), (‘C’, ‘c’)]

Here is what distance looks like after changing to use zip:

def distance(word1, word2):
    difference = 0
    for x,y in zip (word1, word2):
        if x != y:
            difference += 1
    return difference

Multi-variable assignment is totally sweet!  That’s a lot more elegant looking, but how does it perform?

Result(4):
(poets:verse) 79.30 -> 74.59 ( 6%, 151%) 
(verse:poets) 11.92 ->  9.18 (30%, 159%)

This seemed to help the 2nd case a lot more than the first.  Why?  I have no idea, but I’ll take any kind of optimization I can get.  (Although I’d be nice if it helped the slower case more instead of the one that’s already fast)

The next thing that was pointed out to me was the fact that I’m counting the number of differences, when all I want to know (at least for the purposes of getchildren) is whether or not they differ by one letter.  I can stop checking at that point.  I still need the actual distance for calculating the h_score, so I created a new function called is_neighbors that returns true if there is a difference of exactly because that way it can stop checking when the difference is more than one, because we know it’s not a neighbor.  Here’s what that looks like:

def is_neighbors(word1,word2):
    different = False
    for c1,c2 in zip(word1,word2):
        if c1 != c2:
            if different:
                return False
            different = True
    return different

What this does now is to flag the word as different if one letter is found to be different.  If a second letter is found to be different when the flag is already set, then we can return False right away without checking the remaining letters.  If that doesn’t happen then that means either the different flag was set meaning one letter was different, or it’s not set meaning they were the same word.  Let’s see how much this helps:

Result(5):
(poets:verse) 74.59 -> 70.14 (6%, 181%) 
(verse:poets)  9.18 ->  8.83 (4%, 169%)

Another small gain, but still an improvement nonetheless.  But where do we go now?  Well I was directed to the izip function in the itertools module instead of zip because it returns an iterator instead of generating a list.  A list generates more overhead because it is indexed and allows for random access, but we don’t need this since we just need to iterate through the letters in order exactly once.  I won’t bother with a code snippet for this one since all I did was “from itertools import izip” and changed zip to izip in distance and is_neighbors.  Here’s the results:

Result(6):
(poets:verse) 70.14 -> 41.69 (68%, 349%) 
(verse:poets)  8.83 ->  5.02 (76%, 374%)

Wow! It’s amazing what the right data structure can do.  At this point I was going to consider it done.  It’s still not lightning fast, but I didn’t really think I could squeeze much more out of it.  Mark Ransom left a comment on my question that he wanted me to try out the latest version of his answer.  He first checks if the first letter is different, and if it is, then see if the rest of the string is identical.  If it is then we can return true, then it’s different by exactly one letter (the first one), otherwise there’s more than one letter that’s different.  We don’t care which ones.  If the first letter is the same then we continue as usual.  Here is his solution:

if word1[0] != word2[0]:
        return word1[1:] == word2[1:]
    different = False
    for i in range(1, len(word1)):
        if word1[i] != word2[i]:
            if different:
                return False
            different = True
    return different

We already determined that zip/izip is faster than range but I wanted to try it as posted first.  (He later said he meant to use izip, and he did in his testing, just forgot to update his answer).  The “word[1:]” syntax is called slicing which is kinda like substring except that it works with any indexable collection.  If the first letter is omitted it is assumed from the beginning and if the last is omited it is assumed to the end.  As a side-note, an interesting note is you can use list[:] it create a copy of the whole list.  Anyway, let’s see what the profiler has to say about this short-circuit method.

 

Result(7):
(poets:verse) 41.69 -> 29.82 (40%, 528%) 
(verse:poets)  5.02 ->  3.59 (40%, 563%)

 

I was initially shocked at how much of a difference that made.  It didn’t make sense to me how that would speed it up so much, and that’s even with reverting to using range which we’ve shown is much slower than izip.  Let’s consider this for a second though.  Most of the time the first letter is different.  We don’t need to compare the rest of the letters one at a time, a straight equality comparison on 2 strings is much faster.  Well you might say we were already cutting it off as soon as we found a 2nd letter that was different, and that’s what I thought at first.  But really what happens is that if the next letter to differ isn’t until the last letter, then we still ended up checking the whole word.  If there is only one letter different, again we end up checking the whole word.  With this, if the first letter is different, which is very likely given that there’s 26 letters in the alphabet and thus only a 1 in 26 chance that the first letter is the same (okay that’s not true because the list consists of real words and not every combination of possible letters, but it’s close enough for the sake of example) so 25/26 times we only need to check a single letter and we know the answer with a simple straight comparison.

Let’s see what happens if we change it back to use izip

 

def is_neighbors(word1,word2):
    if word1[0] != word2[0]:
        return word1[1:] == word2[1:]
    different = False
    for x,y in izip(word1[1:],word2[1:]):
        if x != y:
            if different:
                return False
            different = True
    return different

 

Instead of zipping the whole word this time, we only need to zip starting from the 2nd letter.  So let’s see how this compares:

 

Result(8):
(poets:verse) 29.82 -> 27.88 (7%, 571%) 
(verse:poets)  3.59 ->  3.38 (6%, 604%)

 

Not quite as big of a difference as what we saw before when we first switching to izip, but that confirms our earlier suspicions that the vast majority of the time we know the answer after checking a single letter.

So now we’re done right?  I thought so too.  Another person, Sumudu Fernando, suggested an entirely different approach:

 

If your wordlist is very long, might it be more efficient to generate all possible 1-letter-differences from ‘word’, then check which ones are in the list? I don’t know any Python but there should be a suitable data structure for the wordlist allowing for log-time lookups.

I suggest this because if your words are reasonable lengths (~10 letters), then you’ll only be looking for 250 potential words, which is probably faster if your wordlist is larger than a few hundred words.

 

At first I was skeptical.  For each word you had to generate a list of all strings that was one letter off,  and that’s huge, for a 5 letter word, there’s 25 possibilities foe each letter, so that’s 25 ^ 5, that’s 9 million strings, I don’t know where you’re getting 250 potential words for a 10 letter word from!

I was actually going to write a comment to that effect, until luckily I caught my own mistake before I posted it.  That’s all possible words, that don’t share any letters in common.  We want words with exactly one letter in common, which is what he said.  The number of possibilities was 25 * 5 not 25 ^5, and 125 is a lot more reasonable than 9 million.  I still felt that generating all those words would bring some overhead, but it’s possible that it could speed it up, so I tried it out and this is what it looked like:

 

def one_letter_off_strings(word):
    import string
    dif_list = []
    for i in xrange(len(word)):
        dif_list.extend((word[:i] + l + word[i+1:] 
            for l in string.ascii_lowercase if l != word[i]))
    return dif_list
def getchildren(word, wordlist):
    oneoff = one_letter_off_strings(word)
    return ( w for w in oneoff if w in wordlist )

 

Someone else introduced me to xrange instead of range, which is analogous to what izip is to zip.  The extend function of a list adds the element of a 2nd list to the first.  You may notice I did a little magic with the segment:

word[:i] + l + word[i+1:]

Remember the slicing we did earlier, well for each i, we create a word that’s identical to word and replace it with the letter l (that’s an L not the number one, probably should’ve used something less confusing, but I wasn’t thinking about that at the time).   Slicing includes the first index, but excludes the last one, so for i=0 and the word “hello”, you get word[0:0] + l + word[1:end], which translates into “” + l + “ello”, then “h” + l + “llo”, and so forth.  We do this for every letter in the alphabet that isn’t equal to the the actual one in the word.

We then change getchildren to loop through the oneoff list and return a tuple of words in the oneoff list that are also in wordlist.  A tuple is basically a read-only list that has a slight performance bonus since it’s read-only.  The one_letter_off function doesn’t look too pretty and probably can be optimized a bit, but I’m not quite sure how, so let’s just see how this does:

Result(9):
(poets:verse) 27.88 -> 34.40 (-23%, 444%) 
(verse:poets)  3.38 ->  3.74 (-11%, 536%)

Ok, this did a little worse, and I can’t really think of any ways to optimize the one_letter_off function, so this is probably a dead-end.  A closer look at the profiler shows that my gut feeling was wrong and that the one_letter_off function ended up being an insignificant amount of time.  The majority of the time was spent in this line:

return ( w for w in oneoff if w in wordlist )

Well, I’m stumped.  I don’t see how much simpler it could get than that.  What if I switched wordlist and oneoff?  What are we really looking for anyway?  We’re looking for the intersection of the 2 lists.  Intersection… that’s a term that’s often applied to sets in set theory.  I wonder if there’s a built-in fast way to do that.  With a bit of google-fu it seems that we can convert a list to a set which is another built-in type, and we can get the intersection with the bitwise and operator (&).  This is what it looks like:

def getchildren(word, wordlist):
    oneoff = one_letter_off_strings(word)
    return set(oneoff) & set(wordlist)

Should get a bit of an improvement with this, I’m sure they optimized set operations on sets.

Result(10):
(poets:verse) 27.88 -> 2.25 (1139%,  8219%) 
(verse:poets)  3.38 -> 0.23 (1370%, 10243%)

!@$!!  Really?  Are you serious?  I had to run it again to make sure it wasn’t a fluke.  Ran it with different inputs to make sure the answer was correct.  Holy $!@%.  Apparently set operations are absurdly fast.  I don’t know how it’s implemented under the hood, but WOW!

For fun I added some little debug prints to see what kind of data it was working with since it seemed like it was checking a lot of words.  What I found was that, there were lots of words with the same f_score, but different h_score.  The algorithm cares about f_score only, but it seems that if the f_score is the same, we’d have more luck with trying words that are closer to the goal first, or in otherwords, have a secondary the h_score if f_score is the same.  Here’s what changed in the main algorithm function:

def AStar(start, goal, wordlist):
    import Queue
    closedset = []
    openset = [start]
    pqueue = Queue.PriorityQueue(0)
    g_score = {start:0}         #Distance from start along optimal path.
    h_score = {start:distance(start, goal)}
    f_score = {start:h_score[start]}
    pqueue.put((f_score[start], h_score[start], start))
    parent_dict = {}
    while len(openset) > 0:
        x = pqueue.get(False)[2]
        if x == goal:
            return reconstruct_path(parent_dict,goal)
        openset.remove(x)
        closedset.append(x)
        for y in getchildren(x, wordlist):
            if y in closedset:
                continue
            temp_g_score = g_score[x] + 1
            temp_is_better = False
            appended = False
            if (not y in openset):
                openset.append(y)
                appended = True
                h_score[y] = distance(y, goal)
                temp_is_better = True
            elif temp_g_score < g_score[y] :
                temp_is_better = True
            else :
                pass
            if temp_is_better:
                parent_dict[y] = x
                g_score[y] = temp_g_score
                f_score[y] = g_score[y] + h_score[y]
                if appended :
                    pqueue.put((f_score[y],h_score[y], y))
    return None

I highlighted the changes.  I added the h_score to the tuple in the priority queue so that acts as a secondary sort.  This change was actually made just now, as in the time of this posting.  As happy as I was with the previous optimizations, once I noticed all the words being checked that didn’t need to be, I was compelled to give this a try.  Here’s the results:

Result(11):
(poets:verse) 2.25 -> 1.28 (76%, 14523%) 
(verse:poets) 0.23 -> 0.19 (21%, 12421%)

A pretty nice gain if I do say so myself.  One thing to keep in mind though, is that these results are looking at the time for the AStar method.  I did this initially because compared to that, everything else had negligible execution time.  It actually takes about 1 second to clean the wordlist, which is not so insignificant now compared to the optimizations done, but for the sake of consistency, and not wanting to wait several minutes for all the earlier tests to rerun, that’s not included in here.  I’m sure that could be optimized as well, but I’m happy with this, so I’m calling it done.  Also, filtering out wordlists by number of letters could easily be pre-calculated so it doesn’t really make sense to bother optimizing that.  There you have it, showed you the optimizations I promised and one freebie.  Guess this goes to show optimizations still matter.  And also profiling is important.  Otherwise I would’ve wasted my time trying to optimize the one_letter_off method in version 9 and completely missed the biggest optimization of all, using sets for intersection.

Well, hope you enjoyed reading that was much as I enjoyed optimizing it.  Until next time!

April 25, 2009

Detour into Python and optimizations (Part 1)

Posted in Python tagged , , , , at 4:48 pm by davy803

Sorry for the lack of updates.  I’ve been distracted for a while because a friend described a word game that is played where you take 2 words and try to convert one into the other by switching one letter at a time, where each iteration is a real word.

e.g.

MOON –> WOLF
GOON
GOOF
GOLF
WOLF

Like any good programmer, the first thing that popped in my head was “Hey I could write a program to solve that! ”  I’ve also been meaning to learn another language for some time, and very reliable sources suggested Python.  From what I read it seemed pretty accepted that Dive Into Python was the best intro to Python for programmers, and so I dove in.

And I’m glad I did.  Python does some pretty amazing things that I could do no justice by explaining here.  For a quick taste, take a look at List Comprehesion and Multi-variable Assignment.  

What the game essentially boils down to is a search for an optimal path through a graph.  I originally thought of it as a tree, but actually with the same start and end points, you could end up generating different trees depending on what path you take, so it’s more accurately described by a simple undirected graph.   The best way to solve this seems to be an A* algorithm.  Dijkstra’s algorithm was also considered, but it assumes that all nodes and edges of the graph are known, and I choose to generate them on the fly.

The general premise of A* is for each node (a word in our case) you know the distance between the start and the current (called g(x)) and you have an estimate to how far you are from the goal (the heuristic, called h(x)).  In our case the heuristic would be the number of letters that differ.  And since it’s impossible to get to the end in fewer steps, that means that it can never overestimate the number of steps remaining and thus is an admissable heuristic.  It is proven that the A* algorithm will always generate an optimal path.  The way it works is the “score” (f(x)) of each word is the sum of g(x) and h(x)  and you always try the paths with the lowest f(x) first.

Let’s take a look at the algorithm in code:

def AStar(start, goal, wordlist):
    import Queue
    closedset = []
    openset = [start]
    pqueue = Queue.PriorityQueue(0)
    g_score = {start:0}
    h_score = {start:distance(start, goal)}
    f_score = {start:h_score[start]}
    pqueue.put((f_score[start], start))
    parent_dict = {}
    while len(openset) > 0:
        x = pqueue.get(False)[1]
        if x == goal:
            return reconstruct_path(parent_dict,goal)
        openset.remove(x)
        closedset.append(x)
        for y in getchildren(x, wordlist):
            if y in closedset:
                continue
            temp_g_score = g_score[x] + 1
            temp_is_better = False
            appended = False
            if (not y in openset):
                openset.append(y)
                appended = True
                h_score[y] = distance(y, goal)
                temp_is_better = True
            elif temp_g_score < g_score[y] :
                temp_is_better = True
            else :
                pass
            if temp_is_better:
                parent_dict[y] = x
                g_score[y] = temp_g_score
                f_score[y] = g_score[y] + h_score[y]
                if appended :
                    pqueue.put((f_score[y], y))
    return None

Now let’s break it down.  We have and openset and a closedset.  The openset is the list of nodes that we know about.  We have a score for each of these nodes, but we don’t know about that node’s children or their scores yet.  Once we get and score all of a node’s children it goes into the closedset which means we’re done looking at them.  The variable pqueue is a priority queue that contains the same nodes as the openset except it also stores and sorts by the f_score of each node.  Why not just have a priority queue instead of the list?  That was my original thought, but I needed to be able to determine whether a given node was already in openset which we can’t do with a queue.  I could also just sort the list at each iteration but it seemed less efficient.

After that we have the 3 different scores that I’ve already defined above.  They’re stored as dictionaries with the node being the key and the score being the value.  parent_dict stores the parents of each node along the optimal path.   This is updated if a better path is found.

Now we go through the openset and keep adding it’s decendants until we either find the goal or we run out of nodes.  We pull the node with the lowest f_score since that’s what pqueue is sorted by, call it x and put it into the closedset.  (Technically it should go to closed after we finish going through it’s children, but it doesn’t really matter in this case). 

Next we get all the children (neighbors) of x.  If it’s already in the closedset, we already know all we need to know about it, move on.  Otherwise, the distance from the start to this node, y, is the distance to it’s parent, x, plus one.  

“temp_is_better” is used to flag whether we should add y to the openset, or update it with a better path.  “appended” is really just a workaround because we can’t add y to pqueue until we know the f_score.  Basically if y isn’t in the openset add it.  If it is, but the current path to y is shorter than the previously discovered path to y, then update all the info about it.

Well that’s it.

Ok I lied.  There were 3 functions that I didn’t define:  getchildren, distance, and reconstruct_path.  Let’s look at getchildren first:

def getchildren(word, wordlist):
    return [ w for w in wordlist if len(word) == len(w) 
             and distance(word, w) == 1 ]

This is an example of list comprehension in Python.  How you read this is for each word, “w”, in “wordlist” if the length of “w” is the same as the length of the paramter “word”, and the distance between word and w (which I’ll define next) is 1, then add w to the list to be returned.  The backslash indicates the the statement continues on the next line, since Python normally used linebreaks to end statements rather than a semicolon.

That was simple enough, now let’s look at the distance function:

def distance(word1, word2):
    if len(word1) != len(word2):
        raise ValueError("Word length do not match")
    matches = 0
    for i in range(len(word1)):
        if word1[i] == word2[i]:
            matches += 1
    return len(word1) - matches

Here we take 2 words and compare to see how many letters are different between them.  First we make sure they contain the same number of letters and raise an exception if they don’t.   Python doesn’t have the standard for loop and instead everything is a foreach loop.  You can mimic a standard for loop by doing “for i in range(stopvalue)” because range is a built-in function that generates a list of numbers 0 to stopvalue -1.  Now it’s just a simple matter of counting the number of letters that match and subtracting that from the number of letters in the word.  Okay, I know what you’re thinking, and you’re right.  It’d be much simpler to count the number of letters that are different instead of the ones that are the same.  It didn’t strike me at the time of writing the first version of the program, but I correct that later on.

Now for the final missing function:

def reconstruct_path(parent_dict,node):
     if node in parent_dict.keys():
         p = reconstruct_path(parent_dict,parent_dict[node])
         p.append(node)
         return p
     else:
         return []   

This is called when we find the goal, and all it does is backtrack recursively through all the parents nodes starting from the goal and finally returning a list of the path.

Now that we have the algorithm down, let’s actually use it:

wordfile = open("realwords.txt")
wordlist = cleanentries(wordfile.read().split())
wordfile.close()
words = []
while True:
    userentry = raw_input("Hello, enter the 2 words to play with separated by a space:n ")
    words = [w.lower() for w in userentry.split()]
    if(len(words) == 2 and len(words[0]) == len(words[1])):
        break
print "You selected %s and %s as your words" % (words[0], words[1])
wordlist = [ w for w in wordlist if len(words[0]) == len(w)]
answer = AStar(words[0], words[1], wordlist)
if answer != None:
    print "Minimum number of steps is %s" % (len(answer))
    reply = raw_input("Would you like the answer(y/n)? ")
    if(reply.lower() == "y"):
        answer.insert(0, words[0])
        print "n".join(answer)
    else:
        print "Good luck!"
else:
    print "Sorry, there's no answer to yours"

Python makes working with text files super easy.  As you can see, I opened the file in the first line.  The 2nd line might need some explaining.  First if you don’t specify a mode for opening a file, the default is readonly mode as text.  (I’m not sure how it handles encoding whether it’s ASCII, ANSI or Unicode, but for our purposes it’s just a plain text file and it just works.)  Specifying read() without parameters reads to the end of file, and since we opened in text mode it returns it as a string.  The split() method takes a string and splits it up into a list of strings for each word.  You can specify a word delimiter, but if you don’t it is assumed to be any kind of white space (space, linebreak, tab).  I wrote a quick method called cleanentries() to clean up some formatting specific to this file, it’s not real robust so not really worth going into. 

After you’re done with a file you should always close it, so I do.  Now I need to ask the user for 2 words.  I use the split method again and convert all the words to lowercase.  Python doesn’t have a do-while loop, so to work around that people suggesting doing while True and then break on the opposite condition.  Here I make sure that exactly 2 words are entered, and that each word has the same number of letters.

I let the user know what words they entered and then remove all the words from the wordlist that don’t have the same number of letters as their input.  Now I use my magic algorithm, and if there’s a solution I tell them how many steps it takes and give them the option of whether or not they want to see the actual solution.

That’s it, all fine and dandy.  Now let’s run it.  One set that my friend did by hand was to convert from “poets” to “verse”, so let’s give that a try.

That took forever.  How can I speed this up?

There’s a saying about performance, always measure and profile.  Luckily Python comes with a pretty easy to use profiler out of the box.  After skimming through this guide, I found out all I needed to do was the open up a command prompt to the folder where my file is saved and type “python -m cProfile [scriptname].py”  So let’s see what it tells us:

wordgameprofileWhat the screenshot doesn’t show is that 156 seconds is in the “raw_input” method which was basically waiting for user input so that doesn’t count, which leaves 189 seconds if you subtract the input time from the cumulative time for WordGame.py:1((module)).  About 1 second went to cleaning the entries from the list, and a little misc time here and there and you end up with the bulk of the time being in the AStar method.  Cumulative time counts the entire time spent in the method, including other method calls, where  total time excludes the time in other methods.  You’ll see that the majority of the time is spent in the distance method and that it’s called a whopping  5.3 million times.  Obviously some optimization needs to go in there.  Also not on the screenshot, but the “len” function takes up 57.6 seconds and is called 32million times.  len is a built-in function, so we can’t really speed up that implementation, but we could call it less often.

In my next post I’ll go into how I optimized the program from taking 189 seconds as you see here, down to 2.25 seconds through a series of optimizations with some help from the people over at Stackoverflow.com.

April 19, 2009

Diving into Test Driven Development

Posted in Chefbook at 10:47 pm by davy803

I started writing a post where I got into desiging the classes in plain English (well, in English anyway) and decided to reflect on the things that I would need to test for each of the functions.  What I ended up doing was just writing the unit tests in clunky natural language form which was less eloquent that just writing it up in code, so I ended up scrapping the post and just writing the tests.

Before I go any further, let me put a disclaimer that I’m not actually following true TDD to the letter.  Instead of using TDD for my design, I’m coming in with a basic design in mind and using some TDD techniques to refine that design.  To see true TDD in action, check out this article.  I can see what they mean when they say that TDD isn’t so much a process for testing as it is a process for designing.  First I stub out the methods required for each feature that was described in the spec.  I started out with the Category class.  Below are the requirements for the Categories:

  • Create
  • Rename
  • Delete
  • Move to another parent category (or none)
  • Add Recipe
  • Categories can contain sub categories
  • Categories can contain recipes
  • Categories display the recipes within them, and also the recipes within their sub-categories

The stubbed out recipes look like this (note I arranged the methods in the same order as the features are listed above for illustrative purposes.  They’ll be rearranged in a more logical order when I go about making the tests pass) :

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System.Text;

namespace Chefbook.DataObjects
{
    /// <summary>
    /// Represents a category in a hierarchy structure that can contain items
    /// </summary>
    public class Category
    {
        /// <summary>
        /// Constructor for a category with a given parent and category name
        /// </summary>
        /// <param name="parent">Category that this Category is contained in.  Null if root category</param>
        /// <param name="name">The name of the Category</param>
        public Category(Category parent)
        {

        }

        /// <summary>
        /// Gets or sets the name of the category
        /// </summary>
        public string Name { get; set; }

        /// <summary>
        /// Removes this folder from its parent
        /// </summary>
        public void Delete()
        {

        }

        /// <summary>
        /// Gets or sets the parent category
        /// </summary>
        public Category Parent { get; set; }

        /// <summary>
        /// Adds a recipe to this category's direct recipes
        /// </summary>
        /// <param name="recipeToAdd"></param>
        public void AddRecipe(Recipe recipeToAdd)
        {

        }

        /// <summary>
        /// Gets a readonly list of direct subcategories of this category
        /// </summary>
        public ReadOnlyCollection<Category> SubCategories
        {
            get { return new ReadOnlyCollection<Category>(new List<Category>()); }
        }

        /// <summary>
        /// Gets a readonly list of recipes contained directly in this category 
        /// not one of its subcategories
        /// </summary>
        public ReadOnlyCollection<Recipe> DirectRecipes
        {
            get { return new ReadOnlyCollection<Recipe>(new List<Recipe>()); }
        }

        /// <summary>
        /// Gets readonly list of all recipes contained in this category or one of its subcategories
        /// </summary>
        public ReadOnlyCollection<Recipe> AllRecipes
        {
            get { return new ReadOnlyCollection<Recipe>(new List<Recipe>()); }
        }
    }
}

One method per feature, pretty straight forward.  For the properties I had to implement a getter that returned the proper type, otherwise it won’t compile, and I can’t run the unit tests.  If you’re unfamiliar with C# properties, they’re basically get method that you can use as if they were instance members, so for instance I can say myCategory.SubCategories.Count; instead of the old way which would be myCategory.GetSubCategories().Count(); The real methods are actually created in the background by the compiler, and they are just syntactical sugar that make them easier to work with. Automatic properties which I used for Parent and Name are a new feature in C# 3.0 that can automatically generate a private backing variable.

System.Collections.ObjectModel is where ReadOnlyCollection resides, which is just a wrapper around IList that doesn’t allow modifications.

Now that we have the method stubs, let’s take a look at the code for the unit tests:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using NUnit.Framework;
using Chefbook.DataObjects;

namespace UnitTests.DataObjectsTests
{
    [TestFixture]
    public class CategoryFixture
    {
        private Category root;
        private Category testCategory;

        [SetUp]
        public void Init()
        {
            root = new Category(null);
            testCategory = new Category(root);
        }
        [Test]
        public void ConstructorTest()
        {
            Assert.AreEqual(root, testCategory.Parent, "Constructor Parent test failed");
            Assert.AreEqual("", testCategory.Name, "Constructor Name test failed");
            Assert.AreEqual(0, testCategory.SubCategories.Count, "Constructor SubCategories test failed");
            Assert.AreEqual(0, testCategory.DirectRecipes.Count, "Constructor Recipes test failed");
        }

        [Test]
        public void RenameTest()
        {
            testCategory.Name = "Tasty";
            Assert.AreEqual("Tasty", testCategory.Name, "Rename test failed");

        }

        [Test]
        public void DeleteTest()
        {
            var parent = testCategory.Parent;
            testCategory.Delete();
            Assert.IsFalse(parent.SubCategories.Contains(testCategory),"Delete test failed");
        }

        [Test]
        public void ChangeParentTest()
        {
            var oldParent = testCategory.Parent;
            var newParent = new Category(root);
            testCategory.Parent = newParent;
            Assert.IsFalse(oldParent.SubCategories.Contains(testCategory),"Not removed from old parent");
            Assert.AreEqual(newParent, testCategory.Parent, "New Parent not set");
            Assert.IsTrue(newParent.SubCategories.Contains(testCategory), "Not added to new parent");
        }

        [Test]
        public void GetAllRecipesTest()
        {
            var recipe = new Recipe(testCategory);
            var subCategory = new Category(testCategory);
            var subSubCategory = new Category(subCategory);
            var nestedrecipe = new Recipe(subSubCategory);

            Assert.Contains(recipe, testCategory.AllRecipes, "AllRecipes didn't contain direct recipe");
            Assert.Contains(nestedrecipe, testCategory.AllRecipes, "AllRecipes didn't contain nested recipe");
        }

        [Test]
        public void GetDirectRecipesTest()
        {
            var recipe = new Recipe(testCategory);
            var subCategory = new Category(testCategory);
            var subSubCategory = new Category(subCategory);
            var nestedrecipe = new Recipe(subSubCategory);

            Assert.Contains(recipe, testCategory.DirectRecipes, "DirectRecipes didn't contain direct recipe");
            Assert.IsFalse(testCategory.DirectRecipes.Contains(nestedrecipe), "DirectRecipes contained nested recipe");            
        }

        [Test]
        public void AddRecipeTest()
        {
            var recipe = new Recipe(root);
            testCategory.AddRecipe(recipe);
            Assert.Contains(recipe, testCategory.DirectRecipes, "Recipe wasn't in DirectRecipes of the category");
            Assert.Contains(testCategory, recipe.Categories, "Category wasn't in recipe's list of categories");
        }
    }
}

After looking at some of the examples here, I was able to come up with some tests to test all the methods I wrote above.  You’ll notice I added a reference to NUnit.Framework.  You’ll also notice that the class is marked with [TestFixture] attribute to indicate that is is a class that contains tests, and each test is marked with the [Test] attribute.  You’ll also see that there’s an Init() method that’s marked with the [SetUp] attribute that indicates this method should be run before every test.  The example I linked puts the attribute declaration on the same line as the class/method declaration, but I think it looks cleaner and is more standard to put it on a separate line.

Now that I have my tests laid out, let’s try running the tests.  Here is what it looks like in the NUnit GUI test runner:

failingunittestsYou’ll notice that the RenameTest is actually passing.  This is because C#’s automatic properties already gave us the functionality, and it would’ve been more work to make up some result to make it fail than it was to just have it passing as is.  This violates step 2 of the TDD proceedure:

2. Run all tests and see if the new one fails

This validates that the test harness is working correctly and that the new test does not mistakenly pass without requiring any new code.

The new test should also fail for the expected reason. This step tests the test itself, in the negative: it rules out the possibility that the new test will always pass, and therefore be worthless.

That’s ok for me though.  I’m not so much interested in following methodology to a T for it’s own sake as much as I’m interested in producing better code.  This process actually resulted in me adding the AddRecipe method and the corresponding entry to the spec.  It was just kinda implied but writing the tests made the need for it apparent because in order to test whether it would properly return the list of recipes, I needed a way to add recipes to a category.  I also needed to construct a recipe, and in doing so realized that the name doesn’t need to be part of the constructor since the user may not enter one right away.

That’s all for tonight though.  Next time we’ll get into making these tests pass, and I’m sure in the process will end up writing more tests.   If you want to see the solution in it’s current state, check out revion 12 from svn, or browse the project directly from the Google Code web interface.

YAGNI, You Ain’t Gonna Need It

Posted in Chefbook tagged , , , , at 10:35 am by davy803

 

I want to take a moment to talk about YAGNI.  YAGNI is somewhat of a natural extension to Release Early, Release Often which I discussed in my last post.  YAGNI tells you that “you ain’t gonna need it” meaning don’t over-engineer a problem and don’t add something until you know you’re going to need it.  You can find a little more discussion on it here.  It doesn’t mean that you should ignore good programming principles and just hack something together as quick as you can.  It implicitly says that you don’t try to anticipate what’s need.

Th principle applies to more than just coding, it also applies to actual working functionality.  Programmers (and people in general) are notoriously bad at predicting what they want or will need in the future.  Even if you do have a general idea that you’ll need it in the future, you probably don’t have a good understanding of the exact details and the kinds of problems that will come up.  It’s not a phrase that’s meant to be taken literally, but more of a something to take into consideration.  It’s easier to change something that’s simple than something that’s complex.  The key here is to be flexible to change.  For the most part you’re going to have pretty inaccurate idea of what users want.  Get something simple out there an let users tell you what they want instead of trying to do guesswork.

There are some notable times where YAGNI doesn’t apply, one of which is when there’s already a well known solution to a well known problem that you are just implementing (maybe in a different language, a different platform, maybe just for your own understanding).  An example is if you’re creating an RSA encryption program, the algorithm is well known, there’s been decades of research into it and you can be pretty sure that it’s not going to change any time soon.  Most of the time this isn’t the case, and you are dealing with unknowns, and it’s best not to guess when you don’t need to.

As far as Chefbook goes, after I defined the spec for version 1.0, I noticed that some of the data in my database schema I wasn’t going to be using.  I had anticipated the need for them, but I don’t need them yet, so I removed them.  I took out the ImagePath of a Recipe, because I’m not going to have the ability to add a picture to recipes initially.  I also removed the RecipeReview table (and the corresponding class) entirely.  I’m not even sure anymore why I put that there in the first place, other than the fact the recipe sites online usually have reviews, and I find them useful.  But initial release is a single-user app, and reviewing your own personal recipes doesn’t seem like a highly requested feature that’s worth spending time on upfront.  It can always be added later, so away it goes.  You can see the comparison below:

database-schema

Old Schema

New Schema

New Schema

You’ll also see that I fixed up some stuff as far as primary keys go, because a RecipeIngredient can’t exist outside of a Recipe, so RecipeId+IngredientId is the Primary Key.  Also to ensure that the RecipeId+CategoryId pair are unique, I did away with the artifical 3rd identifier and now recognize the pair as the primary key.  Choosing the right primary keys is important, and it’s good to get this kind of stuff out of the way early while still the the design stages because they are hard to change later.  Note that this doesn’t contradict YAGNI, because YAGNI doesn’t say be sloppy in your design.  Choosing the right keys isn’t a feature, it’s good design, and you’re always gonna need that.

Now there is one thing that I’m going to add where YAGNI truely doesn’t apply.  Now that I’ve already changed the database schema several times, it’s become quite obvious that I do need a way to transition data from one version of the database schema to another, and that’s not something that can be done just as easily later as it is upfront.  Even though for a working first version I don’t technically need a way to migrate data from a previous version to a newer version, not doing so could potentially leave users with the option of either not upgrading or losing their previous data, neither of which are acceptable, so having a way to upgrade from an older to a newer version with data intact is vital to the project and I will be added to the spec.

Next page