Ecosyste.ms: Packages
An open API service providing package, version and dependency metadata of many open source software ecosystems and registries.
proxy.golang.org : github.com/perdata/treap
Package treap implements a persistent treap (tree/heap combination). https://en.wikipedia.org/wiki/Treap A treap is a binary search tree for storing ordered distinct values (duplicates not allowed). In addition, each node actually a random priority field which is stored in heap order (i.e. all children have lower priority than the parent) This provides the basis for efficient immutable ordered Set operations. See the ordered map example for how this can be used as an ordered map Much of this is based on "Fast Set Operations Using Treaps" by Guy E Blelloch and Margaret Reid-Miller: https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf The most interesting benchmark is the performance of insert where a single random key is inserted into a 5k sized map. As the example shows, the treap structure does well here as opposed to a regular persistent map (which involves full copying). This benchmark does not take into account the fact that the regular maps are not sorted unlike treaps. The intersection benchmark compares the case where two 10k sets with 5k in common being interesected. The regular persistent array is about 30% faster but this is still respectable showing for treaps.
Registry
-
Source
- Documentation
- JSON
purl: pkg:golang/github.com/perdata/treap
Keywords: golang, heap, immutable, map, persistent, set, treap, tree
License: MIT
Latest release: over 4 years ago
First release: over 4 years ago
Namespace: github.com/perdata
Stars: 21 on GitHub
Forks: 6 on GitHub
See more repository details: repos.ecosyste.ms
Last synced: 30 days ago