src/test/bench/shootout-k-nucleotide-pipes.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 // ignore-android: FIXME(#10393)
  12 // ignore-pretty very bad with line comments
  13
  14 // multi tasking k-nucleotide
  15
  16 #![feature(box_syntax)]
  17
  18 use std::ascii::{AsciiExt, OwnedAsciiExt};
  19 use std::cmp::Ordering::{self, Less, Greater, Equal};
  20 use std::collections::HashMap;
  21 use std::mem::replace;
  22 use std::num::Float;
  23 use std::option;
  24 use std::os;
  25 use std::sync::mpsc::{channel, Sender, Receiver};
  26 use std::thread::Thread;
  27
  28 fn f64_cmp(x: f64, y: f64) -> Ordering {
  29     // arbitrarily decide that NaNs are larger than everything.
  30     if y.is_nan() {
  31         Less
  32     } else if x.is_nan() {
  33         Greater
  34     } else if x < y {
  35         Less
  36     } else if x == y {
  37         Equal
  38     } else {
  39         Greater
  40     }
  41 }
  42
  43 // given a map, print a sorted version of it
  44 fn sort_and_fmt(mm: &HashMap<Vec<u8> , uint>, total: uint) -> String {
  45    fn pct(xx: uint, yy: uint) -> f64 {
  46       return (xx as f64) * 100.0 / (yy as f64);
  47    }
  48
  49    // sort by key, then by value
  50    fn sortKV(mut orig: Vec<(Vec<u8> ,f64)> ) -> Vec<(Vec<u8> ,f64)> {
  51         orig.sort_by(|&(ref a, _), &(ref b, _)| a.cmp(b));
  52         orig.sort_by(|&(_, a), &(_, b)| f64_cmp(b, a));
  53         orig
  54    }
  55
  56    let mut pairs = Vec::new();
  57
  58    // map -> [(k,%)]
  59    for (key, &val) in mm.iter() {
  60       pairs.push(((*key).clone(), pct(val, total)));
  61    }
  62
  63    let pairs_sorted = sortKV(pairs);
  64
  65    let mut buffer = String::new();
  66    for &(ref k, v) in pairs_sorted.iter() {
  67        buffer.push_str(format!("{:?} {:0.3}\n",
  68                                k.to_ascii_uppercase(),
  69                                v).as_slice());
  70    }
  71
  72    return buffer
  73 }
  74
  75 // given a map, search for the frequency of a pattern
  76 fn find(mm: &HashMap<Vec<u8> , uint>, key: String) -> uint {
  77    let key = key.into_ascii_lowercase();
  78    match mm.get(key.as_bytes()) {
  79       option::Option::None      => { return 0u; }
  80       option::Option::Some(&num) => { return num; }
  81    }
  82 }
  83
  84 // given a map, increment the counter for a key
  85 fn update_freq(mm: &mut HashMap<Vec<u8> , uint>, key: &[u8]) {
  86     let key = key.to_vec();
  87     let newval = match mm.remove(&key) {
  88         Some(v) => v + 1,
  89         None => 1
  90     };
  91     mm.insert(key, newval);
  92 }
  93
  94 // given a Vec<u8>, for each window call a function
  95 // i.e., for "hello" and windows of size four,
  96 // run it("hell") and it("ello"), then return "llo"
  97 fn windows_with_carry<F>(bb: &[u8], nn: uint, mut it: F) -> Vec<u8> where
  98     F: FnMut(&[u8]),
  99 {
 100    let mut ii = 0u;
 101
 102    let len = bb.len();
 103    while ii < len - (nn - 1u) {
 104       it(&bb[ii..ii+nn]);
 105       ii += 1u;
 106    }
 107
 108    return bb[len - (nn - 1u)..len].to_vec();
 109 }
 110
 111 fn make_sequence_processor(sz: uint,
 112                            from_parent: &Receiver<Vec<u8>>,
 113                            to_parent: &Sender<String>) {
 114    let mut freqs: HashMap<Vec<u8>, uint> = HashMap::new();
 115    let mut carry = Vec::new();
 116    let mut total: uint = 0u;
 117
 118    let mut line: Vec<u8>;
 119
 120    loop {
 121
 122        line = from_parent.recv().unwrap();
 123        if line == Vec::new() { break; }
 124
 125        carry.push_all(line.as_slice());
 126        carry = windows_with_carry(carry.as_slice(), sz, |window| {
 127            update_freq(&mut freqs, window);
 128            total += 1u;
 129        });
 130    }
 131
 132    let buffer = match sz {
 133        1u => { sort_and_fmt(&freqs, total) }
 134        2u => { sort_and_fmt(&freqs, total) }
 135        3u => { format!("{}\t{}", find(&freqs, "GGT".to_string()), "GGT") }
 136        4u => { format!("{}\t{}", find(&freqs, "GGTA".to_string()), "GGTA") }
 137        6u => { format!("{}\t{}", find(&freqs, "GGTATT".to_string()), "GGTATT") }
 138       12u => { format!("{}\t{}", find(&freqs, "GGTATTTTAATT".to_string()), "GGTATTTTAATT") }
 139       18u => { format!("{}\t{}", find(&freqs, "GGTATTTTAATTTATAGT".to_string()),
 140                        "GGTATTTTAATTTATAGT") }
 141         _ => { "".to_string() }
 142    };
 143
 144     to_parent.send(buffer).unwrap();
 145 }
 146
 147 // given a FASTA file on stdin, process sequence THREE
 148 fn main() {
 149     use std::io::{stdio, MemReader, BufferedReader};
 150
 151     let rdr = if os::getenv("RUST_BENCH").is_some() {
 152         let foo = include_bytes!("shootout-k-nucleotide.data");
 153         box MemReader::new(foo.to_vec()) as Box<Reader>
 154     } else {
 155         box stdio::stdin() as Box<Reader>
 156     };
 157     let mut rdr = BufferedReader::new(rdr);
 158
 159     // initialize each sequence sorter
 160     let sizes = vec!(1u,2,3,4,6,12,18);
 161     let mut streams = range(0, sizes.len()).map(|_| {
 162         Some(channel::<String>())
 163     }).collect::<Vec<_>>();
 164     let mut from_child = Vec::new();
 165     let to_child  = sizes.iter().zip(streams.iter_mut()).map(|(sz, stream_ref)| {
 166         let sz = *sz;
 167         let stream = replace(stream_ref, None);
 168         let (to_parent_, from_child_) = stream.unwrap();
 169
 170         from_child.push(from_child_);
 171
 172         let (to_child, from_parent) = channel();
 173
 174         Thread::spawn(move|| {
 175             make_sequence_processor(sz, &from_parent, &to_parent_);
 176         });
 177
 178         to_child
 179     }).collect::<Vec<Sender<Vec<u8> >> >();
 180
 181
 182    // latch stores true after we've started
 183    // reading the sequence of interest
 184    let mut proc_mode = false;
 185
 186    for line in rdr.lines() {
 187        let line = line.unwrap().as_slice().trim().to_string();
 188
 189        if line.len() == 0u { continue; }
 190
 191        match (line.as_bytes()[0] as char, proc_mode) {
 192
 193            // start processing if this is the one
 194            ('>', false) => {
 195                match line.as_slice().slice_from(1).find_str("THREE") {
 196                    Some(_) => { proc_mode = true; }
 197                    None    => { }
 198                }
 199            }
 200
 201            // break our processing
 202            ('>', true) => { break; }
 203
 204            // process the sequence for k-mers
 205            (_, true) => {
 206                let line_bytes = line.as_bytes();
 207
 208                for (ii, _sz) in sizes.iter().enumerate() {
 209                    let lb = line_bytes.to_vec();
 210                    to_child[ii].send(lb).unwrap();
 211                }
 212            }
 213
 214            // whatever
 215            _ => { }
 216        }
 217    }
 218
 219    // finish...
 220    for (ii, _sz) in sizes.iter().enumerate() {
 221        to_child[ii].send(Vec::new()).unwrap();
 222    }
 223
 224    // now fetch and print result messages
 225    for (ii, _sz) in sizes.iter().enumerate() {
 226        println!("{:?}", from_child[ii].recv().unwrap());
 227    }
 228 }