Question

Which is the fastest way to search in a translation dictionary?

In my opinion, the first thing you should know is - what kind of structure (array etc) you should use. The second thing is which algorithm is the best choice to use for that structure.

My guess is that it would be some kind of self-balancing tree. I think that tree is a structure and also it is a search algorithm in one. Am I right? Your opinion?

Thank you!

EDIT: It is a bilingual dictionary. It holds about milion records. One machine.

Was it helpful?

Solution

So your data structure must store pairs of words (in 2 different languages), and you will use words from one language as lookup keys?

Do you need to do more than a million lookups a second? If not, don't worry about what structure is fastest. Just use whatever standard hash table structure is available in your language.

If you're not convinced: I just did a little experiment in Ruby, using a hash table with 1,000,000 entries. On my PC, I can do 1000 lookups in that table in about 1 millisecond.

IF YOU DO need more than 1,000,000 lookups a second: try a search trie.

And remember that since your structure is completely static and unchanging, this task is 100% parallelizable across multiple CPU cores.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top