treap alternatives and similar packages
Based on the "Data Structures" category.
Alternatively, view treap alternatives based on common mentions on social networks and blogs.
-
gods
GoDS (Go Data Structures) - Sets, Lists, Stacks, Maps, Trees, Queues, and much more -
go-datastructures
A collection of useful, performant, and threadsafe Go datastructures. -
golang-set
A simple generic set type for the Go language. Trusted by Docker, 1Password, Ethereum and Hashicorp. -
-
-
-
-
gocache
☔️ A complete Go cache library that brings you multiple ways of managing your caches -
boomfilters
Probabilistic data structures for processing continuous, unbounded streams. -
-
hyperloglog
HyperLogLog with lots of sugar (Sparse, LogLog-Beta bias correction and TailCut space reduction) -
gostl
Data structure and algorithm library for go, designed to provide functions similar to C++ STL -
trie
Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching. -
go-geoindex
Go native library for fast point tracking and K-Nearest queries -
ttlcache
An in-memory cache with item expiration and generics [Moved to: https://github.com/jellydator/ttlcache] -
-
hilbert
Go package for mapping values to and from space-filling curves, such as Hilbert and Peano curves. -
Bloomfilter
Face-meltingly fast, thread-safe, marshalable, unionable, probability- and optimal-size-calculating Bloom filter in go -
go-adaptive-radix-tree
Adaptive Radix Trees implemented in Go -
cuckoo-filter
Cuckoo Filter go implement, better than Bloom Filter, configurable and space optimized 布谷鸟过滤器的Go实现，优于布隆过滤器，可以定制化过滤器参数，并进行了空间优化 -
goconcurrentqueue
Go concurrent-safe, goroutine-safe, thread-safe queue -
-
-
-
ring
Package ring provides a high performance and thread safe Go implementation of a bloom filter. -
-
go-rquad
:pushpin: State of the art point location and neighbour finding algorithms for region quadtrees, in Go -
set
A simple Set data structure implementation in Go (Golang) using LinkedHashMap. -
goset
Set is a useful collection but there is no built-in implementation in Go lang. -
nan
Zero allocation Nullable structures in one library with handy conversion functions, marshallers and unmarshallers -
-
Truly a developer’s best friend
Do you think we are missing an alternative of treap or a related project?
|
Clean code begins in your IDE with SonarLint
sponsored
www.sonarlint.org
|
Popular Comparisons
|
Delete the most useless function ever: context switching.
sponsored
www.zigi.ai
|
README
treap
Package treap implements an immutabe sorted set datastructure using a combination tree/heap or treap.
The algorithms are mostly based on Fast Set Operations Using Treaps
Although the package is oriented towards ordered sets, it is simple to convert it to work as a persistent map. There is a working example showing how to do this.
Benchmark stats
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 immutable map (using 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 map is about 30% faster but this is still respectable showing for treaps.
$ go test --bench=. -benchmem
goos: darwin
goarch: amd64
pkg: github.com/perdata/treap
BenchmarkInsert-4 1000000 2347 ns/op 1719 B/op 36 allocs/op
BenchmarkInsertRegularMap-4 2000 890745 ns/op 336311 B/op 8 allocs/op
BenchmarkIntersection-4 500 3125772 ns/op 1719838 B/op 35836 allocs/op
BenchmarkIntersectionRegularMap-4 500 2436519 ns/op 718142 B/op 123 allocs/op
BenchmarkUnion-4 1000 1451047 ns/op 939846 B/op 19580 allocs/op
BenchmarkDiff-4 500 3280823 ns/op 1742080 B/op 36298 allocs/op
PASS