order-statistic-tree

Order statistic trees based on weight-balanced trees

Latest on Hackage:0.1.1.0

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.

BSD3 licensed by Mansur Ziiatdinov
Maintained by mz@lambdasoft.ru

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.

Depends on:
comments powered byDisqus