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