Without speaking to the correctness of your algorithm, I can tell you why
your results are not as you expect. It is a classic benchmark mistake. You
are creating your slice, filled with ordered integers, then running your
code on the same slice again and again. So after the first iteration the
slice is "sorted" already. For whatever reason, QuickFind likes this
scenario a lot, and QuickUnion does not. What you really want is to use the
same initial data for each iteration. That means resetting the 'a' slice
inside the "for i := 0; i < b.N; i++" loop. When the code is modified like
this:
package quickfind
import (
"fmt"
"testing"
)
type pair struct {
X int
Y int
}
func quickUnion(a []int, p, q int) {
var i, j int
for i = p; i != a[i]; i = a[i] {
}
for j = q; j != a[j]; j = a[j] {
}
if i != j {
a[i] = j
}
}
func qf(a []int, p, q int) {
// Are p and q already connected ?
if a[p] == a[q] {
return
}
n := len(a)
for i := 0; i < n; i++ {
if a[i] == a[p] {
a[i] = a[q]
}
}
}
func createSlice(n int) []int {
a := make([]int, n, n)
return a
}
func fillSlice(a []int) {
// initialize each element of the array to it's index value
for i := range a {
a[i] = i
}
}
func createPairs(bmTestSize int) []pair {
pairs := make([]pair, bmTestSize-1, bmTestSize-1)
// Create a slice of pairs
for j := 0; j < bmTestSize-1; j++ {
pairs[j] = pair{j, j + 1}
}
return pairs
}
func BenchmarkQuickUnion(b *testing.B) {
bmTestSizes := []int{10, 100, 1000, 10000}
for _, bmTestSize := range bmTestSizes {
bmName := fmt.Sprintf("BenchmarkQuickUnion%d", bmTestSize)
b.Run(bmName, func(b *testing.B) {
b.StopTimer()
pairs := createPairs(bmTestSize)
a := createSlice(bmTestSize)
pLen := bmTestSize - 1
b.StartTimer()
for i := 0; i < b.N; i++ {
b.StopTimer()
fillSlice(a)
b.StartTimer()
for j := 0; j < pLen; j++ {
quickUnion(a, pairs[j].X, pairs[j].Y)
}
}
})
}
}
func BenchmarkQuickFind(b *testing.B) {
bmTestSizes := []int{10, 100, 1000, 10000}
for _, bmTestSize := range bmTestSizes {
bmName := fmt.Sprintf("BenchmarkQuickFind%d", bmTestSize)
b.Run(bmName, func(b *testing.B) {
b.StopTimer()
pairs := createPairs(bmTestSize)
pLen := bmTestSize - 1
a := createSlice(bmTestSize)
b.StartTimer()
for i := 0; i < b.N; i++ {
b.StopTimer()
fillSlice(a)
b.StartTimer()
for j := 0; j < pLen; j++ {
qf(a, pairs[j].X, pairs[j].Y)
}
}
})
}
}
I get:
BenchmarkQuickUnion/BenchmarkQuickUnion10-4 6483990
158 ns/op
BenchmarkQuickUnion/BenchmarkQuickUnion100-4 2472957
531 ns/op
BenchmarkQuickUnion/BenchmarkQuickUnion1000-4 142843
7048 ns/op
BenchmarkQuickUnion/BenchmarkQuickUnion10000-4 17023
68428 ns/op
BenchmarkQuickFind/BenchmarkQuickFind10-4 3646029
328 ns/op
BenchmarkQuickFind/BenchmarkQuickFind100-4 88860
13043 ns/op
BenchmarkQuickFind/BenchmarkQuickFind1000-4 774
1488236 ns/op
BenchmarkQuickFind/BenchmarkQuickFind10000-4 7
150857786 ns/op
PASS
ok command-line-arguments 443.341s
QuickUnion outperforms QuickFind in every case, and massively outperforms
on large sets. Again, I have no idea if your code is actually correct.
Because the slice needs to be reconfigured for each run, it makes the high
iteration benchmarks (the ones with small sets) take a long time to run. On
my machine these took about 8 minutes, so be patient.
On Saturday, February 15, 2020 at 2:55:18 PM UTC-5, envee wrote:
>
> My apologies about syntax coloring.
> Here is the createSlice function :
>
> func createSlice(n int) []int {
> a := make([]int, n, n)
> // initialize each element of the array to it's index value
> for i := range a {
> a[i] = i
> }
> return a
> }
>
>
>
> On Sunday, 16 February 2020 06:31:49 UTC+11, Jake Montgomery wrote:
>>
>> On Saturday, February 15, 2020 at 6:24:02 AM UTC-5, envee wrote:
>>>
>>> Hi,
>>>
>>> I am using the following version of go :
>>> PS C:\Temp> go version
>>> go version go1.13.5 windows/amd64
>>>
>>> I am trying to compare the performance of QuickUnion (just the basic one
>>> with no weighting/ranking/path compression) and QuickFind algorithms.
>>> My benchmarking test cases basically create a (N-1) element array of
>>> pairs starting with (0,1), (1,2).....all the way upto (N-2,N-1). N is the
>>> number of data points. The benchmarking is run for N=10,100,1000.
>>> The benchmark functions then test the union-find functions by creating
>>> all the connections from the above array of pairs.
>>>
>>> From the Benchmarking results, it appears that the QuickUnion function
>>> is taking longer than the QuickFind function for the same data size and
>>> same set of input pairs.
>>>
>>> QuickFind benchmarking results.
>>> Running tool: C:\Go\bin\go.exe test -benchmem -run=^$ github.com\en-vee\ds
>>> -bench ^(BenchmarkQuickFind)$
>>>
>>> goos: windows
>>> goarch: amd64
>>> pkg: github.com/en-vee/ds
>>> BenchmarkQuickFind/BenchmarkQuickFind10-8 36392860
>>> 33.2 ns/op 0 B/op 0 allocs/op
>>> BenchmarkQuickFind/BenchmarkQuickFind100-8 3199598
>>> 388 ns/op 0 B/op 0 allocs/op
>>> BenchmarkQuickFind/BenchmarkQuickFind1000-8 300667
>>> 3852 ns/op 0 B/op 0 allocs/op
>>> PASS
>>> ok github.com/en-vee/ds 5.064s
>>> Success: Benchmarks passed.
>>>
>>>
>>> QuickUnion benchmarking results (See how much poorly they perform as
>>> compared to the QuickFind. The times per op are almost double the times for
>>> QuickFind).
>>>
>>> Running tool: C:\Go\bin\go.exe test -benchmem -run=^$ github.com\en-vee\ds
>>> -bench ^(BenchmarkQuickUnion)$
>>>
>>> goos: windows
>>> goarch: amd64
>>> pkg: github.com/en-vee/ds
>>> BenchmarkQuickUnion/BenchmarkQuickUnion10-8 17946232
>>> 65.4 ns/op 0 B/op 0 allocs/op
>>> BenchmarkQuickUnion/BenchmarkQuickUnion100-8 88495
>>> 13516 ns/op 0 B/op 0 allocs/op
>>> BenchmarkQuickUnion/BenchmarkQuickUnion1000-8 907
>>> 1328386 ns/op 0 B/op 0 allocs/op
>>> PASS
>>> ok github.com/en-vee/ds 4.691s
>>> Success: Benchmarks passed.
>>>
>>>
>>> Upon CPU profiling the BenchmarkQuickUnion test case, the two for loops
>>> related to the Find operation take the maximum time, but I am surprised
>>> that this function is taking longer because the loop does not iterate
>>> through the entire Array for any pair. Infact, I guess the loops must be
>>> performing only 2 iterations per pair. (Also see the pprof CPU profile
>>> attachment which shows the QuickUnion CPU profile for my function
>>> QuickUnion).
>>>
>>> Is the array lookup being performed by the Find operations in QuickUnion
>>> function, causing this performance bottleneck ?
>>>
>>> I guess the most surprising bit is : Why is QuickUnion slower than
>>> QuickFind for the same input data ? Or am I missing something ?
>>>
>>> (BTW, the implementations are based on Robert Sedgwick's equivalent
>>> implementations in C as given in his excellent book)
>>>
>>> The QuickUnion and Quick Find functions are as below :
>>>
>>> QuickUnion
>>>
>>> func quickUnion(a []int, p, q int) {
>>> var i, j int
>>>
>>> for i = p; i != a[i]; i = a[i] {
>>> }
>>>
>>> for j = q; j != a[j]; j = a[j] {
>>> }
>>>
>>> if i != j {
>>> a[i] = j
>>> }
>>> }
>>>
>>> QuickFind
>>>
>>> func qf(a []int, p, q int) {
>>> // Are p and q already connected ?
>>> if a[p] == a[q] {
>>> return
>>> }
>>>
>>> n := len(a)
>>>
>>> for i := 0; i < n; i++ {
>>> if a[i] == a[p] {
>>> a[i] = a[q]
>>> }
>>> }
>>> }
>>>
>>> My benchmarking test cases :
>>>
>>> BenchmarkQuickUnion
>>>
>>> func BenchmarkQuickUnion(b *testing.B) {
>>> type pair struct {
>>> X int
>>> Y int
>>> }
>>> bmTestSizes := []int{10, 100, 1000}
>>> for _, bmTestSize := range bmTestSizes {
>>> a := createSlice(bmTestSize)
>>> pairs := make([]pair, bmTestSize-1, bmTestSize-1)
>>> // Create a slice of pairs
>>> for j := 0; j < bmTestSize-1; j++ {
>>> pairs[j] = pair{j, j + 1}
>>> }
>>> pLen := bmTestSize - 1
>>> //b.ResetTimer()
>>> bmName := fmt.Sprintf("BenchmarkQuickUnion%d", bmTestSize)
>>> b.Run(bmName, func(b *testing.B) {
>>> for i := 0; i < b.N; i++ {
>>> for j := 0; j < pLen; j++ {
>>> quickUnion(a, pairs[j].X, pairs[j].Y)
>>> }
>>> //qf(a, (len(a)-1)/2, len(a)-1)
>>> }
>>> })
>>> }
>>> }
>>>
>>>
>>> BenchmarkQuickFind
>>> func BenchmarkQuickFind(b *testing.B) {
>>>
>>> type pair struct {
>>> X int
>>> Y int
>>> }
>>> bmTestSizes := []int{10, 100, 1000, 10000, 100000}
>>> for _, bmTestSize := range bmTestSizes {
>>> a := createSlice(bmTestSize)
>>> pairs := make([]pair, bmTestSize-1, bmTestSize-1)
>>> // Create a slice of pairs
>>> for j := 0; j < bmTestSize-1; j++ {
>>> pairs[j] = pair{j, j + 1}
>>> }
>>> pLen := bmTestSize - 1
>>>
>>> bmName := fmt.Sprintf("BenchmarkQuickFind%d", bmTestSize)
>>> b.Run(bmName, func(b *testing.B) {
>>> for i := 0; i < b.N; i++ {
>>> for j := 0; j < pLen; j++ {
>>> qf(a, pairs[j].X, pairs[j].Y)
>>> }
>>> }
>>> })
>>> }
>>> }
>>> Enter code here...
>>>
>>>
>>>
>> As Roberts said, please post code without color please. Use plain text,
>> or a simple code block, or the playground.
>> I would love to try to replicate your results, but the createSlice()
>> function is missing. Can you provide it?
>>
>
--
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/4ebb8098-5bc7-4c95-9b8a-e314384b59ec%40googlegroups.com.
