TernaryTrees: Efficient pure ternary tree Sets and Maps
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:
(Exported the Internal modules because apparently you need to)
Moved datatype definitions into .Internal modules so that testing can be performed, without needing to export their definitions in the main modules.
Checked a lot of the source with HLint 1.6 and made some minor changes based on that ((mostly redundant brackets)).
© 2009 by Alex Mason (http://random.axman6.com/blog/). BSD3 license.
|Versions [RSS] [faq]||0.0.1, 0.0.2, 0.0.2.1, 0.0.2.2, 0.0.3.0, 0.0.4.0, 0.1.0.0, 0.1.1.0, 0.1.1.1, 0.1.2.0, 0.1.3.0, 0.1.3.1, 0.1.3.2, 0.1.3.3, 0.1.3.4, 0.2.0.0, 0.2.0.2|
|Dependencies||base (>=18.104.22.168 && <22.214.171.124), binary (>=0.4.4) [details]|
|Maintainer||Alex Mason (irc: Axman6) <email@example.com>|
|Uploaded||by AlexMason at 2009-07-12T02:18:43Z|
|Downloads||13039 total (76 in the last 30 days)|
|Rating||(no votes yet) [estimated by Bayesian average]|
Docs not available [build log]
Last success reported on 2016-12-31 [all 9 reports]