Debian Codegraph @

README

raw
1 NAME
2 Algorithm::Numerical::Sample - Draw samples from a set
3
4 SYNOPSIS
5 use Algorithm::Numerical::Sample qw /sample/;
6
7 @sample = sample (-set => [1 .. 10000],
8 -sample_size => 100);
9
10 $sampler = Algorithm::Numerical::Sample::Stream -> new;
11 while (<>) {$sampler -> data ($_)}
12 $random_line = $sampler -> extract;
13
14 DESCRIPTION
15 This package gives two methods to draw fair, random samples from a set.
16 There is a procedural interface for the case the entire set is known,
17 and an object oriented interface when the a set with unknown size has to
18 be processed.
19
20 A: "sample (set => ARRAYREF [,sample_size => EXPR])"
21 The "sample" function takes a set and a sample size as arguments. If the
22 sample size is omitted, a sample of 1 is taken. The keywords "set" and
23 "sample_size" may be preceeded with an optional "-". The function
24 returns the sample list, or a reference to the sample list, depending on
25 the context.
26
27 B: "Algorithm::Numerical::Sample::Stream"
28 The class "Algorithm::Numerical::Sample::Stream" has the following
29 methods:
30
31 "new"
32 This function returns an object of the
33 "Algorithm::Numerical::Sample::Stream" class. It will take an
34 optional argument of the form "sample_size => EXPR", where "EXPR"
35 evaluates to the sample size to be taken. If this argument is
36 missing, a sample of size 1 will be taken. The keyword "sample_size"
37 may be preceeded by an optional dash.
38
39 "data (LIST)"
40 The method "data" takes a list of parameters which are elements of
41 the set we are sampling. Any number of arguments can be given.
42
43 "extract"
44 This method will extract the sample from the object, and reset it to
45 a fresh state, such that a sample of the same size but from a
46 different set, can be taken. "extract" will return a list in list
47 context, or the first element of the sample in scalar context.
48
49 CORRECTNESS PROOFS
50 Algorithm A.
51 Crucial to see that the "sample" algorithm is correct is the fact that
52 when we sample "n" elements from a set of size "N" that the "t + 1"st
53 element is choosen with probability "(n - m)/(N - t)", when already "m"
54 elements have been choosen. We can immediately see that we will never
55 pick too many elements (as the probability is 0 as soon as "n == m"),
56 nor too few, as the probability will be 1 if we have "k" elements to
57 choose from the remaining "k" elements, for some "k". For the proof that
58 the sampling is unbiased, we refer to [3]. (Section 3.4.2, Exercise 3).
59
60 Algorithm B.
61 It is easy to see that the second algorithm returns the correct number
62 of elements. For a sample of size "n", the first "n" elements go into
63 the reservoir, and after that, the reservoir never grows or shrinks in
64 size; elements only get replaced. A detailed proof of the fairness of
65 the algorithm appears in [3]. (Section 3.4.2, Exercise 7).
66
67 LITERATURE
68 Both algorithms are discussed by Knuth [3] (Section 3.4.2). The first
69 algoritm, *Selection sampling technique*, was discovered by Fan, Muller
70 and Rezucha [1], and independently by Jones [2]. The second algorithm,
71 *Reservoir sampling*, is due to Waterman.
72
73 REFERENCES
74 [1] C. T. Fan, M. E. Muller and I. Rezucha, *J. Amer. Stat. Assoc.* 57
75 (1962), pp 387 - 402.
76
77 [2] T. G. Jones, *CACM* 5 (1962), pp 343.
78
79 [3] D. E. Knuth: *The Art of Computer Programming*, Volume 2, Third
80 edition. Reading: Addison-Wesley, 1997. ISBN: 0-201-89684-2.
81
82 DEVELOPMENT
83 The current sources of this module are found on github,
84 <git://github.com/Abigail/algorithms--numerical--sample.git>.
85
86 AUTHOR
87 This package was written by Abigail, [email protected].
88
89 COPYRIGHT and LICENSE
90 Copyright (C) 1998, 1999, 2009, Abigail.
91
92 Permission is hereby granted, free of charge, to any person obtaining a
93 copy of this software and associated documentation files (the
94 "Software"), to deal in the Software without restriction, including
95 without limitation the rights to use, copy, modify, merge, publish,
96 distribute, sublicense, and/or sell copies of the Software, and to
97 permit persons to whom the Software is furnished to do so, subject to
98 the following conditions:
99
100 The above copyright notice and this permission notice shall be included
101 in all copies or substantial portions of the Software.
102
103 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
104 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
105 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
106 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
107 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
108 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
109 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
110