Hi All,
Last year, I had asked something similar about comparing QuickUnion with
QuickFind although that turned out to be a flaw in my benchmarking function.
This time, I am comparing the QuickUnion with WeightedQuickUnion.
I ran benchmarking on this code and noticed that the WeightedQuickUnion
actually runs slower than the QuickUnion (contrary to my understanding).
I can confirm that my implementation of the algorithms is correct.
*So I am not able to understand why QuickUnion performs better than
WeightedQuickUnion ?*
I believe that the difference is probably because in WeightedQuickUnion,
there is a lot of time spent in comparing the sizes of 2 nodes and then
attaching the smaller sized tree to the larger sized tree. I was able to
check this by performing profiling and here is what I see.
WeighteQuickUnion spends about 750ms in performing the comparisons and
updating the array elements on line numbers 85-90.
(pprof) list WeightedQuickUnion
Total: 4.26s
ROUTINE ======================== ds.(*DynamicConnector).WeightedQuickUnion
in /Users/neeraj.vaidyamatrixx.com/Work/Matrixx/src/ds/uf.go
1.26s 2.27s (flat, cum) 53.29% of Total
. . 72: // Union
. . 73: dc.elements[rootp] = dc.elements[rootq]
. . 74: return false
. . 75:}
. . 76:
130ms 130ms 77:func (dc *DynamicConnector)
WeightedQuickUnion(p, q int) bool {
. . 78: // Find
40ms 1.04s 79: rootp, rootq := dc.getRoot(p),
dc.getRoot(q)
150ms 150ms 80: if rootp == rootq {
. . 81: return true
. . 82: }
. . 83: // Union
. . 84: // update root depending on which tree is
bigger
*280ms 280ms 85: if dc.nodeWeight[rootp] <=
dc.nodeWeight[rootq] { . . 86:
dc.elements[rootp] = rootq 40ms 40ms 87:
dc.nodeWeight[rootq] += dc.nodeWeight[rootp] . .
88: } else { 10ms 10ms 89: dc.elements[rootq] =
rootp 410ms 420ms 90: dc.nodeWeight[rootp] +=
dc.nodeWeight[rootq] . . 91: }*
200ms 200ms 92: return false
. . 93:}
. . 94:
. . 95:func (dc *DynamicConnector)
WeightedQuickUnionWithPathCompression(p, q int) bool {
. . 96: return false
. . 97:}
Given below is all my code.
My benchmarking functions :
*uf_test.go*
package ds
import (
"fmt"
"testing"
)
var elementsMap map[int][]int
var nodeWeightsMap map[int][]int
func init() {
elementsMap = map[int][]int{
10: make([]int, 10),
1000: make([]int, 1000),
100000: make([]int, 100000),
1000000: make([]int, 1000000),
}
for _, v := range elementsMap {
initElementsArray(v)
}
nodeWeightsMap = map[int][]int{
10: make([]int, 10),
1000: make([]int, 1000),
100000: make([]int, 100000),
1000000: make([]int, 1000000),
}
for _, v := range nodeWeightsMap {
initWeightsArray(v)
}
}
func initElementsArray(elems []int) {
for i := range elems {
elems[i] = i
}
}
func initWeightsArray(elems []int) {
for i := range elems {
elems[i] = 1
}
}
func BenchmarkQuickUnion(b *testing.B) {
testData := []DynamicConnector{
NewDynamicConnector(QuickUnion, 10),
NewDynamicConnector(QuickUnion, 1000),
NewDynamicConnector(QuickUnion, 100000),
}
for _, dc := range testData {
b.Run(fmt.Sprintf("Size-%d", dc.size), func(b *testing.B) {
for i := 0; i < b.N; i++ {
for j := 1; j < dc.size-1; j++ {
if dc.connect(j, j+1) {
b.Errorf("error")
}
}
if dc.connect(0, 1) {
b.Errorf("error")
}
copy(dc.elements, elementsMap[dc.size])
}
})
}
}
func BenchmarkWeightedQuickUnion(b *testing.B) {
testData := []DynamicConnector{
NewDynamicConnector(WeightedQuickUnion, 10),
NewDynamicConnector(WeightedQuickUnion, 1000),
NewDynamicConnector(WeightedQuickUnion, 100000),
}
for _, dc := range testData {
b.Run(fmt.Sprintf("Size-%d", dc.size), func(b *testing.B) {
for i := 0; i < b.N; i++ {
for j := 1; j < dc.size-1; j++ {
if dc.connect(j, j+1) {
b.Errorf("error")
}
}
if dc.connect(0, 1) {
b.Errorf("error")
}
copy(dc.elements, elementsMap[dc.size])
copy(dc.nodeWeight, nodeWeightsMap[dc.size])
}
})
}
}
My code is as follows :
*uf.go*
package ds
type DynamicConnector struct {
elements []int
nodeWeight []int
typ ConnectorType
size int
connect func(p, q int) bool
}
type ConnectorType int
const (
QuickFind ConnectorType = iota
QuickUnion
WeightedQuickUnion
WeightedQuickUnionWithPathCompression
)
func NewDynamicConnector(connectorType ConnectorType, size int)
DynamicConnector {
dynamicConnector := DynamicConnector{typ: connectorType, size: size}
dynamicConnector.elements = make([]int, size)
// initialize
for i := range dynamicConnector.elements {
dynamicConnector.elements[i] = i
}
switch connectorType {
case WeightedQuickUnion, WeightedQuickUnionWithPathCompression:
dynamicConnector.nodeWeight = make([]int, size)
for i := range dynamicConnector.nodeWeight {
dynamicConnector.nodeWeight[i] = 1
}
}
if connectorType == QuickFind {
dynamicConnector.connect = dynamicConnector.QuickFind
} else if connectorType == QuickUnion {
dynamicConnector.connect = dynamicConnector.QuickUnion
} else if connectorType == WeightedQuickUnion {
dynamicConnector.connect = dynamicConnector.WeightedQuickUnion
} else if connectorType == WeightedQuickUnionWithPathCompression {
dynamicConnector.connect =
dynamicConnector.WeightedQuickUnionWithPathCompression
}
return dynamicConnector
}
func (dc *DynamicConnector) Connect(p, q int) bool {
return dc.connect(p, q)
}
func (dc *DynamicConnector) QuickFind(p, q int) bool {
// Find
if dc.elements[p] == dc.elements[q] {
return true
}
// Union
for t, i := dc.elements[p], 0; i < dc.size; i++ {
if dc.elements[i] == t {
dc.elements[i] = dc.elements[q]
}
}
return false
}
// QuickUnion returns true if nodes are already connected and false
otherwise
func (dc *DynamicConnector) QuickUnion(p, q int) bool {
// Find
rootp, rootq := dc.getRoot(p), dc.getRoot(q)
if rootp == rootq {
return true
}
// Union
dc.elements[rootp] = rootq
return false
}
// WeightedQuickUnion returns true if nodes are already connected and false
otherwise
func (dc *DynamicConnector) WeightedQuickUnion(p, q int) bool {
// Find
rootp, rootq := dc.getRoot(p), dc.getRoot(q)
if rootp == rootq {
return true
}
// Union
// update root depending on which tree is bigger
if dc.nodeWeight[rootp] <= dc.nodeWeight[rootq] {
dc.elements[rootp] = rootq
dc.nodeWeight[rootq] += dc.nodeWeight[rootp]
} else {
dc.elements[rootq] = rootp
dc.nodeWeight[rootp] += dc.nodeWeight[rootq]
}
return false
}
func (dc *DynamicConnector) WeightedQuickUnionWithPathCompression(p, q int)
bool {
return false
}
func (dc *DynamicConnector) getRoot(p int) int {
root := p
for ; dc.elements[root] != root; root = dc.elements[root] {
}
return root
}
--
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/golang-nuts/5b80484d-4e79-4964-98a4-95458010d6f5n%40googlegroups.com.
