order-statistic-tree: Order statistic trees based on weight-balanced trees
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 1.987 ± 0.015 s (e.g. for Data.Map.Strict - 2.081 ± 0.008 s);
deletion from OSTree with 1.000.000 random numbers was made in 13.88 ± 0.14 ms;
lookup from OSTree with 1.000.000 random numbers was made in 164.8 ± 1.06 ns;
selection from OSTree with 1.000.000 random numbers was made in 56.54 ± 0.99 ns;
full testing protocol can be found in result-bench.txt.
[Skip to Readme]
Downloads
- order-statistic-tree-0.1.1.1.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
Versions [RSS] | 0.1.0.0, 0.1.0.1, 0.1.1.0, 0.1.1.1 |
---|---|
Change log | CHANGELOG.md |
Dependencies | base (>=4.8 && <5) [details] |
License | BSD-3-Clause |
Copyright | Lambda Kazan, 2016 |
Author | Mansur Ziiatdinov |
Maintainer | mz@lambdasoft.ru |
Category | Data |
Source repo | head: git clone https://github.com/lambdakazan/ostree.git |
Uploaded | by MZiatdinov at 2018-11-02T07:20:19Z |
Distributions | NixOS:0.1.1.1 |
Reverse Dependencies | 1 direct, 0 indirect [details] |
Downloads | 2754 total (6 in the last 30 days) |
Rating | (no votes yet) [estimated by Bayesian average] |
Your Rating | |
Status | Docs uploaded by user Build status unknown [no reports yet] |