Treeset background triggering

Allendar commented

2016-08-27 19:33:26 +00:00

(Migrated from github.com)

I have a small question concerning treesets. I'm applying it on bigger string-sets. Kind of like ORDER BY in SQL languages for my result-sets. I ran some Benchmarks with 5000 .Add(SomeStruct{123, "Name"}) per run, but I was wondering; how does the object do this logic in the background? Does every .Add() constantly trigger the sorting to happen or only if I read from the object? The performance degrades very fast with strings and I already have an older mechanic running in my API to do this kind of like this:

nameAsc := func(p1, p2 *SorterObject) bool {
    return p1.Value < p2.Value
}
nameDesc := func(p1, p2 *SorterObject) bool {
    return p1.Value > p2.Value
}

By(nameAsc).Sort(users)

This code-structure also suffers from exponential degradation.

I kind of wanted to see if the most optimal form of using treesets would be faster than the native Go solution I currently have running.

Any other tips (maybe another object would be better at this even) would be very much appreciated too! The idea of what I'm trying to achieve is that the Key keeps actively moving with the way the Name (string-value) is sorted.

Benchmarks for 10k and 100k .Add() per cycle:

1000  1920877 ns/op
100   19820013 ns/op

I have a small question concerning treesets. I'm applying it on bigger string-sets. Kind of like `ORDER BY` in SQL languages for my result-sets. I ran some Benchmarks with 5000 `.Add(SomeStruct{123, "Name"})` per run, but I was wondering; how does the object do this logic in the background? Does every `.Add()` constantly trigger the sorting to happen or only if I read from the object? The performance degrades very fast with strings and I already have an older mechanic running in my API to do this kind of like this: ``` nameAsc := func(p1, p2 *SorterObject) bool { return p1.Value < p2.Value } nameDesc := func(p1, p2 *SorterObject) bool { return p1.Value > p2.Value } By(nameAsc).Sort(users) ``` This code-structure also suffers from exponential degradation. I kind of wanted to see if the most optimal form of using treesets would be faster than the native Go solution I currently have running. Any other tips (maybe another object would be better at this even) would be very much appreciated too! The idea of what I'm trying to achieve is that the Key keeps actively moving with the way the Name (string-value) is sorted. Benchmarks for 10k and 100k `.Add()` per cycle: ``` 1000 1920877 ns/op 100 19820013 ns/op ```

Allendar commented

2016-08-27 20:00:53 +00:00

(Migrated from github.com)

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.

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.

emirpasic commented

2016-08-27 20:38:12 +00:00

(Migrated from github.com)

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.

This really depends on the use case, i.e. do you need your elements sorted after each insertion? A [red-black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_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: ![Big O](http://image.slidesharecdn.com/computability-tractableintractableandnon-computablefunction-140808040825-phpapp01/95/computability-tractable-intractable-and-noncomputable-function-9-638.jpg) > 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.

emirpasic commented

2016-09-07 00:59:03 +00:00

(Migrated from github.com)

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...

Definitely a bug and thank you for pointing it out: ``` go 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...

Allendar commented

2016-09-07 11:42:01 +00:00

(Migrated from github.com)

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?

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?

emirpasic commented

2016-09-07 13:22:10 +00:00

(Migrated from github.com)

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

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

Rows
Columns

Treeset background triggering #31