6 ms·
I wrote something like this for contact auto completion - running in the browser we had to ensure that both tree construction was fast, and also that completion
by cirwin 3y ago
I wrote something like this for contact auto completion - running in the browser we had to ensure that both tree construction was fast, and also that completion was instantaneous. So the next level of optimization is to amortize tree construction over searches (using the observation that most of the tree is never accessed)
https://github.com/superhuman/trie-ing https://github.com/superhuman/trie-ing
- leeoniya 3y agointeresting. i made something much more stupid, but brutally effective: https://github.com/leeoniya/uFuzzy https://github.com/leeoniya/uFuzzy i guess if you wanted results ordered by contact frequency you can just keep the original haystack sorted by frequency, and would get the Richard match first. or keep the frequency in an adjacent lookup and sort/pick the result afterwards. PSA: don't use the ultra popular Fuse.js for fuzzy matching, it's super slow and has pretty terrible match quality. e.g. https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uFuzzy,fuzzysort,QuickScore,Fuse&search=super%20ma https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...
- rockwotj 3y agoIf youre interested in a TypeScript fork of this that also supports deletion, see here: https://github.com/shortwave/trie https://github.com/shortwave/trie There are also a couple of bug fixes in there, for example: https://github.com/shortwave/trie/commit/1e7045d89cc200112517a3aa82ecfbcaf2c3b210 https://github.com/shortwave/trie/commit/1e7045d89cc20011251...