The order-statistic-tree package
This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.
This repository contains an implementation of order statistic tree in Haskell programming language. I could not find an order statistic tree at Hackage, so I have to develop one.
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 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.
I tried to make this tree as fast as possible. The 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.
|Versions||0.1.0.0, 0.1.0.0, 0.1.0.1, 0.1.1.0|
|Change log||None available|
|Dependencies||base (==4.8.*) [details]|
|Copyright||Lambda Kazan, 2016|
|Source repository||head: git clone https://github.com/lambdakazan/ostree.git|
|Uploaded||Mon Feb 29 13:20:55 UTC 2016 by MZiatdinov|
- order-statistic-tree-0.1.0.0.tar.gz [browse] (Cabal source package)
- Package description (included in the package)
For package maintainers and hackage trustees