Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
JavaScript Ruby
Branch: master

Fetching latest commit…

Cannot retrieve the latest commit at this time

Failed to load latest commit information.
alt_trie
app
data
lib
.gitignore
MIT_LICENSE.txt
README.md
array_find_dictionary.rb
array_select_dictionary.rb
dictionary.rb
dictionary_spec.rb
mem_test.rb
memory.rb
names.rb
non_trie_dictionary.rb
perf_test.rb
set_dictionary.rb
trie.gemspec
trie.rb
trie_dictionary.rb
trie_sym_dictionary.rb

README.md

Trie Example

This is a dictionary implemented as a trie, inspired by Tyler McMullen's LA RubyConf 2010 talk: http://www.scribd.com/doc/27149829/Alternative-Data-Structures-in-Ruby

There are also naive implementations using Array and Set that are fun for comparing performance and memory footprint.

How to use it:

>> require 'trie_dictionary'
=> true
>> d = Dictionary.new
=> #
>> d.add ("fish")
(irb):7: warning: don't put space before argument parentheses
=> true
>> d.add("fiend")
=> true
>> d.add("foo")
=> true
>> d.find('f')
=> ["fish", "fiend", "foo"]
>> d.find('fi')
=> ["fish", "fiend"]
>> d.find('fo')
=> ["foo"]

Alternate implementation Performance results:

Something went wrong with that request. Please try again.