Sunday, May 4, 2014

Golang Trie implementation

Sunday, May 04, 2014 Posted by Andre Broers 9 comments
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.

9 comments:

  1. Fine information, many thanks to the author. 123helpme
    It is puzzling to me now, but in general, the usefulness and importance is overwhelming. Very much thanks again and best of luck!

    ReplyDelete
  2. I enjoyed over read your blog post. Your blog have nice information, I got good ideas from this amazing blog. I am always searching like this type blog post. I hope I will see again..
    starfall | barney | abcya

    ReplyDelete
  3. * Jual Obat Aborsi,,
    * Obat Aborsi,,
    * Obat Penggugur Kandungan,,
    * what I have read on this page is enough to make me satisfied can menik die this article thanks greetings *
    * Harga Obat Aborsi,,

    ReplyDelete