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

## Related Discussions

 view thread | post posts ‹ prev | 4 of 5 | next ›
Discussion Overview
 group golang-nuts categories go posted Jun 6, '13 at 5:09p active Jun 7, '13 at 11:18a posts 5 users 3 website golang.org

### 3 users in discussion

Content

People

Support

Translate

site design / logo © 2022 Grokbase