src/test/bench/shootout-k-nucleotide.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 // ignore-android see #10393 #13206
  42
  43 #![feature(slicing_syntax)]
  44
  45 use std::string::String;
  46 use std::slice;
  47 use std::sync::{Arc, Future};
  48
  49 static TABLE: [u8, ..4] = [ 'A' as u8, 'C' as u8, 'G' as u8, 'T' as u8 ];
  50 static TABLE_SIZE: uint = 2 << 16;
  51
  52 static OCCURRENCES: [&'static str, ..5] = [
  53     "GGT",
  54     "GGTA",
  55     "GGTATT",
  56     "GGTATTTTAATT",
  57     "GGTATTTTAATTTATAGT",
  58 ];
  59
  60 // Code implementation
  61
  62 #[deriving(PartialEq, PartialOrd, Ord, Eq)]
  63 struct Code(u64);
  64
  65 impl Code {
  66     fn hash(&self) -> u64 {
  67         let Code(ret) = *self;
  68         return ret;
  69     }
  70
  71     fn push_char(&self, c: u8) -> Code {
  72         Code((self.hash() << 2) + (pack_symbol(c) as u64))
  73     }
  74
  75     fn rotate(&self, c: u8, frame: uint) -> Code {
  76         Code(self.push_char(c).hash() & ((1u64 << (2 * frame)) - 1))
  77     }
  78
  79     fn pack(string: &str) -> Code {
  80         string.bytes().fold(Code(0u64), |a, b| a.push_char(b))
  81     }
  82
  83     fn unpack(&self, frame: uint) -> String {
  84         let mut key = self.hash();
  85         let mut result = Vec::new();
  86         for _ in range(0, frame) {
  87             result.push(unpack_symbol((key as u8) & 3));
  88             key >>= 2;
  89         }
  90
  91         result.reverse();
  92         String::from_utf8(result).unwrap()
  93     }
  94 }
  95
  96 // Hash table implementation
  97
  98 trait TableCallback {
  99     fn f(&self, entry: &mut Entry);
 100 }
 101
 102 struct BumpCallback;
 103
 104 impl TableCallback for BumpCallback {
 105     fn f(&self, entry: &mut Entry) {
 106         entry.count += 1;
 107     }
 108 }
 109
 110 struct PrintCallback(&'static str);
 111
 112 impl TableCallback for PrintCallback {
 113     fn f(&self, entry: &mut Entry) {
 114         let PrintCallback(s) = *self;
 115         println!("{}\t{}", entry.count as int, s);
 116     }
 117 }
 118
 119 struct Entry {
 120     code: Code,
 121     count: uint,
 122     next: Option<Box<Entry>>,
 123 }
 124
 125 struct Table {
 126     items: Vec<Option<Box<Entry>>>
 127 }
 128
 129 struct Items<'a> {
 130     cur: Option<&'a Entry>,
 131     items: slice::Items<'a, Option<Box<Entry>>>,
 132 }
 133
 134 impl Table {
 135     fn new() -> Table {
 136         Table {
 137             items: Vec::from_fn(TABLE_SIZE, |_| None),
 138         }
 139     }
 140
 141     fn search_remainder<C:TableCallback>(item: &mut Entry, key: Code, c: C) {
 142         match item.next {
 143             None => {
 144                 let mut entry = box Entry {
 145                     code: key,
 146                     count: 0,
 147                     next: None,
 148                 };
 149                 c.f(&mut *entry);
 150                 item.next = Some(entry);
 151             }
 152             Some(ref mut entry) => {
 153                 if entry.code == key {
 154                     c.f(&mut **entry);
 155                     return;
 156                 }
 157
 158                 Table::search_remainder(&mut **entry, key, c)
 159             }
 160         }
 161     }
 162
 163     fn lookup<C:TableCallback>(&mut self, key: Code, c: C) {
 164         let index = key.hash() % (TABLE_SIZE as u64);
 165
 166         {
 167             if self.items[index as uint].is_none() {
 168                 let mut entry = box Entry {
 169                     code: key,
 170                     count: 0,
 171                     next: None,
 172                 };
 173                 c.f(&mut *entry);
 174                 self.items[index as uint] = Some(entry);
 175                 return;
 176             }
 177         }
 178
 179         {
 180             let entry = self.items[index as uint].as_mut().unwrap();
 181             if entry.code == key {
 182                 c.f(&mut **entry);
 183                 return;
 184             }
 185
 186             Table::search_remainder(&mut **entry, key, c)
 187         }
 188     }
 189
 190     fn iter(&self) -> Items {
 191         Items { cur: None, items: self.items.iter() }
 192     }
 193 }
 194
 195 impl<'a> Iterator<&'a Entry> for Items<'a> {
 196     fn next(&mut self) -> Option<&'a Entry> {
 197         let ret = match self.cur {
 198             None => {
 199                 let i;
 200                 loop {
 201                     match self.items.next() {
 202                         None => return None,
 203                         Some(&None) => {}
 204                         Some(&Some(ref a)) => { i = &**a; break }
 205                     }
 206                 }
 207                 self.cur = Some(&*i);
 208                 &*i
 209             }
 210             Some(c) => c
 211         };
 212         match ret.next {
 213             None => { self.cur = None; }
 214             Some(ref next) => { self.cur = Some(&**next); }
 215         }
 216         return Some(ret);
 217     }
 218 }
 219
 220 // Main program
 221
 222 fn pack_symbol(c: u8) -> u8 {
 223     match c as char {
 224         'A' => 0,
 225         'C' => 1,
 226         'G' => 2,
 227         'T' => 3,
 228         _ => panic!("{}", c as char),
 229     }
 230 }
 231
 232 fn unpack_symbol(c: u8) -> u8 {
 233     TABLE[c as uint]
 234 }
 235
 236 fn generate_frequencies(mut input: &[u8], frame: uint) -> Table {
 237     let mut frequencies = Table::new();
 238     if input.len() < frame { return frequencies; }
 239     let mut code = Code(0);
 240
 241     // Pull first frame.
 242     for _ in range(0, frame) {
 243         code = code.push_char(input[0]);
 244         input = input[1..];
 245     }
 246     frequencies.lookup(code, BumpCallback);
 247
 248     while input.len() != 0 && input[0] != ('>' as u8) {
 249         code = code.rotate(input[0], frame);
 250         frequencies.lookup(code, BumpCallback);
 251         input = input[1..];
 252     }
 253     frequencies
 254 }
 255
 256 fn print_frequencies(frequencies: &Table, frame: uint) {
 257     let mut vector = Vec::new();
 258     for entry in frequencies.iter() {
 259         vector.push((entry.count, entry.code));
 260     }
 261     vector.as_mut_slice().sort();
 262
 263     let mut total_count = 0;
 264     for &(count, _) in vector.iter() {
 265         total_count += count;
 266     }
 267
 268     for &(count, key) in vector.iter().rev() {
 269         println!("{} {:.3}",
 270                  key.unpack(frame).as_slice(),
 271                  (count as f32 * 100.0) / (total_count as f32));
 272     }
 273     println!("");
 274 }
 275
 276 fn print_occurrences(frequencies: &mut Table, occurrence: &'static str) {
 277     frequencies.lookup(Code::pack(occurrence), PrintCallback(occurrence))
 278 }
 279
 280 fn get_sequence<R: Buffer>(r: &mut R, key: &str) -> Vec<u8> {
 281     let mut res = Vec::new();
 282     for l in r.lines().map(|l| l.ok().unwrap())
 283         .skip_while(|l| key != l.as_slice().slice_to(key.len())).skip(1)
 284     {
 285         res.push_all(l.as_slice().trim().as_bytes());
 286     }
 287     for b in res.iter_mut() {
 288         *b = b.to_ascii().to_uppercase().to_byte();
 289     }
 290     res
 291 }
 292
 293 fn main() {
 294     let input = if std::os::getenv("RUST_BENCH").is_some() {
 295         let fd = std::io::File::open(&Path::new("shootout-k-nucleotide.data"));
 296         get_sequence(&mut std::io::BufferedReader::new(fd), ">THREE")
 297     } else {
 298         get_sequence(&mut *std::io::stdin().lock(), ">THREE")
 299     };
 300     let input = Arc::new(input);
 301
 302     let nb_freqs: Vec<(uint, Future<Table>)> = range(1u, 3).map(|i| {
 303         let input = input.clone();
 304         (i, Future::spawn(proc() generate_frequencies(input.as_slice(), i)))
 305     }).collect();
 306     let occ_freqs: Vec<Future<Table>> = OCCURRENCES.iter().map(|&occ| {
 307         let input = input.clone();
 308         Future::spawn(proc() generate_frequencies(input.as_slice(), occ.len()))
 309     }).collect();
 310
 311     for (i, freq) in nb_freqs.into_iter() {
 312         print_frequencies(&freq.unwrap(), i);
 313     }
 314     for (&occ, freq) in OCCURRENCES.iter().zip(occ_freqs.into_iter()) {
 315         print_occurrences(&mut freq.unwrap(), occ);
 316     }
 317 }