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

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.

[maintain] [Publish]

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]

Properties

Versions	0.1.0.0, 0.1.0.1, 0.1.1.0, 0.1.1.1, 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:16:44Z

Modules

[Index]

Data
- Data.OSTree

Downloads

order-statistic-tree-0.1.1.1.tar.gz [browse] (Cabal source package)
Package description (as included in the package)

Maintainer's Corner

Package maintainers

MZiatdinov

For package maintainers and hackage trustees

edit package information

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