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

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
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-22T21:42:57Z
Distributions NixOS:0.1.0.1
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 1770 total (7 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.1

[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)