Dictionary Lookups in JavaScript | Hacker News Reader

Dictionary Lookups in JavaScript

ejohn.org

70 pointsstanleydrew19 comments

Great explanation and practical sample of javascript features + HTML5's local storage.

The only thing missing was converting the dictionary data into a trie. ;-)

Thanks for the Trie suggestion! I’ll do a follow-up post and talk about that specifically. Note that this post was mostly written to get people thinking about practical forms of optimization (that hopefully transcend dictionaries themselves – which only have limited applications in JavaScript applications). I’ll definitely do another post digging deeper into dictionary lookups themselves. Thanks!

I didn't expect you to do that and was joking (hence the wink) but it would be amazing to see it AT work. If you had added the Trie in this post, it would have probably been over the average human threshold of patience and understanding.

While a Trie is the "correct" datastructure with appropriate storage techniques, you have to be careful when your hands are tied regarding what datastructure you build it on top of.

When I benchmarked a Trie implementation using dicts of dicts in Python, and I found that the memory usage was an order of magnitude higher than just having a set or list of strings (2mb vs ~100kb), while the performance difference was negligible. I ended up going with a set.

The issue is that each layer per node has 26+ instances of your core object struct (whether it's a list or a dict), so any overhead gets ballooned really fast.

You can get around that by using an array, and having functions to get and set parts of the array.

That stops the object overhead in python from killing memory.

But it's not the prettiest way to do things.

The only thing missing was converting the dictionary data into a trie. ;-)

That's what I was thinking. I wonder what the memory and download footprint for that would be in practice. Considering characters are represented by string objects in JavaScript, it could get expensive, unless the runtime interns short strings. If not, you could represent single letters with integers, which are almost certainly interned or even use a non-pointer representation. All those objects at each tree level might be a bit much though.

In this situation, I'd seriously consider throwing down a binary blob as a string that directly represents this data as whatever fancy structure you want and writing the small handful of functions it would take to traverse that "string" to do the lookup. Then you can do whatever optimal thing you want and memory usage is very predictable.

Technically this is what his final solution converged on, it's just the least fancy "fancy structure" there is.

It's a last resort, certainly, but in certain cases it's the simplest answer. Be aware of encoding issues, though; UTF-8 technically can't carry arbitrary binaries and you may have to work around some things a bit.

I'd recommend sending base64'd data down. Use this to encode/decode from javascript strings of 1-byte-per-character data:

https://github.com/mcarter/js.io/blob/master/packages/std/ba...

FYI, many browsers offer (native) 'atob()' and 'btoa()' functions for Base64 encode/decode that will outperform that JS code.

For what it's worth, the linked code on github appears to be specific to node.js. Last I checked, there was no native function to convert strings to and from base64, only buffers.

If you're writing this for client side, it would indeed be preferable to use the native functions.

Less than a naive dictionary; it's a very compact and natural representation of ordered lists of unique words.

I realise that, I'm interested in the per-object overhead. This approaches zero for the single giant string.

Take a look at Saurabh Odhyan's JavaScript prefix trie implementation; https://github.com/odhyan/trie

I would have probably stored all the words as keys in a Redis DB, and then never would have discovered the neat ideas he did about having the dictionary client-side.

That's funny because I got something very similar as a job interview question the other day, and my first response was basically, "Put it in Redis. Next question."

Yeah... I didn't get that job.

Instead of shoving the whole dictionary onto the client side (as clever as that is), he could also look up all the anagrams & subanagrams given a set of letters and then match against that subset of words.

Check out http://stackoverflow.com/questions/396005/word-anagram-hashi... for an example

Very interesting. The is a good solution for lots of things

Jresig needs to take a data structures 101 course.

Elaborate?

Reply on news.ycombinator.com