search

twitter / typeahead.js

typeahead.js is a fast and fully-featured autocomplete library
http://twitter.github.io/typeahead.js/
MIT License
16.52k stars 3.21k forks source link

Local Storage Optimization #841

Open marcguyer opened 10 years ago

marcguyer commented 10 years ago

I've noticed that the data inserted in local storage is almost 6x the size of the original data set. For a 50k data set, the local storage data is 291k in my tests. This could be quickly reduced by changing the "children" key to something smaller as others have suggested for optimizing the post-processed data. Further, I don't presume to understand how the "trie" is built/used/etc, but on the surface it appears to contain some redundancy that could be avoided.

Perhaps I could take a look at improving this myself with just a bit of guidance based on your institutional knowledge.

jharding commented 10 years ago

Related to #845. The reason it's so large is because when the prefetch data is loaded, it's processed into a trie for quick lookups. It's debatable whether this is necessary.

browles commented 9 years ago

The current trie implementation gives very quick lookups at a unnecessarily large cost to memory. One problem is that ids are pushed to the .ids array of every node corresponding to the letters of the token; this could be changed to store the ids only at the node of the terminal token letter. Autocomplete matching could be then changed to: traverse down the trie via the letters of the input partial word, and retrieve all ids below that node. This would slow lookups slightly, but each id would only be stored once instead of at numerous nodes.

We could furthermore make the .ids property undefined until there were an id to push, giving marginal savings on space. Additionally the .children property ought to be renamed to a one or two character name, .ch or something.

If that sounds alright, I'm going to start working on this.