src/test/bench/core-map.rs

   1 // Copyright 2013 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 #![feature(unboxed_closures)]
  12
  13 use std::collections::{BTreeMap, HashMap, HashSet};
  14 use std::os;
  15 use std::rand::{Rng, IsaacRng, SeedableRng};
  16 use std::str::from_str;
  17 use std::time::Duration;
  18 use std::uint;
  19
  20 fn timed<F>(label: &str, f: F) where F: FnMut() {
  21     println!("  {}: {}", label, Duration::span(f));
  22 }
  23
  24 trait MutableMap {
  25     fn insert(&mut self, k: uint, v: uint);
  26     fn remove(&mut self, k: &uint) -> bool;
  27     fn find(&self, k: &uint) -> Option<&uint>;
  28 }
  29
  30 impl MutableMap for BTreeMap<uint, uint> {
  31     fn insert(&mut self, k: uint, v: uint) { self.insert(k, v); }
  32     fn remove(&mut self, k: &uint) -> bool { self.remove(k).is_some() }
  33     fn find(&self, k: &uint) -> Option<&uint> { self.get(k) }
  34 }
  35 impl MutableMap for HashMap<uint, uint> {
  36     fn insert(&mut self, k: uint, v: uint) { self.insert(k, v); }
  37     fn remove(&mut self, k: &uint) -> bool { self.remove(k).is_some() }
  38     fn find(&self, k: &uint) -> Option<&uint> { self.get(k) }
  39 }
  40
  41 fn ascending<M: MutableMap>(map: &mut M, n_keys: uint) {
  42     println!(" Ascending integers:");
  43
  44     timed("insert", || {
  45         for i in range(0u, n_keys) {
  46             map.insert(i, i + 1);
  47         }
  48     });
  49
  50     timed("search", || {
  51         for i in range(0u, n_keys) {
  52             assert_eq!(map.find(&i).unwrap(), &(i + 1));
  53         }
  54     });
  55
  56     timed("remove", || {
  57         for i in range(0, n_keys) {
  58             assert!(map.remove(&i));
  59         }
  60     });
  61 }
  62
  63 fn descending<M: MutableMap>(map: &mut M, n_keys: uint) {
  64     println!(" Descending integers:");
  65
  66     timed("insert", || {
  67         for i in range(0, n_keys).rev() {
  68             map.insert(i, i + 1);
  69         }
  70     });
  71
  72     timed("search", || {
  73         for i in range(0, n_keys).rev() {
  74             assert_eq!(map.find(&i).unwrap(), &(i + 1));
  75         }
  76     });
  77
  78     timed("remove", || {
  79         for i in range(0, n_keys) {
  80             assert!(map.remove(&i));
  81         }
  82     });
  83 }
  84
  85 fn vector<M: MutableMap>(map: &mut M, n_keys: uint, dist: &[uint]) {
  86     timed("insert", || {
  87         for i in range(0u, n_keys) {
  88             map.insert(dist[i], i + 1);
  89         }
  90     });
  91
  92     timed("search", || {
  93         for i in range(0u, n_keys) {
  94             assert_eq!(map.find(&dist[i]).unwrap(), &(i + 1));
  95         }
  96     });
  97
  98     timed("remove", || {
  99         for i in range(0u, n_keys) {
 100             assert!(map.remove(&dist[i]));
 101         }
 102     });
 103 }
 104
 105 fn main() {
 106     let args = os::args();
 107     let args = args.as_slice();
 108     let n_keys = {
 109         if args.len() == 2 {
 110             from_str::<uint>(args[1].as_slice()).unwrap()
 111         } else {
 112             1000000
 113         }
 114     };
 115
 116     let mut rand = Vec::with_capacity(n_keys);
 117
 118     {
 119         let seed: &[_] = &[1, 1, 1, 1, 1, 1, 1];
 120         let mut rng: IsaacRng = SeedableRng::from_seed(seed);
 121         let mut set = HashSet::new();
 122         while set.len() != n_keys {
 123             let next = rng.gen();
 124             if set.insert(next) {
 125                 rand.push(next);
 126             }
 127         }
 128     }
 129
 130     println!("{} keys", n_keys);
 131
 132     // FIXME: #9970
 133     println!("{}", "\nBTreeMap:");
 134
 135     {
 136         let mut map: BTreeMap<uint,uint> = BTreeMap::new();
 137         ascending(&mut map, n_keys);
 138     }
 139
 140     {
 141         let mut map: BTreeMap<uint,uint> = BTreeMap::new();
 142         descending(&mut map, n_keys);
 143     }
 144
 145     {
 146         println!(" Random integers:");
 147         let mut map: BTreeMap<uint,uint> = BTreeMap::new();
 148         vector(&mut map, n_keys, rand.as_slice());
 149     }
 150
 151     // FIXME: #9970
 152     println!("{}", "\nHashMap:");
 153
 154     {
 155         let mut map: HashMap<uint,uint> = HashMap::new();
 156         ascending(&mut map, n_keys);
 157     }
 158
 159     {
 160         let mut map: HashMap<uint,uint> = HashMap::new();
 161         descending(&mut map, n_keys);
 162     }
 163
 164     {
 165         println!(" Random integers:");
 166         let mut map: HashMap<uint,uint> = HashMap::new();
 167         vector(&mut map, n_keys, rand.as_slice());
 168     }
 169 }