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

Discussion Posts

Follow ups

Related Discussions

Discussion Navigation
viewthread | post
posts ‹ prev | 1 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