Hacker News Reader

I was curious how they implemented prefix matching, so I went and looked at the code [1]. Unfortunately, this is just a simple linear scan that calls .startswith(). It is possible to do fast (log N) prefix matching with radix / critbit trees.

[1] https://github.com/Greplin/greplin-lucene-utils/blob/master/...

View on HN

Radix trees are O(k), where k is the length of the query string.

Anyway, for prefix matching, you want to take careful note of the size and shape of your data, because it matters for which algorithm is fastest. If your data all fits in RAM (or better yet, all fits in L2 cache), then I've had very good results with binary search (O(log N)) to find the first matching result, and then linear scan to find all possible suffixes. This is a lot more cache-friendly than radix trees, which have better theoretical performance but often touch memory that's all over the place.

> Radix trees are O(k)

Yes, thank you.

Reply on news.ycombinator.com