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