In the past, I've asked a
couple of times
about
how you design algorithms. Of course, I'm not talking about algorithms with obvious solutions
or those which are already well-known.
Lately, I've been working on a project that I can't share too much about, where we're exploring what is, to my knowledge, mostly virgin territory. One thing I have learned that I
can share, is something about algorithm design.
It seems obvious to me now, and may be to you, but before recently, I had never thought about it: you can use an iterative approach in designing new algorithms. In the past, I had thought the opposite - since as a unit, the algorithm would rarely have the ability to be broken into chunks for testing purposes, how could we break it into chunks for iteration purposes?
But with the latest one we've been working on, we were able to take an iterative approach in it's design.
The process went something like this:
- Decide what it is you need to accomplish - not necessarily how to accomplish it.
- Based on that, find the parameters to the algorithm that will vary in each invocation.
- Fix the parameters, and run through the algorithm. This will be it's simplest version.
- Go ahead and write it if you want - but be aware it will likely change dramatically between now and when you are finished.
- For each parameter p, vary it and go through the algorithm keeping the rest of the
parameters fixed.
- When you've got that working, now you can start varying combinations of parameters.
Always observe what your algorithm is outputting versus expected output, and
fix it when it's wrong.
- Finally, allow all the parameters to vary as they would in working conditions.
- Clean it up, keeping its essence.
A final bit of advice: don't force looping when the code won't go there. The code
I was working on could have had any number of nested loops, and I spent a long time trying to find the relationships behind the parameters and their depth in the loop structure, in an
attempt to find a way to fix the number of loops (so we don't have to change the code each time
we need another loop in the nest). It was quickly becoming a hard-to-understand mess.
Instead, take a few minutes to step back and look at it from a distance. Do you really need to be looping? In my case, not as much as I thought.
Use recursion when the code wants to be recursive. (If you still really want to avoid recursion, you'll probably need to simulate it with your own stack - but why do all the extra work?)
That iterative approach to algorithm design worked for me. It turned what at first seemed like a daunting, complicated algorithm into just several lines of elegant, understandable code.
Do you have an approach to designing algorithms whose solutions you don't know (and to be clear - can't find via search)?
Hey! Why don't you make your life easier and subscribe to the full post
or short blurb RSS feed? I'm so confident you'll love my smelly pasta plate
wisdom that I'm offering a no-strings-attached, lifetime money back guarantee!
Leave a comment
This may seem like a silly comment, but when I am developing a really complex algorithm, I like to scatter in ASSERT comments. Something like this:
<!---
ASSERT: At this point, no matter how data XYZ came into the function, we now have a standardized query object.
--->
While this has no programmatic functionality, it is a mental trick that I do to compartmentalize the aspects of my algorithms. Without actually doing it, I can mentally black-box chunks of code by just following my ASSERT statements.
Sometimes, when things are extremely complex, I will actually go and try to write my ASSERT statements BEFORE I write much of the code. This way, it provides me while "mile markers" that I can aim for.
Posted by
Ben Nadel
on Mar 10, 2008 at 08:33 AM UTC - 5 hrs
That's not silly at all. In fact, I will try that - I'm usually just outputting things, but asserting them would make it stronger and crash when something is not expected - that's less work my brain would need to do when looking at the output.
I really think that's a good idea. I've been doing that on homeworks to "prove" something works like it should (in lieu of writing unit tests), but hadn't thought about it in the way you've just described.
I'll certainly use it next time. Thanks for the great idea!
Posted by
Sammy Larbi
on Mar 10, 2008 at 09:02 AM UTC - 5 hrs
Sammy, give it a try. But, just to be clear, these aren't programmatic asserts like:
Assert( HasPolicy, "boolean", true )
... or anything like that. These are just CF comments that help me divide and conquer the code in my head. I think you get the benefits of itemized development without the overhead of extra method calls.
Posted by
Ben Nadel
on Mar 10, 2008 at 09:09 AM UTC - 5 hrs
Oh, I thought you meant programmatic asserts. =) In any case, it's certainly good to sketch out the algorithm before coding it anyway - but still, you gave me the idea.
Posted by
Sammy Larbi
on Mar 10, 2008 at 10:14 AM UTC - 5 hrs
Sounds good to me :)
Posted by
Ben Nadel
on Mar 10, 2008 at 10:21 AM UTC - 5 hrs
Wouldn't writing unit test or spec (like Rspec) do away totally with Ben's assert comments? Besides, having specs and unit tests improve the debug-ability of the algorithm. Do you have any comment on building algorithm with a pure functional approach versus and oo-approach?
Posted by
Dat Chu
on Mar 12, 2008 at 10:23 AM UTC - 5 hrs
@Dat Chu,
You are correct purely from a code-works view point. However, my ASSERT statements not meant for the compiler or the run-time environment; they are meant to let me (or any other developer) get a better sense of what the code is doing or should be doing. They are for readability and maintainability, not for unit testing or regression testing.
Those are important too, but for different reasons.
Posted by
Ben Nadel
on Mar 12, 2008 at 10:55 AM UTC - 5 hrs
@Dat: I have no comments on building algorithms with a functional approach verus OO, but I admit I may not fully understand the question, and that could be why.
I see your point about the unit tests and/or specs, but my comment has become long and somewhat hard to follow, so I'm going to see if I can sort my thoughts out a little better and post it as a top-level post as opposed to a comment.
Posted by
Sammy Larbi
on Mar 12, 2008 at 11:55 AM UTC - 5 hrs
PS: I'll probably get to that by Monday. As you know, the week before Spring Break can get kind of hectic. =)
Posted by
Sammy Larbi
on Mar 12, 2008 at 11:55 AM UTC - 5 hrs
