diff options
Diffstat (limited to '')
-rw-r--r-- | dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/fannkuch-parallel.go | 227 |
1 files changed, 227 insertions, 0 deletions
diff --git a/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/fannkuch-parallel.go b/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/fannkuch-parallel.go new file mode 100644 index 0000000..a69b09c --- /dev/null +++ b/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/fannkuch-parallel.go @@ -0,0 +1,227 @@ +//go:build ignore +// +build ignore + +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* + * The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + * Based on fannkuch.scala by Rex Kerr + */ + +package main + +import ( + "flag" + "fmt" + "runtime" +) + +var n = flag.Int("n", 7, "count") +var nCPU = flag.Int("ncpu", 4, "number of cpus") + +type Job struct { + start []int + n int +} + +type Found struct { + who *Kucher + k int +} + +type Kucher struct { + perm []int + temp []int + flip []int + in chan Job +} + +func NewKucher(length int) *Kucher { + return &Kucher{ + perm: make([]int, length), + temp: make([]int, length), + flip: make([]int, length), + in: make(chan Job), + } +} + +func (k *Kucher) permute(n int) bool { + i := 0 + for ; i < n-1 && k.flip[i] == 0; i++ { + t := k.perm[0] + j := 0 + for ; j <= i; j++ { + k.perm[j] = k.perm[j+1] + } + k.perm[j] = t + } + k.flip[i]-- + for i > 0 { + i-- + k.flip[i] = i + } + return k.flip[n-1] >= 0 +} + +func (k *Kucher) count() int { + K := 0 + copy(k.temp, k.perm) + for k.temp[0] != 0 { + m := k.temp[0] + for i := 0; i < m; i++ { + k.temp[i], k.temp[m] = k.temp[m], k.temp[i] + m-- + } + K++ + } + return K +} + +func (k *Kucher) Run(foreman chan<- Found) { + for job := range k.in { + verbose := 30 + copy(k.perm, job.start) + for i, v := range k.perm { + if v != i { + verbose = 0 + } + k.flip[i] = i + } + K := 0 + for { + if verbose > 0 { + for _, p := range k.perm { + fmt.Print(p + 1) + } + fmt.Println() + verbose-- + } + count := k.count() + if count > K { + K = count + } + if !k.permute(job.n) { + break + } + } + foreman <- Found{k, K} + } +} + +type Fanner struct { + jobind int + jobsdone int + k int + jobs []Job + workers []*Kucher + in chan Found + result chan int +} + +func NewFanner(jobs []Job, workers []*Kucher) *Fanner { + return &Fanner{ + jobs: jobs, workers: workers, + in: make(chan Found), + result: make(chan int), + } +} + +func (f *Fanner) Run(N int) { + for msg := range f.in { + if msg.k > f.k { + f.k = msg.k + } + if msg.k >= 0 { + f.jobsdone++ + } + if f.jobind < len(f.jobs) { + msg.who.in <- f.jobs[f.jobind] + f.jobind++ + } else if f.jobsdone == len(f.jobs) { + f.result <- f.k + return + } + } +} + +func swapped(a []int, i, j int) []int { + b := make([]int, len(a)) + copy(b, a) + b[i], b[j] = a[j], a[i] + return b +} + +func main() { + flag.Parse() + runtime.GOMAXPROCS(*nCPU) + N := *n + base := make([]int, N) + for i := range base { + base[i] = i + } + + njobs := 1 + if N > 8 { + njobs += (N*(N-1))/2 - 28 // njobs = 1 + sum(8..N-1) = 1 + sum(1..N-1) - sum(1..7) + } + jobs := make([]Job, njobs) + jobsind := 0 + + firstN := N + if firstN > 8 { + firstN = 8 + } + jobs[jobsind] = Job{base, firstN} + jobsind++ + for i := N - 1; i >= 8; i-- { + for j := 0; j < i; j++ { + jobs[jobsind] = Job{swapped(base, i, j), i} + jobsind++ + } + } + + nworkers := *nCPU + if njobs < nworkers { + nworkers = njobs + } + workers := make([]*Kucher, nworkers) + foreman := NewFanner(jobs, workers) + go foreman.Run(N) + for i := range workers { + k := NewKucher(N) + workers[i] = k + go k.Run(foreman.in) + foreman.in <- Found{k, -1} + } + fmt.Printf("Pfannkuchen(%d) = %d\n", N, <-foreman.result) +} |