src/test/bench/shootout-fannkuch-redux.rs

   1 // The Computer Language Benchmarks Game
   2 // http://benchmarksgame.alioth.debian.org/
   3 //
   4 // contributed by the Rust Project Developers
   5
   6 // Copyright (c) 2014 The Rust Project Developers
   7 //
   8 // All rights reserved.
   9 //
  10 // Redistribution and use in source and binary forms, with or without
  11 // modification, are permitted provided that the following conditions
  12 // are met:
  13 //
  14 // - Redistributions of source code must retain the above copyright
  15 //   notice, this list of conditions and the following disclaimer.
  16 //
  17 // - Redistributions in binary form must reproduce the above copyright
  18 //   notice, this list of conditions and the following disclaimer in
  19 //   the documentation and/or other materials provided with the
  20 //   distribution.
  21 //
  22 // - Neither the name of "The Computer Language Benchmarks Game" nor
  23 //   the name of "The Computer Language Shootout Benchmarks" nor the
  24 //   names of its contributors may be used to endorse or promote
  25 //   products derived from this software without specific prior
  26 //   written permission.
  27 //
  28 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  29 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  30 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  31 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  32 // COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  33 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  34 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  35 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  36 // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  37 // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  38 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  39 // OF THE POSSIBILITY OF SUCH DAMAGE.
  40
  41 use std::{cmp, iter, mem};
  42 use std::thread::Thread;
  43
  44 fn rotate(x: &mut [i32]) {
  45     let mut prev = x[0];
  46     for place in x.iter_mut().rev() {
  47         prev = mem::replace(place, prev)
  48     }
  49 }
  50
  51 fn next_permutation(perm: &mut [i32], count: &mut [i32]) {
  52     for i in range(1, perm.len()) {
  53         rotate(perm.slice_to_mut(i + 1));
  54         let count_i = &mut count[i];
  55         if *count_i >= i as i32 {
  56             *count_i = 0;
  57         } else {
  58             *count_i += 1;
  59             break
  60         }
  61     }
  62 }
  63
  64 struct P {
  65     p: [i32; 16],
  66 }
  67
  68 impl Copy for P {}
  69
  70 struct Perm {
  71     cnt: [i32; 16],
  72     fact: [u32; 16],
  73     n: u32,
  74     permcount: u32,
  75     perm: P,
  76 }
  77
  78 impl Copy for Perm {}
  79
  80 impl Perm {
  81     fn new(n: u32) -> Perm {
  82         let mut fact = [1; 16];
  83         for i in range(1, n as uint + 1) {
  84             fact[i] = fact[i - 1] * i as u32;
  85         }
  86         Perm {
  87             cnt: [0; 16],
  88             fact: fact,
  89             n: n,
  90             permcount: 0,
  91             perm: P { p: [0; 16 ] }
  92         }
  93     }
  94
  95     fn get(&mut self, mut idx: i32) -> P {
  96         let mut pp = [0u8; 16];
  97         self.permcount = idx as u32;
  98         for (i, place) in self.perm.p.iter_mut().enumerate() {
  99             *place = i as i32 + 1;
 100         }
 101
 102         for i in range(1, self.n as uint).rev() {
 103             let d = idx / self.fact[i] as i32;
 104             self.cnt[i] = d;
 105             idx %= self.fact[i] as i32;
 106             for (place, val) in pp.iter_mut().zip(self.perm.p[..i+1].iter()) {
 107                 *place = (*val) as u8
 108             }
 109
 110             let d = d as uint;
 111             for j in range(0, i + 1) {
 112                 self.perm.p[j] = if j + d <= i {pp[j + d]} else {pp[j+d-i-1]} as i32;
 113             }
 114         }
 115
 116         self.perm
 117     }
 118
 119     fn count(&self) -> u32 { self.permcount }
 120     fn max(&self) -> u32 { self.fact[self.n as uint] }
 121
 122     fn next(&mut self) -> P {
 123         next_permutation(&mut self.perm.p, &mut self.cnt);
 124         self.permcount += 1;
 125
 126         self.perm
 127     }
 128 }
 129
 130
 131 fn reverse(tperm: &mut [i32], k: uint) {
 132     tperm.slice_to_mut(k).reverse()
 133 }
 134
 135 fn work(mut perm: Perm, n: uint, max: uint) -> (i32, i32) {
 136     let mut checksum = 0;
 137     let mut maxflips = 0;
 138
 139     let mut p = perm.get(n as i32);
 140
 141     while perm.count() < max as u32 {
 142         let mut flips = 0;
 143
 144         while p.p[0] != 1 {
 145             let k = p.p[0] as uint;
 146             reverse(&mut p.p, k);
 147             flips += 1;
 148         }
 149
 150         checksum += if perm.count() % 2 == 0 {flips} else {-flips};
 151         maxflips = cmp::max(maxflips, flips);
 152
 153         p = perm.next();
 154     }
 155
 156     (checksum, maxflips)
 157 }
 158
 159 fn fannkuch(n: i32) -> (i32, i32) {
 160     let perm = Perm::new(n as u32);
 161
 162     let N = 4;
 163     let mut futures = vec![];
 164     let k = perm.max() / N;
 165
 166     for (_, j) in range(0, N).zip(iter::count(0, k)) {
 167         let max = cmp::min(j+k, perm.max());
 168
 169         futures.push(Thread::scoped(move|| {
 170             work(perm, j as uint, max as uint)
 171         }))
 172     }
 173
 174     let mut checksum = 0;
 175     let mut maxflips = 0;
 176     for fut in futures.into_iter() {
 177         let (cs, mf) = fut.join().ok().unwrap();
 178         checksum += cs;
 179         maxflips = cmp::max(maxflips, mf);
 180     }
 181     (checksum, maxflips)
 182 }
 183
 184 fn main() {
 185     let n = std::os::args().as_slice()
 186         .get(1)
 187         .and_then(|arg| arg.parse())
 188         .unwrap_or(2i32);
 189
 190     let (checksum, maxflips) = fannkuch(n);
 191     println!("{}\nPfannkuchen({}) = {}", checksum, n, maxflips);
 192 }