Sunday, May 4, 2014

Golang Trie implementation

Sunday, May 04, 2014 Posted by Andre Broers
For a webcrawler I needed a low memory solution to keep track of the already crawled web urls. Because this list grows fast I choose a Trie (wiki) implementation. I just started playing with the Golang language so my implementation will be in this language.
The first thing I tried was an implementation based on maps. But it turned out the creation of maps is very memory intensive. My test of one million records failed on an out of memory error.
The code of my first attempt:

I implemented the functions again using a slice. Which turns out to be way faster and consuming less memory. It runs the tests in less than 3 seconds on a basic Microsoft Azure Ubuntu extra small instance.

I published this as a golang module to github at :
https://github.com/broersa/trie

Feel free to use it.