order-statistic-tree
Version 0.1.1.0 revision 0 uploaded by MZiatdinov.
Package meta
- Synopsis
- Order statistic trees based on weight-balanced trees
- Description
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.
Benchmarks
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.
- Author
- Mansur Ziiatdinov
- Bug reports
- n/a
- Category
- Data
- Copyright
- Lambda Kazan, 2016
- Homepage
- n/a
- Maintainer
- mz@lambdasoft.ru
- Package URL
- n/a
- Stability
- n/a