GitHub - Leeheng86/radix_tree: Naive implementation of Radix Tree for Ruby

Leeheng86 / radix_tree Public

forked from nahi/radix_tree

Notifications You must be signed in to change notification settings
Fork 0
Star 0

Naive implementation of Radix Tree for Ruby

Notifications

Name		Name	Last commit message	Last commit date
Latest commit History 39 Commits
bench		bench
lib		lib
test		test
.gitignore		.gitignore
.travis.yml		.travis.yml
Gemfile		Gemfile
README		README
Rakefile		Rakefile
radix_tree.gemspec		radix_tree.gemspec

Repository files navigation

radix_tree - Naive implementation of Radix Tree for Ruby
Copyright (C) 2012 Hiroshi Nakamura <[email protected]>

My intention is using Radix Tree instead of Hash for parsing external input
to avoid DoS via Algorithmic Complexity Attacks.


== Performance

* 20 times slower for 10 bytes key, 100000 elements insertion
* 10 times slower for 10 bytes key, 100000 elements retrieval


== TODO

See comments in lib/radix_tree.rb


== History

 * 1.0.0 - Initial release.
 * 1.1.0 - 1.8 support, speed/memory perf improvement.


== Author

Name:: Hiroshi Nakamura
E-mail:: [email protected]
Project web site:: http://github.com/nahi/radix_tree


== License

This program is copyrighted free software by Hiroshi Nakamura.  You can
redistribute it and/or modify it under the same terms of Ruby's license;
either the dual license version in 2003, or any later version.