1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
extern crate clap;
extern crate rand;
use clap::{Arg, App};
use std::collections::vec_deque::VecDeque;
use std::io::{self, BufRead};
use std::result::Result;
fn some<R: rand::Rng, T: Iterator<Item = Result<String, io::Error>>>(
r: &mut R,
n: usize,
lines: T,
) -> Result<VecDeque<String>, io::Error> {
let mut result: VecDeque<String> = VecDeque::with_capacity(n);
fn push(v: &mut VecDeque<String>, n: usize, x: String) {
v.push_back(x);
if v.len() > n {
v.pop_front();
}
};
for (i, line) in lines.enumerate() {
let line = line?;
if result.len() < n {
push(&mut result, n, line);
} else if r.gen_range(0, i) < n {
let victim = r.gen_range(0, n);
result.remove(victim);
push(&mut result, n, line);
// Assumption: |result| contains m random elements from the (i-1)
// first lines.
//
// |line| is in result with n/i probability (if expression)
}
// An arbitrary line0 occuring before line was in result with
// probability m/(i-1).
//
// P(line0 is still in result) =
// m/i * (1 - 1/m) + (1 - m/i) =
// m/i - 1/i + 1 - m/i = 1 - 1/i = (i-1) / i
//
// The probability that an arbitrary line from the i first lines is in
// |result| is: m/(i-1) * ((i-1)/i) = m/i. The induction holds.
}
return Ok(result);
}
fn main() {
let matches = App::new("some")
.version("0.1")
.author("Kjetil Ørbekk <kj@orbekk.com>")
.arg(
Arg::with_name("lines")
.short("n")
.value_name("NUM")
.help("Number of lines to print")
.takes_value(true),
)
.get_matches();
let num_lines = matches
.value_of("lines")
.unwrap_or("10")
.parse::<usize>()
.expect("number of lines to print");
let stdin = io::stdin();
let lines = some(&mut rand::thread_rng(), num_lines, stdin.lock().lines());
match lines {
Ok(lines) => {
for line in lines {
println!("{}", line);
}
}
Err(e) => println!("Error: {}", e),
}
}
|
