Hackage :: [Package]

order-statistic-tree: Order statistic trees based on weight-balanced trees

[ bsd3, data, library ] [ Propose Tags ] [ Report a vulnerability ]

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]

Modules

[Index]

Downloads

Maintainer's Corner

Package maintainers

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 2787 total (21 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]

Readme for order-statistic-tree-0.1.1.1

[back to package description]

Order Statistic Tree

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 as 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 code from containers package.

Implementation of order statistic tree is described in

  • Cormen, T.H., Leiserson, Rivest, Stein. Introduction to algorithms. The MIT Press. 3rd ed.

Installation

This package will be deployed to hackage, so you can install it using cabal:

cabal install order-statistic-tree

Building

cabal configure
cabal build

Testing

cabal configure --enable-tests --enable-benchmarks
cabal test

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