Are you sure you want to delete this task? Once this task is deleted, it cannot be recovered.
6543 fdf750e4d4 | 4 years ago | |
---|---|---|
.. | ||
.gitignore | 5 years ago | |
LICENSE | 7 years ago | |
README.md | 5 years ago | |
go.mod | 4 years ago | |
treap.go | 7 years ago |
gtreap is an immutable treap implementation in the Go Language
gtreap implements an immutable treap data structure in golang.
By treap, this data structure is both a heap and a binary search tree.
By immutable, any updates/deletes to a treap will return a new treap
which can share internal nodes with the previous treap. All nodes in
this implementation are read-only after their creation. This allows
concurrent readers to operate safely with concurrent writers as
modifications only create new data structures and never modify
existing data structures. This is a simple approach to achieving MVCC
or multi-version concurrency control.
By heap, items in the treap follow the heap-priority property, where a
parent node will have higher priority than its left and right children
nodes.
By binary search tree, items are store lexigraphically, ordered by a
user-supplied Compare function.
To get a probabilistic O(lg N) tree height, you should use a random
priority number during the Upsert() operation.
MIT
import (
"math/rand"
"github.com/steveyen/gtreap"
)
func stringCompare(a, b interface{}) int {
return bytes.Compare([]byte(a.(string)), []byte(b.(string)))
}
t := gtreap.NewTreap(stringCompare)
t = t.Upsert("hi", rand.Int())
t = t.Upsert("hola", rand.Int())
t = t.Upsert("bye", rand.Int())
t = t.Upsert("adios", rand.Int())
hi = t.Get("hi")
bye = t.Get("bye")
// Some example Delete()'s...
t = t.Delete("bye")
nilValueHere = t.Get("bye")
t2 = t.Delete("hi")
nilValueHere2 = t2.Get("hi")
// Since we still hold onto treap t, we can still access "hi".
hiStillExistsInTreapT = t.Get("hi")
t.VisitAscend("cya", func(i Item) bool {
// This visitor callback will be invoked with every item
// from "cya" onwards. So: "hi", "hola".
// If we want to stop visiting, return false;
// otherwise a true return result means keep visiting items.
return true
})
The Upsert() method takes both an Item (an interface{}) and a heap
priority. Usually, that priority should be a random int
(math/rand.Int()) or perhaps even a hash of the item. However, if you
want to shuffle more commonly accessed items nearer to the top of the
treap for faster access, at the potential cost of not approaching a
probabilistic O(lg N) tree height, then you might tweak the priority.
For a simple, ordered, key-value storage or persistence library built
on immutable treaps, see: https://github.com/steveyen/gkvlite
本项目是群体化方法与技术的开源实现案例,在基于Gitea的基础上,进一步支持社交化的协同开发、协同学习、协同研究等群体创新实践服务,特别是针对新一代人工智能技术特点,重点支持项目管理、git代码管理、大数据集存储管理与智能计算平台接入。
Go SVG JavaScript Vue HTML other
Dear OpenI User
Thank you for your continuous support to the Openl Qizhi Community AI Collaboration Platform. In order to protect your usage rights and ensure network security, we updated the Openl Qizhi Community AI Collaboration Platform Usage Agreement in January 2024. The updated agreement specifies that users are prohibited from using intranet penetration tools. After you click "Agree and continue", you can continue to use our services. Thank you for your cooperation and understanding.
For more agreement content, please refer to the《Openl Qizhi Community AI Collaboration Platform Usage Agreement》