skew-list: Random access lists: skew binary
This package provides ordinary random access list, SkewList
implemented using skew binary approach.
It's worth comparing to ordinary lists, binary random access list (as in ral
package) and vectors (vector
package)
across two operations: indexing and consing.
Consing | Indexing | |
Ordinary list, [a] | O(1) | O(n) |
Binary list, RAList a | O(log n) | O(log n) |
Vector, Vector | O(n) | O(1) |
Sequence, Seq | O(1) | O(log n) |
Skew binary list, SkewList | O(1) | O(log n) |
SkewList
improves upon ordinary list, the cons operation is still
constant time (though with higher constant factor), but indexing
can be done in a logarithmic time.
Binary list cons is slower, as it might need to walk over whole log n sized structure.
Vector
is the other end of trade-off spectrum: indexing is constant time
operation, but consing a new element will need to copy whole spine.
Seq
from Data.Sequence has similar (but amortized) complexity bounds for
cons and index as SkewList
. However (it seems) that indexing is quicker for
SkewList
in practice. Also SkewList
has strict spine.
On the other hand, Seq
has quick append if you need that.
If you need both: fast consing and index, consider using SkewList
.
Modules
[Index] [Quick Jump]
Downloads
- skew-list-0.1.tar.gz [browse] (Cabal source package)
- Package description (revised from the package)
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
For package maintainers and hackage trustees
Candidates
- No Candidates
Versions [RSS] | 0.1 |
---|---|
Change log | ChangeLog.md |
Dependencies | base (>=4.12.0.0 && <4.21), deepseq (>=1.4.4.0 && <1.6), hashable (>=1.4.1.0 && <1.5), indexed-traversable (>=0.1.1 && <0.2), QuickCheck (>=2.14.2 && <2.16), strict (>=0.4.0.1 && <0.6) [details] |
Tested with | ghc ==8.6.5 || ==8.8.4 || ==8.10.7 || ==9.0.2 || ==9.2.8 || ==9.4.8 || ==9.6.5 || ==9.8.2 || ==9.10.1 |
License | BSD-3-Clause |
Copyright | (c) 2022 Oleg Grenrus |
Author | Oleg Grenrus <oleg.grenrus@iki.fi> |
Maintainer | Oleg.Grenrus <oleg.grenrus@iki.fi> |
Revised | Revision 3 made by phadej at 2024-06-15T13:27:26Z |
Category | Data |
Home page | https://github.com/phadej/skew-list |
Bug tracker | https://github.com/phadej/skew-list/issues |
Source repo | head: git clone https://github.com/phadej/skew-list.git |
Uploaded | by phadej at 2023-01-03T14:58:07Z |
Distributions | NixOS:0.1 |
Reverse Dependencies | 1 direct, 0 indirect [details] |
Downloads | 125 total (15 in the last 30 days) |
Rating | (no votes yet) [estimated by Bayesian average] |
Your Rating | |
Status | Docs available [build log] Last success reported on 2023-01-03 [all 1 reports] |