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