Hi all,
As a newbie I tried to implement a simple program calculating the Catalan
numbers, which are the numbers satisfying the recursion equation c(1) = 1;
c(n) = c(n - 1) * c(1) + c(n - 2) * c(2) + ... c(1) * c(n).
At first, I implemented it without channels:
package main
import (
"fmt"
"os"
"strconv"
)
func catalan(n int) int {
if n == 1 {
return 1
}
res := 0
for i := 1; i < n; i++ {
res += catalan(n - i) * catalan(i)
}
return res
}
func main() {
n, _ := strconv.Atoi(os.Args[1])
for i := 1; i <= n; i++ {
fmt.Println(catalan(i))
}
}
Then I thought the calculation can be easily made concurrent, so I wrote
the version below:
package main
import (
"fmt"
"os"
"strconv"
)
func catalan(n int, ch chan int) {
if n == 1 {
ch <- 1
return
}
res := 0
for i := 1; i < n; i++ {
ch1 := make(chan int)
ch2 := make(chan int)
go catalan(n - i, ch1)
go catalan(i, ch2)
res += <-ch1 * <-ch2
close(ch1)
close(ch2)
}
ch <- res
}
func main() {
n, _ := strconv.Atoi(os.Args[1])
for i := 1; i <= n; i++ {
q := make(chan int)
go catalan(i, q)
fmt.Println(<-q)
close(q)
}
}
But I found the second version was unexpectly slower than the first:
go run catalan.go 15 0.07s user 0.66s system 257% cpu 0.281 total
vs
go run catalan-parallel.go 15 3.80s user 0.97s system 130% cpu 3.662 total
What's the reason behind this? How can I improve this concurrent version to
make it faster?
--
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 [email protected].
For more options, visit https://groups.google.com/d/optout.
