Data.OSTree

Contents

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

Order statistic tree with elements of type a

Instances

Returns an empty tree

Returns a tree with single element

Returns size of the tree

insert :: Ord a => a -> OSTree a -> OSTree a Source

Insert the element into the tree

lookup :: Ord a => a -> OSTree a -> Maybe a Source

Lookup the element in the tree

delete :: Ord a => a -> OSTree a -> OSTree a Source

Delete first occurence of the element from the tree

Return list of elements of the tree

fromList :: Ord a => [a] -> OSTree a Source

Convert list of elements to the tree

Arguments

:: OSTree a	tree
-> Int	index `i`, starting from 1
-> Maybe a	if there are at least `i` elements, returns i-th least element

Returns i-th least element of the tree