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