3 ms·

Interesting that this is fast! I looked at the code and it looks like a super vanilla (prefix) trie, at least for exact match searching. For approximate searchi

Interesting that this is fast! I looked at the code and it looks like a super vanilla (prefix) trie, at least for exact match searching. For approximate searching, it seems to just explore the trie from the endpoint of the word in the query; it I understand correctly, if wouldn't find "banana" given the query "baana" and some tolerance. The readme says that the trie has some tricks to make it fast; the only such trick that I could find is "fast properties", which seems to be a JS-specific thing to make object property access faster (something with promoting an ad-hoc object to a prototype, which presumably enjoys more optimisation in JS engines). Hence I'm sort-of surprised that this performs well! If a simple trie is sufficient for that, I might go forward with implementing search for some of my other stuff just like that.

nine_k 4y ago
Modern computers are ridiculously fast. V8 JIT compiler can produce pretty fast native code for hot paths. Thus all together allows JS perform surprisingly well in the vanilla case, even using simple algorithms. I wonder how much faster could one make the lookup by e.g. using a typed array to represent the trie and the index; that would be cache-friendly.
- tomsmeding 4y ago
  I'm less surprised about the fact that JS can be fast, and more that a vanilla trie can be fast and (hopefully) resource-efficient; I had the impression that any scalable index would need to compact the trie in some manner (i.e. combining multiple characters in one node) or do other algorithmic improvements that I don't know about. (That's why I looked at the code, to find those -- but I didn't really find any)
  - micheleriva 4y ago
    The current release of Lyra is treating the trie structure as a tree (of course), but we're planning to start approaching it as a graph for the exact reason you're mentioning. We don't have performance comparisons yet, but we'll document everything

nine_k 4y ago

Modern computers are ridiculously fast. V8 JIT compiler can produce pretty fast native code for hot paths. Thus all together allows JS perform surprisingly well in the vanilla case, even using simple algorithms. I wonder how much faster could one make the lookup by e.g. using a typed array to represent the trie and the index; that would be cache-friendly.

tomsmeding 4y ago
I'm less surprised about the fact that JS can be fast, and more that a vanilla trie can be fast and (hopefully) resource-efficient; I had the impression that any scalable index would need to compact the trie in some manner (i.e. combining multiple characters in one node) or do other algorithmic improvements that I don't know about. (That's why I looked at the code, to find those -- but I didn't really find any)
- micheleriva 4y ago
  The current release of Lyra is treating the trie structure as a tree (of course), but we're planning to start approaching it as a graph for the exact reason you're mentioning. We don't have performance comparisons yet, but we'll document everything