Thanks Jake. That makes sense.
Because the slice was being reused as-is for each iteration, the QuickFind
was finishing much faster than the QuickUnion. That is because the find
part in the QuickFind function returned immediately as all pairs got
connected in a previous iteration.
I am confident that the functions for QuickUnion and QuickFind are
correctly implemented. (They are taken straight from Robert Sedgewick's
book, but just converted to go).
But, if I look at the CPU profile of these benchmarking functions, the
assignment to a slice element or a comparision of 2 slice elements takes
about 200 milliseconds and is one of the longest time-taking instruction.
On Saturday, 15 February 2020 22:24:02 UTC+11, 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...
>
>
>
--
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/d3a10abd-3463-47e4-8569-74bc11ef1ba1%40googlegroups.com.
