I’m awesome and I didn’t even realize it

So this week I was playing around with MBA, working on some experimental code to perform a stochastic search over the solution space instead of an exhaustive search. The plan was to Somehow choose to fix the number of missings in certain ranges in the protein at each iteration based on the results of the previous iteration. Not wanting to rush into this without some idea of what would make a good Somehow, I threw together a quick-and-dirty exhaustive search that used the same constraints mechanism that stochastic search would.

Guess what.

The constrained-exhaustive search appears to run an order of magnitude faster than the ordinary exhaustive search. As in, what used to take over an hour now takes twelve minutes. As in, what used to take over a day now takes two and a half hours! Constrained-exhaustive search even plays more nicely with RMI-based parallelization than the old exhaustive search.


I certainly wasn’t expecting that that I threw together after making big simplifications to the ideas Vitek and I had talked about, and intended to use only to see what happens when you throw constraints into the mix.

The moral? Try the stupidly simple approach first. You might be surprised just how well it actually works.

2 Responses

  1. Today you have learned that search-space culling is often the first step in algorithmic optimization.

    Now you know why I spent so much time working on group-level gross visibility culling in grad school. ;)

  2. The entire program’s all about culling the search space. It just turns out that the quick-and-dirty approach to applying constraints culls things to a far greater degree than I would’ve expected, more than offsetting needing to solve something like O(n^m) subproblems, and can be implemented as a quick single pass over the data.

    Now the question is whether other ways of constraining missings besides quick-and-dirty can be even better. I’m thinking not, and they’re more difficult to implement (read: it’s not working yet), but it’s worth a try.

Comments are closed.