3 ms·
Your linked blog post was a really good read, but I'm not totally sure if the correct takeaway was that brute force outperforms "clever" algorithms. Unless I mi
by mattb314 10y ago
Your linked blog post was a really good read, but I'm not totally sure if the correct takeaway was that brute force outperforms "clever" algorithms. Unless I misinterpreted the results, FLANN and Annoy (which implement hierarchical k-means and a binary space partitioning algorithm, respectively) both ran about 100x faster than brute force.
Were you referring to the number of libraries the author couldn't get to work? This certainly might be a failure of over complicated algos, but it seemed more like an engineering failure than a performance failure to me.
- Radim 10y agoWell, complex algos and engineering failures go hand in hand :-) The approximative kNNs are superior if done well, no doubt about that. It's just that "doing them well" is a major challenge, even for well-established and well thought out tools, such as scikit-learn. So many things can go wrong, and despite the increased complexity & settling for approximative results, you can end up with worse runtime performance than O(n) brute force... The performance of brute force is pleasantly predictable and stable. I just found the parallels with OP's article (which is on fulltext search, a mostly unrelated field) interesting, that's all.