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

Search Discussions

Discussion Posts

Previous

Follow ups

Related Discussions

Discussion Navigation
viewthread | post
posts ‹ prev | 4 of 5 | next ›
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