| 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 |
|