Hackage :: [Package]

skip-list: An implementation of pure skip lists

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

Skip lists provide efficient amortized indexing deep into lists by building an index that, essentially, converts the list into a balance binary tree. See the wikipedia entry on skip lists for more information.

[Skip to Readme]

Modules

[Index]

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.1.0.0, 0.1.0.1
Change log CHANGES.md
Dependencies base (>=4.8 && <5) [details]
Tested with ghc ==7.10.3, ghc ==8.0.2, ghc ==8.2.1
License MIT
Copyright 2017 Gregory Malecha
Author Gregory Malecha
Maintainer gmalecha@gmail.com
Revised Revision 1 made by HerbertValerioRiedel at 2017-07-22T20:52:07Z
Category Data
Home page https://github.com/gmalecha/skip-list#readme
Source repo head: git clone https://github.com/gmalecha/skip-list
Uploaded by gmalecha at 2017-07-22T20:45:38Z
Distributions NixOS:0.1.0.1
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 1797 total (1 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2017-07-22 [all 1 reports]

Readme for skip-list-0.1.0.0

[back to package description]

skip-list

Build Status

Skip lists provide efficient amortized indexing deep into lists by building an index that, essentially, converts the list into a balance binary tree. See the wikipedia entry on skip lists for more information.

Performance

You can run the benchmarks using stack bench. The benchmark is the following:

let big = [0..1000] in
big == get (make big) <$> big
  • For lists (get = !! and make = id) 
benchmarking all/!!
time                 864.6 μs   (858.1 μs .. 873.0 μs)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 859.3 μs   (855.5 μs .. 864.3 μs)
std dev              14.76 μs   (11.86 μs .. 21.57 μs)
  • For SkipList (get = SL.lookup and make = SL.toSkipList 32) 
benchmarking Quantities/SkipList<32>
time                 134.9 μs   (134.0 μs .. 135.7 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 134.0 μs   (133.6 μs .. 134.5 μs)
std dev              1.559 μs   (1.317 μs .. 1.958 μs)