Treeset background triggering about gods HOT 5 CLOSED

I also noticed that the treeset method removes all Names that already occurred and only keeps the first match. Is that intended?

So if I have:

set := treeset.NewWith(byName)

set.Add(User{1, "James"})
set.Add(User{9, "Kyle"})
set.Add(User{5, "James"})

James (5) fully disappears.

from gods.

This really depends on the use case, i.e. do you need your elements sorted after each insertion?

A red-black tree is used in the background of a treeset to keep elements sorted upon insertion and deletion, i.e. it finds the node in the tree into which to insert the element with O(log n) complexity. This is generally the efficient way in terms of performance and memory allocations, since it only searches for the right position and inserts, rather than the above implementation of Go's merge-sorting the whole collection with O(n log n) complexity, which will degrade performance as the number of elements grows as you've stated. This point is valid if you perform the sort in your mechanic on each insertion. In that case it would be better to use gods' treeset.

On another note, if you don't need to perform the sort on each insertion, then I think it would be more efficient to insert all elements and sort them as you've done in your code using the native way. However I suppose that's not what you need?

Compare below the behavior of treeset (orange) with Go's native sort after each insertion (red) with respect to the number of elements:

I also noticed that the treeset method removes all Names that already occurred and only keeps the first match. Is that intended?

That was not intended, the new value should replace the old, i.e. James(1) should have disappeared. If that's not the case, then that is a bug and should be fixed. Let me investigate and I'll come back to you.

from gods.

Definitely a bug and thank you for pointing it out:

package main

import (
    "fmt"
    "github.com/emirpasic/gods/sets/treeset"
    "github.com/emirpasic/gods/utils"
)

type User struct {
    Id   int
    Name string
}

func byName(a, b interface{}) int {
    return utils.StringComparator(a.(User).Name, b.(User).Name)
}

func main() {
    set := treeset.NewWith(byName)

    set.Add(User{1, "James"})
    set.Add(User{9, "Kyle"})
    set.Add(User{5, "James"})

    fmt.Println(set) // Output: {1 James}, {9 Kyle}
}

Working on a fix...

from gods.

Glad to help. Sorry for my late response.

On the matter of performance; would there be a way to feed the Treeset the whole list once and only make it sort once? Iterating and making it refresh intersections each time sounds a bit painfully redundant in the case of bigger pre-defined data-sets over feeding the Treeset continuous data.

Simplistically put, something like:

set := treeset.NewWith(byName)
set.DisableAutoSorting()

set.Add(User{1, "James"})
set.Add(User{9, "Kyle"})
set.Add(User{5, "James"})

set.EnableAutoSorting()
// OR
set.EnableAutoSortingAndDoSort() // To force it to run sorting explicitly too

Does that make sense and would that be achievable?

from gods.

That does make absolute sense, but I will need to first implement that bulk insert into red-black tree, since the treeset uses the red-black tree in the background. As a matter of fact I have started working on some of those already:

• For BinaryHeap tree #35 already implemented
• For other structures #36 standing issue to be implemented

from gods.