TernaryTrees
Version 0.1.0.0 revision 0 uploaded by AlexMason.
Package meta
- Synopsis
- Efficient pure ternary tree Sets and Maps
- Description
Ternary trees are an efficient structure often used for storing strings for fast lookups. This package implements a generic tree for storing lists of Ord instances, and a specialised String implementation which is about 30% faster than the generic version.
An example program is provided what shows how to use the package as a dictionary program for spell checking, and how it can be used to serialise data with Don Stewart's Data.Binary package.
From my testing, using the /usr/share/dict/words file on my system (over 230,000 words), inserting all words, checking they all exist in the tree, writing them to a binary file, reading them back in and checking the read in result is the same as the original takes slightly over 3 seconds using the StringSet. The written file is also slightly smaller than the input (by over 40% in some cases).
New in this version:
First major interface change since the first release... (less than 24 hours ago).
Changed many function names to match those in Data.[Map,Set] to provide a more familiar interface.
Added a Functor instance for TernaryMap.
Added empty and null functions to all types, and elems to TernaryMap.
© 2009 by Alex Mason (http://axman6.homeip.net/blog/). BSD3 license.
- Author
- Alex Mason
- Bug reports
- n/a
- Category
- Data Structures
- Copyright
- n/a
- Homepage
- n/a
- Maintainer
- Alex Mason (irc: Axman6) <axman6@gmail.com>
- Package URL
- n/a
- Stability
- n/a