Home | History | Annotate | Download | only in shootout 
      1 /*
      2 Redistribution and use in source and binary forms, with or without
      3 modification, are permitted provided that the following conditions are met:
      4 
      5     * Redistributions of source code must retain the above copyright
      6     notice, this list of conditions and the following disclaimer.
      7 
      8     * Redistributions in binary form must reproduce the above copyright
      9     notice, this list of conditions and the following disclaimer in the
     10     documentation and/or other materials provided with the distribution.
     11 
     12     * Neither the name of "The Computer Language Benchmarks Game" nor the
     13     name of "The Computer Language Shootout Benchmarks" nor the names of
     14     its contributors may be used to endorse or promote products derived
     15     from this software without specific prior written permission.
     16 
     17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
     18 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     19 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     20 ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
     21 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     22 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     23 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     24 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     25 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     26 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     27 POSSIBILITY OF SUCH DAMAGE.
     28 */
     29 
     30 /*
     31  * The Computer Language Benchmarks Game
     32  * http://shootout.alioth.debian.org/
     33  *
     34  * contributed by The Go Authors.
     35  * Based on fannkuch.scala by Rex Kerr
     36  */
     37 
     38 package main
     39 
     40 import (
     41 	"flag"
     42 	"fmt"
     43 	"runtime"
     44 )
     45 
     46 var n = flag.Int("n", 7, "count")
     47 var nCPU = flag.Int("ncpu", 4, "number of cpus")
     48 
     49 type Job struct {
     50 	start []int
     51 	n     int
     52 }
     53 
     54 type Found struct {
     55 	who *Kucher
     56 	k   int
     57 }
     58 
     59 type Kucher struct {
     60 	perm []int
     61 	temp []int
     62 	flip []int
     63 	in   chan Job
     64 }
     65 
     66 func NewKucher(length int) *Kucher {
     67 	return &Kucher{
     68 		perm: make([]int, length),
     69 		temp: make([]int, length),
     70 		flip: make([]int, length),
     71 		in:   make(chan Job),
     72 	}
     73 }
     74 
     75 func (k *Kucher) permute(n int) bool {
     76 	i := 0
     77 	for ; i < n-1 && k.flip[i] == 0; i++ {
     78 		t := k.perm[0]
     79 		j := 0
     80 		for ; j <= i; j++ {
     81 			k.perm[j] = k.perm[j+1]
     82 		}
     83 		k.perm[j] = t
     84 	}
     85 	k.flip[i]--
     86 	for i > 0 {
     87 		i--
     88 		k.flip[i] = i
     89 	}
     90 	return k.flip[n-1] >= 0
     91 }
     92 
     93 func (k *Kucher) count() int {
     94 	K := 0
     95 	copy(k.temp, k.perm)
     96 	for k.temp[0] != 0 {
     97 		m := k.temp[0]
     98 		for i := 0; i < m; i++ {
     99 			k.temp[i], k.temp[m] = k.temp[m], k.temp[i]
    100 			m--
    101 		}
    102 		K++
    103 	}
    104 	return K
    105 }
    106 
    107 func (k *Kucher) Run(foreman chan<- Found) {
    108 	for job := range k.in {
    109 		verbose := 30
    110 		copy(k.perm, job.start)
    111 		for i, v := range k.perm {
    112 			if v != i {
    113 				verbose = 0
    114 			}
    115 			k.flip[i] = i
    116 		}
    117 		K := 0
    118 		for {
    119 			if verbose > 0 {
    120 				for _, p := range k.perm {
    121 					fmt.Print(p + 1)
    122 				}
    123 				fmt.Println()
    124 				verbose--
    125 			}
    126 			count := k.count()
    127 			if count > K {
    128 				K = count
    129 			}
    130 			if !k.permute(job.n) {
    131 				break
    132 			}
    133 		}
    134 		foreman <- Found{k, K}
    135 	}
    136 }
    137 
    138 type Fanner struct {
    139 	jobind   int
    140 	jobsdone int
    141 	k        int
    142 	jobs     []Job
    143 	workers  []*Kucher
    144 	in       chan Found
    145 	result   chan int
    146 }
    147 
    148 func NewFanner(jobs []Job, workers []*Kucher) *Fanner {
    149 	return &Fanner{
    150 		jobs: jobs, workers: workers,
    151 		in:     make(chan Found),
    152 		result: make(chan int),
    153 	}
    154 }
    155 
    156 func (f *Fanner) Run(N int) {
    157 	for msg := range f.in {
    158 		if msg.k > f.k {
    159 			f.k = msg.k
    160 		}
    161 		if msg.k >= 0 {
    162 			f.jobsdone++
    163 		}
    164 		if f.jobind < len(f.jobs) {
    165 			msg.who.in <- f.jobs[f.jobind]
    166 			f.jobind++
    167 		} else if f.jobsdone == len(f.jobs) {
    168 			f.result <- f.k
    169 			return
    170 		}
    171 	}
    172 }
    173 
    174 func swapped(a []int, i, j int) []int {
    175 	b := make([]int, len(a))
    176 	copy(b, a)
    177 	b[i], b[j] = a[j], a[i]
    178 	return b
    179 }
    180 
    181 func main() {
    182 	flag.Parse()
    183 	runtime.GOMAXPROCS(*nCPU)
    184 	N := *n
    185 	base := make([]int, N)
    186 	for i := range base {
    187 		base[i] = i
    188 	}
    189 
    190 	njobs := 1
    191 	if N > 8 {
    192 		njobs += (N*(N-1))/2 - 28 // njobs = 1 + sum(8..N-1) = 1 + sum(1..N-1) - sum(1..7)
    193 	}
    194 	jobs := make([]Job, njobs)
    195 	jobsind := 0
    196 
    197 	firstN := N
    198 	if firstN > 8 {
    199 		firstN = 8
    200 	}
    201 	jobs[jobsind] = Job{base, firstN}
    202 	jobsind++
    203 	for i := N - 1; i >= 8; i-- {
    204 		for j := 0; j < i; j++ {
    205 			jobs[jobsind] = Job{swapped(base, i, j), i}
    206 			jobsind++
    207 		}
    208 	}
    209 
    210 	nworkers := *nCPU
    211 	if njobs < nworkers {
    212 		nworkers = njobs
    213 	}
    214 	workers := make([]*Kucher, nworkers)
    215 	foreman := NewFanner(jobs, workers)
    216 	go foreman.Run(N)
    217 	for i := range workers {
    218 		k := NewKucher(N)
    219 		workers[i] = k
    220 		go k.Run(foreman.in)
    221 		foreman.in <- Found{k, -1}
    222 	}
    223 	fmt.Printf("Pfannkuchen(%d) = %d\n", N, <-foreman.result)
    224 }
    225