FAQ
I re-implemented (partially) Left-leaning Red-Black Trees today.

The performance is quite nice, it's 323 ns/op for my attempt, while petar's
GoLLRB package gets 1794 ns/op. Thus, it runs factor 5 faster than GoLLRB.

My own needs are a bit limited, I only need Search and Insert, so I haven't
implemented the other operations, yet, besides Length.

In fairness, https://github.com/petar/GoLLRB has the much nicer interface.
It resembles container/list, whereas my attempt is modeled after sort. The
difference is … boilerplate. Here's what you have to do to use Niko's
Sorted Set:

type intNode struct {
val int
left, right *intNode
color Color
}
// -1, if z < nd, 0 if z == nd, 1 if z > nd.
func (z intNode) Cmp(nd Node) int {
v := nd.(*intNode).val
if z.val < v {
return -1
} else if z.val == v {
return 0
} else {
return 1
}
}
func (z intNode) Left() (nd Node, ok bool) { return z.left, z.left != nil}
func (z intNode) Right() (nd Node, ok bool) { return z.right, z.right !=
nil }
func (z *intNode) SetLeft(nd Node) { (*z).left = nd.(*intNode) }
func (z *intNode) SetRight(nd Node) { (*z).right = nd.(*intNode) }
func (z intNode) Color() Color { return z.color }
func (z *intNode) SetColor(cl Color) { (*z).color = cl }
func (z *intNode) SetValue(nd Node) { z.val = nd.(*intNode).val }

A lot of stuff, you say? Yea, I guess. But factor 5 may be worth that. The
performance gain comes from storing the payload right inside the nodes,
rather than wrap an interface around them. Given that we do fancy data
structures for performance in the first place, I think that's a worthwhile
tradeoff.


Get the sources here: https://github.com/nes1983/sset


Niko

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Search Discussions

  • Dan Kortschak at Jun 6, 2013 at 11:21 pm
    Can you make that 'go get'-able? Do you have benchmark code in there (I
    couldn't find any); I'd like to compare against biogo.llrb.

    Dan

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Dan Kortschak at Jun 6, 2013 at 11:53 pm
    Nice work.

    Using this slightly altered intNode defintion:

    type intNode struct {
      val int
      left, right *intNode
      color sset.Color
    }

    func (z intNode) Cmp(nd sset.Node) int { return z.val - nd.(*intNode).val }
    func (z intNode) Left() (nd sset.Node, ok bool) { return z.left, z.left != nil }
    func (z intNode) Right() (nd sset.Node, ok bool) { return z.right, z.right != nil }
    func (z *intNode) SetLeft(nd sset.Node) { (*z).left = nd.(*intNode) }
    func (z *intNode) SetRight(nd sset.Node) { (*z).right = nd.(*intNode) }
    func (z intNode) Color() sset.Color { return z.color }
    func (z *intNode) SetColor(cl sset.Color) { (*z).color = cl }
    func (z *intNode) SetValue(nd sset.Node) { z.val = nd.(*intNode).val }


    BenchmarkInsert 1000000 1211 ns/op
    BenchmarkGet 5000000 554 ns/op

    BenchmarkInsertSSet 5000000 476 ns/op
    BenchmarkGetSSet 10000000 193 ns/op


    You're not far off the builtin:

    BenchmarkInsertMap 10000000 300 ns/op
    BenchmarkGetMap 20000000 130 ns/op

    Dan

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Roger peppe at Jun 7, 2013 at 10:41 am
    it's a nice idea but i'm sad to say the implementation is
    broken. if there was a test that a) added more than
    one element to the list and b) actually ran (tests must begin
    with a "Test" prefix) then it would become evident that the
    set never grows larger than one element and hence insertion
    and lookup times are really remarkably fast :-)

    here's a slightly different approach that doesn't require
    implementing quite as many methods each time
    and is somewhat more efficient to boot.

    http://play.golang.org/p/NqEplsTLcv

    the code still broken (i only fixed the most obvious
    problem in the most obvious way) but i think the API
    is perhaps worth considering.

    here's the test file i used: http://play.golang.org/p/uYYwbT0Fkk

    note that the Get benchmark hangs up - i think that insert
    might be O(n) or something. i have no time to investigate.

       cheers,
         rog.

    PS i am suspicious of all LLRB implementations without seriously
    comprehensive test suites - i made an implementation years ago
    which followed all the rules but was still broken in rare circumstances.
    you can't depend on everything in Sedgewick's slides.
    On 7 June 2013 00:53, Dan Kortschak wrote:
    Nice work.

    Using this slightly altered intNode defintion:

    type intNode struct {
    val int
    left, right *intNode
    color sset.Color
    }

    func (z intNode) Cmp(nd sset.Node) int { return z.val - nd.(*intNode).val }
    func (z intNode) Left() (nd sset.Node, ok bool) { return z.left, z.left != nil }
    func (z intNode) Right() (nd sset.Node, ok bool) { return z.right, z.right != nil }
    func (z *intNode) SetLeft(nd sset.Node) { (*z).left = nd.(*intNode) }
    func (z *intNode) SetRight(nd sset.Node) { (*z).right = nd.(*intNode) }
    func (z intNode) Color() sset.Color { return z.color }
    func (z *intNode) SetColor(cl sset.Color) { (*z).color = cl }
    func (z *intNode) SetValue(nd sset.Node) { z.val = nd.(*intNode).val }


    BenchmarkInsert 1000000 1211 ns/op
    BenchmarkGet 5000000 554 ns/op

    BenchmarkInsertSSet 5000000 476 ns/op
    BenchmarkGetSSet 10000000 193 ns/op


    You're not far off the builtin:

    BenchmarkInsertMap 10000000 300 ns/op
    BenchmarkGetMap 20000000 130 ns/op

    Dan

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Dan Kortschak at Jun 7, 2013 at 11:18 am
    Mmmm. I didn't run tests on it, just a modification of my benchmarks to
    take this implementation.

    That is sad. Though on the brighter side, it means I don't need to think
    about improving biogo.llrb.
    On Fri, 2013-06-07 at 11:41 +0100, roger peppe wrote:
    it's a nice idea but i'm sad to say the implementation is
    broken. if there was a test that a) added more than
    one element to the list and b) actually ran (tests must begin
    with a "Test" prefix) then it would become evident that the
    set never grows larger than one element and hence insertion
    and lookup times are really remarkably fast :-)

    here's a slightly different approach that doesn't require
    implementing quite as many methods each time
    and is somewhat more efficient to boot.

    http://play.golang.org/p/NqEplsTLcv

    the code still broken (i only fixed the most obvious
    problem in the most obvious way) but i think the API
    is perhaps worth considering.

    here's the test file i used: http://play.golang.org/p/uYYwbT0Fkk

    note that the Get benchmark hangs up - i think that insert
    might be O(n) or something. i have no time to investigate.

    cheers,
    rog.

    PS i am suspicious of all LLRB implementations without seriously
    comprehensive test suites - i made an implementation years ago
    which followed all the rules but was still broken in rare circumstances.
    you can't depend on everything in Sedgewick's slides.
    That's why my test suite is significantly longer than the actual
    implementation... and includes graphical output for failing cases :)

    Dan

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedJun 6, '13 at 5:09p
activeJun 7, '13 at 11:18a
posts5
users3
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase