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 #![feature(slicing_syntax)]
  42
  43 use std::{cmp, iter, mem};
  44 use std::thread::Thread;
  45
  46 fn rotate(x: &mut [i32]) {
  47     let mut prev = x[0];
  48     for place in x.iter_mut().rev() {
  49         prev = mem::replace(place, prev)
  50     }
  51 }
  52
  53 fn next_permutation(perm: &mut [i32], count: &mut [i32]) {
  54     for i in range(1, perm.len()) {
  55         rotate(perm.slice_to_mut(i + 1));
  56         let count_i = &mut count[i];
  57         if *count_i >= i as i32 {
  58             *count_i = 0;
  59         } else {
  60             *count_i += 1;
  61             break
  62         }
  63     }
  64 }
  65
  66 struct P {
  67     p: [i32; 16],
  68 }
  69
  70 impl Copy for P {}
  71
  72 struct Perm {
  73     cnt: [i32; 16],
  74     fact: [u32; 16],
  75     n: u32,
  76     permcount: u32,
  77     perm: P,
  78 }
  79
  80 impl Copy for Perm {}
  81
  82 impl Perm {
  83     fn new(n: u32) -> Perm {
  84         let mut fact = [1; 16];
  85         for i in range(1, n as uint + 1) {
  86             fact[i] = fact[i - 1] * i as u32;
  87         }
  88         Perm {
  89             cnt: [0; 16],
  90             fact: fact,
  91             n: n,
  92             permcount: 0,
  93             perm: P { p: [0; 16 ] }
  94         }
  95     }
  96
  97     fn get(&mut self, mut idx: i32) -> P {
  98         let mut pp = [0u8; 16];
  99         self.permcount = idx as u32;
 100         for (i, place) in self.perm.p.iter_mut().enumerate() {
 101             *place = i as i32 + 1;
 102         }
 103
 104         for i in range(1, self.n as uint).rev() {
 105             let d = idx / self.fact[i] as i32;
 106             self.cnt[i] = d;
 107             idx %= self.fact[i] as i32;
 108             for (place, val) in pp.iter_mut().zip(self.perm.p[..i+1].iter()) {
 109                 *place = (*val) as u8
 110             }
 111
 112             let d = d as uint;
 113             for j in range(0, i + 1) {
 114                 self.perm.p[j] = if j + d <= i {pp[j + d]} else {pp[j+d-i-1]} as i32;
 115             }
 116         }
 117
 118         self.perm
 119     }
 120
 121     fn count(&self) -> u32 { self.permcount }
 122     fn max(&self) -> u32 { self.fact[self.n as uint] }
 123
 124     fn next(&mut self) -> P {
 125         next_permutation(&mut self.perm.p, &mut self.cnt);
 126         self.permcount += 1;
 127
 128         self.perm
 129     }
 130 }
 131
 132
 133 fn reverse(tperm: &mut [i32], mut k: uint) {
 134     tperm.slice_to_mut(k).reverse()
 135 }
 136
 137 fn work(mut perm: Perm, n: uint, max: uint) -> (i32, i32) {
 138     let mut checksum = 0;
 139     let mut maxflips = 0;
 140
 141     let mut p = perm.get(n as i32);
 142
 143     while perm.count() < max as u32 {
 144         let mut flips = 0;
 145
 146         while p.p[0] != 1 {
 147             let k = p.p[0] as uint;
 148             reverse(&mut p.p, k);
 149             flips += 1;
 150         }
 151
 152         checksum += if perm.count() % 2 == 0 {flips} else {-flips};
 153         maxflips = cmp::max(maxflips, flips);
 154
 155         p = perm.next();
 156     }
 157
 158     (checksum, maxflips)
 159 }
 160
 161 fn fannkuch(n: i32) -> (i32, i32) {
 162     let perm = Perm::new(n as u32);
 163
 164     let N = 4;
 165     let mut futures = vec![];
 166     let k = perm.max() / N;
 167
 168     for (i, j) in range(0, N).zip(iter::count(0, k)) {
 169         let max = cmp::min(j+k, perm.max());
 170
 171         futures.push(Thread::spawn(move|| {
 172             work(perm, j as uint, max as uint)
 173         }))
 174     }
 175
 176     let mut checksum = 0;
 177     let mut maxflips = 0;
 178     for fut in futures.into_iter() {
 179         let (cs, mf) = fut.join().ok().unwrap();
 180         checksum += cs;
 181         maxflips = cmp::max(maxflips, mf);
 182     }
 183     (checksum, maxflips)
 184 }
 185
 186 fn main() {
 187     let n = std::os::args().as_slice()
 188         .get(1)
 189         .and_then(|arg| arg.parse())
 190         .unwrap_or(2i32);
 191
 192     let (checksum, maxflips) = fannkuch(n);
 193     println!("{}\nPfannkuchen({}) = {}", checksum, n, maxflips);
 194 }