Re: [go-nuts] Left-leaning Red-Black Trees, again

[Dan Kortschak]

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

[Dan Kortschak]

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

[roger peppe]

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.

> --
> 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...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Dan Kortschak]

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