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