| Portability | non-portable |
|---|---|
| Stability | experimental |
| Maintainer | Edward Kmett <ekmett@gmail.com> |
| Safe Haskell | None |
Data.Vector.Map.Deamortized
Description
This module provides a Vector-based Map that is loosely based on the
Cache Oblivious Lookahead Array (COLA) by Bender et al. from
"Cache-Oblivious Streaming B-Trees",
but with inserts deamortized by using a varant of a technique from Overmars and van Leeuwen.
Currently this Map is implemented in an insert-only fashion. Deletions are left to future work
or to another derived structure in case they prove expensive.
Currently, we also do not use fractional cascading, as it affects the constant factors badly enough to not pay for itself at the scales we are interested in. The naive O(log^2 n) lookup consistently outperforms the alternative.
Compared to the venerable Data.Map, this data structure currently consumes more memory, but it
provides a more limited palette of operations with different asymptotics (~10x faster inserts at a million entries)
and enables us to utilize contiguous storage.
NB: when used with boxed data this structure may hold onto references to old versions of things for many updates to come until sufficient operations have happened to merge them out of the COLA.
- data Map k a
- empty :: Map k v
- null :: Map k v -> Bool
- singleton :: (Arrayed k, Arrayed v) => k -> v -> Map k v
- lookup :: (Ord k, Arrayed k, Arrayed v) => k -> Map k v -> Maybe v
- insert :: (Ord k, Arrayed k, Arrayed v) => k -> v -> Map k v -> Map k v
- fromList :: (Ord k, Arrayed k, Arrayed v) => [(k, v)] -> Map k v
Documentation
This Map is implemented as an insert-only Cache Oblivious Lookahead Array (COLA) with amortized complexity bounds that are equal to those of a B-Tree, except for an extra log factor slowdown on lookups due to the lack of fractional cascading. It uses a traditional Data.Map as a nursery.
singleton :: (Arrayed k, Arrayed v) => k -> v -> Map k vSource
O(1) Construct a Map from a single key/value pair.
lookup :: (Ord k, Arrayed k, Arrayed v) => k -> Map k v -> Maybe vSource
O(log^2 N) worst-case. Lookup an element.