Hacker News new | past | comments | ask | show | jobs | submit login

They're not using any fancy algorithms...except when they implement a customized version of Boyer-Moore for better string searching in a critical section of their algorithm. Not to mention all the fancy algorithms optimizing their brute-force code underneath their immediately visible program.

A better title would be, "How we determined when to use brute force."




Say what you will, but while Boyer-Moore can be tricky to implement, it's not exactly a fancy algorithm.


Exactly; "fancy" is relative. It's a bit tricky, but it's nothing like the complexity of maintaining and using a keyword index. The reference implementation given in the article we linked to is thirty-odd lines of code. What we're using in practice is somewhat larger, in part because Java is more verbose for this kind of thing, but still reasonable. (If there's interest, we'd be happy to post the code.)


Would love to look at your code...


I think the real point is that they did a bona-fide tradeoff analysis and found that for their use case one algorithm was better than another. It's not about how fancy the algorithm is, that's just how great engineering works. It's only surprising if you don't consider "brute force" to be just as valid a tool as any other.


Moreover, however fancy Boyer-Moore is, the data structure it is being applied to is incredible simple. There are no inverted indexes, B-trees, etc - just a string.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: