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