Comments (6)
glycerine
commented on September 27, 2024
1
For the sake of generating API ideas, consider how this works in a another red-black tree package. I can advance the iterator before deleting behind me:
package main
import (
"fmt"
"github.com/glycerine/rbtree"
)
type job struct {
endx int64
user string
jobid string
}
func newTree() *rbtree.Tree {
return rbtree.NewTree(
func(a1, b2 rbtree.Item) int {
a := a1.(*job)
b := b2.(*job)
if a.endx == b.endx {
switch {
case a.jobid == b.jobid:
return 0
case a.jobid < b.jobid:
return -1
case a.jobid > b.jobid:
return 1
}
}
return int(a.endx - b.endx)
})
}
func main() {
tree := newTree()
tree.Insert(&job{endx: 1, jobid: "hij"})
tree.Insert(&job{endx: 1, jobid: "abc"})
tree.Insert(&job{endx: 1, jobid: "def"})
tree.Insert(&job{endx: 2, jobid: "hij"})
tree.Insert(&job{endx: 2, jobid: "abc"})
tree.Insert(&job{endx: 2, jobid: "def"})
tree.Insert(&job{endx: 3, jobid: "hij"})
tree.Insert(&job{endx: 3, jobid: "abc"})
tree.Insert(&job{endx: 3, jobid: "def"})
show(tree)
// delete through the 2s
for it := tree.Min(); !it.Limit(); {
item := it.Item().(*job)
if item.endx <= 2 {
fmt.Printf("delete pass deletes %#v\n", item)
next := it.Next()
tree.DeleteWithIterator(it)
it = next
} else {
fmt.Printf("delete pass ignores %#v\n", item)
break // we can stop scanning now.
}
}
show(tree)
}
func show(tree *rbtree.Tree) {
fmt.Printf("showing tree: len = %v\n", tree.Len())
for it := tree.Min(); !it.Limit(); it = it.Next() {
item := it.Item().(*job)
fmt.Printf("%#v\n", item)
}
}
output:
showing tree: len = 9
&main.job{endx:1, user:"", jobid:"abc"}
&main.job{endx:1, user:"", jobid:"def"}
&main.job{endx:1, user:"", jobid:"hij"}
&main.job{endx:2, user:"", jobid:"abc"}
&main.job{endx:2, user:"", jobid:"def"}
&main.job{endx:2, user:"", jobid:"hij"}
&main.job{endx:3, user:"", jobid:"abc"}
&main.job{endx:3, user:"", jobid:"def"}
&main.job{endx:3, user:"", jobid:"hij"}
delete pass deletes &main.job{endx:1, user:"", jobid:"abc"}
delete pass deletes &main.job{endx:1, user:"", jobid:"def"}
delete pass deletes &main.job{endx:1, user:"", jobid:"hij"}
delete pass deletes &main.job{endx:2, user:"", jobid:"abc"}
delete pass deletes &main.job{endx:2, user:"", jobid:"def"}
delete pass deletes &main.job{endx:2, user:"", jobid:"hij"}
delete pass ignores &main.job{endx:3, user:"", jobid:"abc"}
showing tree: len = 3
&main.job{endx:3, user:"", jobid:"abc"}
&main.job{endx:3, user:"", jobid:"def"}
&main.job{endx:3, user:"", jobid:"hij"}
from btree.
gconnell
commented on September 27, 2024
Great question, and sorry I didn't see this sooner.
As you've found, currently our iterator functions aren't resilient to mutations during iteration. We might work on this later (and happy to accept pull requests ;), but to get things going right away, you could do this:
todelete := []btree.Item{}
tree.Ascend(..., func(x btree.Item) bool {
todelete = append(todelete, x)
return true
})
for _, x := range todelete {
tree.Delete(x)
}It's not as efficient as it could be, and it requires extra storage, but it also actually works right now :)
from btree.
glycerine
commented on September 27, 2024
For efficiency, the DeleteMin() method turned out to work well. This is isn't a general solution if you want to delete a range that starts in the middle of you elements, but it worked for the case above. As in the example above, where you want to delete all elements belong some time threshold, with a callback for each deletion, I'm doing:
func deleteThrough(t *btree, x int64, callme func(goner *mjob, through int64)) {
for {
min := t.Min()
if min == nil {
return
}
cur := min.(*mjob)
if cur.endx > x {
return
}
t.DeleteMin()
if callme != nil {
callme(cur, x)
}
}
}
At least I think (hope) this is efficient. If its not, please let me know! :-) Typically a tree will keep a pointer to its minimum element... but if its log(n) to find the smallest element, this might be a problem...
from btree.
glycerine
commented on September 27, 2024
Actually its worse than I expected.
https://github.com/google/btree/blob/master/btree.go#L153
makes it look like every delete is O(n) in the size of the tree n, as it does a full copy of the entire tree.
This is really, really, not what I would expect from a balanced binary tree implementation. Deleting the entire tree becomes an O(n*n) operation.
This is important. I'll make a separate issue.
from btree.
gconnell
commented on September 27, 2024
Nope, your original supposition was correct: it's O(logn) for a delete.
https://github.com/google/btree/blob/master/btree.go#L153 is the code called to delete an item from a single node, which is O(degree) of the btree (items will be max 'degree' in length, one itemset per node).
Your code is nicely efficient, but could be slightly moreso if you expect to delete more than 2 entries in your loop. In that case, you could blindly issue the delete, then put it back when you get to the one you care about.
var item btree.Item
for item = t.DeleteMin(); item.(*mjob).endx <= x {}
t.Insert(item)Calling Min, which is O(logn), then Delete, which is O(logn) effectively doubles your processing time, unless you expect to only delete zero or one element each time.
from btree.
cstockton
commented on September 27, 2024
I ran into having to clear the tree myself today, created #20 which if it's not accepted it's small enough to copy pasta if it will help you.
from btree.
Related Issues (20)
- Can it be done if I want to insert pair instead of int? HOT 1
- deleteMin appears to be O(n); not O(log(n)) as expected from a balanced binary tree. HOT 2
- Read traversal and COW HOT 1
- only one goroutine put and some other goroutines get , Is it safe ? HOT 1
- Tagged releases
- panic: runtime error: index out of range using Ascend iterator HOT 3
- Marshaling btree on disk
- Question on iteration HOT 8
- "t2" declared but "out" returned
- Bounds issue in insertAt HOT 3
- Go modules giving issues while importing kubernetes/cli-runtime
- Worked unexpected in go rountine? HOT 1
- What is the meaning of `copyOnWriteContext`? HOT 1
- Generic approach HOT 4
- should call Less() fewer times when iterating HOT 1
- BTree Iterators
- is it b-tree or b+tree? HOT 1
- is it b plus tree?? HOT 1
- stack overflow while deleting a key from the tree
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from btree.