| Copyright | (c) Lambda Kazan 2016 |
|---|---|
| License | BSD3 |
| Maintainer | mz@lambdasoft.ru |
| Stability | experimental |
| Portability | POSIX |
| Safe Haskell | Safe |
| Language | Haskell2010 |
Data.OSTree
Description
Order Statistic Tree
This implementation uses weight-balanced trees which are desribed in
- Hirai, Yoichi, and Kazuhiko Yamamoto. "Balancing weight-balanced trees." Journal of Functional Programming 21.03 (2011): 287-307.
Also some of its code is based on containers package.
Implementation of order statistic tree is described in
- Cormen, T.H., Leiserson, Rivest, Stein. Introduction to algorithms. The MIT Press. 3rd ed.
Benchmarks
I tried to make this tree as fast as possible. I'm not bos, but results on my i7-4790 with 16Gb RAM are following:
- OSTree was created from 1.000.000 random numbers in 2.087 ± 0.021 s (e.g. for Data.Map.Strict - 1.977 ± 0.016 s);
- deletion from OSTree with 1.000.000 random numbers was made in 13.94 ± 0.93 ms;
- lookup from OSTree with 1.000.000 random numbers was made in 208.2 ± 3.48 ns;
- selection from OSTree with 1.000.000 random numbers was made in 92.72 ± 1.91 ns;
- full testing protocol can be found in result-bench.txt.
cabal configure --enable-tests --enable-benchmarks cabal bench
If someone knows how to improve these results or benchmarking itself, please don't hesitate to contact me
Synopsis
- data OSTree a
- empty :: OSTree a
- singleton :: a -> OSTree a
- size :: OSTree a -> Size
- insert :: Ord a => a -> OSTree a -> OSTree a
- lookup :: Ord a => a -> OSTree a -> Maybe a
- delete :: Ord a => a -> OSTree a -> OSTree a
- deleteFindMin :: OSTree a -> (a, OSTree a)
- deleteFindMax :: OSTree a -> (a, OSTree a)
- toList :: OSTree a -> [a]
- fromList :: Ord a => [a] -> OSTree a
- select :: OSTree a -> Int -> Maybe a
Documentation
Order statistic tree with elements of type a
Creating OSTree
Search Tree operations
delete :: Ord a => a -> OSTree a -> OSTree a Source #
O(log n). Delete first occurence of the element from the tree
deleteFindMin :: OSTree a -> (a, OSTree a) Source #
O(log n). Delete and find the minimal element.
deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")]) deleteFindMin Error: can not return the minimal element of an empty map
deleteFindMax :: OSTree a -> (a, OSTree a) Source #
O(log n). Delete and find the maximal element.
deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")]) deleteFindMax empty Error: can not return the maximal element of an empty map