skip-list: An implementation of pure skip lists

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]

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]

Properties

Versions 0.1.0.0, 0.1.0.0, 0.1.0.1
Change log CHANGES.md
Dependencies base (>=4.7 && <5) [details]
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-22T20:45:08Z

Modules

[Index]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


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