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