This is the simpsamp Reference Manual, version 0.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sun Dec 08 19:35:05 2024 GMT+0.
simpsamp/simpsamp.asd
simpsamp/core.lisp
simpsamp/input.lisp
simpsamp/output.lisp
simpsamp/out-do.lisp
simpsamp/out-map.lisp
simpsamp/out-list.lisp
simpsamp/out-vector.lisp
simpsamp/out-hash-table.lisp
simpsamp/unbounded-iterator.lisp
simpsamp/generic-functions.lisp
simpsamp/test.lisp
simpsamp/test-core.lisp
simpsamp/test-outputs.lisp
simpsamp/package.lisp
The main system appears first, followed by any subsystem dependency.
simpsamp
Fast algorithms for simple random sampling from sets, without replacement.
J.P. Larocque
J.P. Larocque
ISC-style permissive
0.1
jpl-util
(system)., at least version "0.2"
core.lisp
(file).
input.lisp
(file).
output.lisp
(file).
out-do.lisp
(file).
out-map.lisp
(file).
out-list.lisp
(file).
out-vector.lisp
(file).
out-hash-table.lisp
(file).
unbounded-iterator.lisp
(file).
generic-functions.lisp
(file).
test.lisp
(file).
test-core.lisp
(file).
test-outputs.lisp
(file).
package.lisp
(file).
Files are sorted by type and then listed depth-first from the systems components trees.
simpsamp/simpsamp.asd
simpsamp/core.lisp
simpsamp/input.lisp
simpsamp/output.lisp
simpsamp/out-do.lisp
simpsamp/out-map.lisp
simpsamp/out-list.lisp
simpsamp/out-vector.lisp
simpsamp/out-hash-table.lisp
simpsamp/unbounded-iterator.lisp
simpsamp/generic-functions.lisp
simpsamp/test.lisp
simpsamp/test-core.lisp
simpsamp/test-outputs.lisp
simpsamp/package.lisp
simpsamp/core.lisp
package.lisp
(file).
simpsamp
(system).
do-sample-of-iterator-expr
(macro).
vector-sample-of-unbounded-iterator-expr
(macro).
simpsamp/input.lisp
package.lisp
(file).
simpsamp
(system).
with-list-iterator
(macro).
with-range-iterator
(macro).
with-vector-iterator
(macro).
simpsamp/output.lisp
package.lisp
(file).
simpsamp
(system).
with-hash-table-accumulator
(macro).
with-list-accumulator
(macro).
with-vector-accumulator
(macro).
simpsamp/out-do.lisp
core.lisp
(file).
input.lisp
(file).
unbounded-iterator.lisp
(file).
package.lisp
(file).
simpsamp
(system).
do-sample-of-hash-table
(macro).
do-sample-of-iterator
(macro).
do-sample-of-list
(macro).
do-sample-of-range
(macro).
do-sample-of-unbounded-iterator
(macro).
do-sample-of-vector
(macro).
simpsamp/out-map.lisp
out-do.lisp
(file).
package.lisp
(file).
simpsamp
(system).
map-sample-of-hash-table
(function).
map-sample-of-hash-table-keys
(function).
map-sample-of-hash-table-values
(function).
map-sample-of-iterator
(function).
map-sample-of-list
(function).
map-sample-of-range
(function).
map-sample-of-unbounded-iterator
(function).
map-sample-of-vector
(function).
simpsamp/out-list.lisp
out-do.lisp
(file).
output.lisp
(file).
unbounded-iterator.lisp
(file).
package.lisp
(file).
simpsamp
(system).
list-sample-of-hash-table-keys
(function).
list-sample-of-hash-table-pairs
(function).
list-sample-of-hash-table-values
(function).
list-sample-of-iterator
(function).
list-sample-of-list
(function).
list-sample-of-range
(function).
list-sample-of-unbounded-iterator
(function).
list-sample-of-vector
(function).
simpsamp/out-vector.lisp
core.lisp
(file).
input.lisp
(file).
output.lisp
(file).
out-do.lisp
(file).
package.lisp
(file).
simpsamp
(system).
vector-sample-of-hash-table-keys
(function).
vector-sample-of-hash-table-pairs
(function).
vector-sample-of-hash-table-values
(function).
vector-sample-of-iterator
(function).
vector-sample-of-list
(function).
vector-sample-of-range
(function).
vector-sample-of-vector
(function).
simpsamp/out-hash-table.lisp
output.lisp
(file).
out-do.lisp
(file).
package.lisp
(file).
simpsamp
(system).
hash-table-sample-of-hash-table
(function).
simpsamp/unbounded-iterator.lisp
core.lisp
(file).
package.lisp
(file).
simpsamp
(system).
vector-sample-of-unbounded-iterator
(function).
simpsamp/generic-functions.lisp
out-map.lisp
(file).
out-list.lisp
(file).
out-vector.lisp
(file).
package.lisp
(file).
simpsamp
(system).
list-sample
(generic function).
map-sample
(generic function).
sample
(generic function).
vector-sample
(generic function).
define-typical-sample-methods
(macro).
simpsamp/test.lisp
test-core.lisp
(file).
test-outputs.lisp
(file).
package.lisp
(file).
simpsamp
(system).
test
(function).
simpsamp/test-core.lisp
core.lisp
(file).
input.lisp
(file).
simpsamp
(system).
measure-selection-rates
(function).
report-selection-rates
(function).
test-core
(function).
simpsamp/test-outputs.lisp
output.lisp
(file).
out-do.lisp
(file).
out-map.lisp
(file).
out-list.lisp
(file).
out-vector.lisp
(file).
out-hash-table.lisp
(file).
unbounded-iterator.lisp
(file).
package.lisp
(file).
simpsamp
(system).
*test-output-lower-bound*
(special variable).
*test-output-upper-bound*
(special variable).
list->hash-table
(function).
list->iterator-mv
(function).
list->unbounded-iterator
(function).
make-test-set-as-list
(function).
make-test-set-as-range
(function).
make-test-set-as-vector
(function).
test-accumulated-sample
(macro).
test-computed-sample
(function).
test-do-sample
(macro).
test-list-sample
(macro).
test-output
(function).
test-output-as-hash-table
(function).
test-output-as-iteration
(function).
test-output-as-list
(function).
test-output-as-mapping
(function).
test-output-as-vector
(function).
test-output-methods
(function).
test-vector-sample
(macro).
Packages are listed by definition order.
simpsamp
common-lisp
.
do-sample-of-hash-table
(macro).
do-sample-of-iterator
(macro).
do-sample-of-iterator-expr
(macro).
do-sample-of-list
(macro).
do-sample-of-range
(macro).
do-sample-of-unbounded-iterator
(macro).
do-sample-of-vector
(macro).
hash-table-sample-of-hash-table
(function).
list-sample
(generic function).
list-sample-of-hash-table-keys
(function).
list-sample-of-hash-table-pairs
(function).
list-sample-of-hash-table-values
(function).
list-sample-of-iterator
(function).
list-sample-of-list
(function).
list-sample-of-range
(function).
list-sample-of-unbounded-iterator
(function).
list-sample-of-vector
(function).
map-sample
(generic function).
map-sample-of-hash-table
(function).
map-sample-of-hash-table-keys
(function).
map-sample-of-hash-table-values
(function).
map-sample-of-iterator
(function).
map-sample-of-list
(function).
map-sample-of-range
(function).
map-sample-of-unbounded-iterator
(function).
map-sample-of-vector
(function).
sample
(generic function).
test
(function).
vector-sample
(generic function).
vector-sample-of-hash-table-keys
(function).
vector-sample-of-hash-table-pairs
(function).
vector-sample-of-hash-table-values
(function).
vector-sample-of-iterator
(function).
vector-sample-of-list
(function).
vector-sample-of-range
(function).
vector-sample-of-unbounded-iterator
(function).
vector-sample-of-unbounded-iterator-expr
(macro).
vector-sample-of-vector
(function).
*test-output-lower-bound*
(special variable).
*test-output-upper-bound*
(special variable).
define-typical-sample-methods
(macro).
list->hash-table
(function).
list->iterator-mv
(function).
list->unbounded-iterator
(function).
make-test-set-as-list
(function).
make-test-set-as-range
(function).
make-test-set-as-vector
(function).
measure-selection-rates
(function).
report-selection-rates
(function).
test-accumulated-sample
(macro).
test-computed-sample
(function).
test-core
(function).
test-do-sample
(macro).
test-list-sample
(macro).
test-output
(function).
test-output-as-hash-table
(function).
test-output-as-iteration
(function).
test-output-as-list
(function).
test-output-as-mapping
(function).
test-output-as-vector
(function).
test-output-methods
(function).
test-vector-sample
(macro).
with-hash-table-accumulator
(macro).
with-list-accumulator
(macro).
with-list-iterator
(macro).
with-range-iterator
(macro).
with-vector-accumulator
(macro).
with-vector-iterator
(macro).
Definitions are sorted by export status, category, package, and then by lexicographic order.
Iterates over a simple random sample of N-FORM elements, without
replacement, from a set expressed by SIZE-FORM and NEXT-FORM.
N-FORM is evaluated once, before any other arguments are evaluated.
If the value of N-FORM is larger than the size of the input set, then
the resulting sample will just contain all the elements of the
set–that is, the value of N-FORM is automatically lowered to the size
of the input set when necessary.
SIZE-FORM is then evaluated once to produce the number of elements in
the set.
When INITIAL-FORM is given, it is evaluated before iteration begins.
When RESULT-FORM is given, it is evaluated after iteration ends, and
its resulting values become the result of the iteration form; if
RESULT-FORM is not given, the result is NIL. If EFFECTIVE-N-VAR is
given, it is bound with the effective number of elements to
process (the result of N-FORM limited by the actual size of the input
set) for the evaluation of INITIAL-FORM, NEXT-FORM, RESULT-FORM, and
BODY.
NEXT-FORM is evaluated to produce the next available element,
advancing through the set. NEXT-FORM may produce multiple values;
these values taken together as a tuple constitute a single element of
the set. NEXT-FORM will never be evaluated more times than the value
of SIZE-FORM.
For each element selected for the random sample, BODY is evaluated
with the symbol specified by VARS bound to a list of each value of the
element (the values yielded by NEXT-FORM). Alternatively, VARS may be
a list of symbols, each of which is bound to each successive value of
the element, as if by MULTIPLE-VALUE-BIND. In either case, the
bindings may be shared between different iterations, or the binding
may be fresh each time.
An implicit block named NIL is established around the loop. RETURN may be used to terminate the loop prematurely, overriding the default resulting values of the iteration form (controlled by RESULT-FORM).
The order in which BODY is evaluated on the sampled elements is not assured to be random. The only thing that is random is which selection is made of all the possible subsets of the input set with the size expressed by N-FORM.
Evaluates to a simple random sample of size N-FORM, without
replacement, from a set of unknown size expressed by NEXT-FORM and
EXHAUSTED?-FORM. The resulting sample is expressed as a vector.
N-FORM is evaluated once, before any other arguments are evaluated.
If the value of N-FORM is larger than the size of the input set, then
the resulting sample will just contain all the elements of the
set–that is, the value of N-FORM is automatically lowered to the size
of the input set when necessary. The value of N-FORM (before being
limited by the size of the input set) must be within the host
implementation’s ARRAY-DIMENSION-LIMIT.
NEXT-FORM is evaluated to produce the next available element,
advancing through the input set. (Its first return value is used as
the element, or NIL if NEXT-FORM produced no values.) EXHAUSTED?-FORM
is evaluated to produce a generalized boolean indicating whether the
input set has been exhausted. NEXT-FORM will never be evaluated
unless EXHAUSTED?-FORM has been evaluated since the last evaluation of
NEXT-FORM, and the result was false.
The order of the returned elements is not assured to be random. The only thing that is random is which selection is made of all the possible subsets of the input set with the size expressed by N-FORM.
Like SAMPLE, but the result is a LIST.
Like SAMPLE, but applies FUNCTION to each element
of the resulting selection.
When SET is a mapping type (e.g. a HASH-TABLE), FUNCTION is applied with two arguments: the key and the value.
Returns a simple random sample of size N, without
replacement, from SET. The output will be of type SEQUENCE. (Whether
a LIST is returned or a VECTOR depends on which is most efficient for
the type of SET.)
If N is larger than the size of SET, then the resulting sample will
just contain all the elements of SET–that is, N is automatically
lowered to the size of SET when necessary.
When SET is a mapping type (e.g. a HASH-TABLE), the returned elements
will be CONSes of the form (KEY . VALUE).
The order of the returned elements is not assured to be random. The only thing that is random is which selection is made of all the possible subsets of SET of size N.
Like SAMPLE, but the result is a VECTOR.
Evaluates BODY, which accumulates the elements of a sample taken
from a set. After evaluating BODY, tests the sample against the input
set and the requested sample size. If there is an error in the
resulting sample, an error is signalled. LABEL is included in any
error messages.
ACCUMULATE is defined with MACROLET for the evaluation of BODY.
(ACCUMULATE ELEMENT) is used to accumulate each ELEMENT of the sample
that is taken.
INPUT-SET-FORM is evaluated to produce the input set (or an equivalent
copy), as a SEQUENCE.
REQUESTED-SAMPLE-SIZE-FORM is evaluated to produce the requested size
of the sample to take.
Note that the input set and requested sample size are not passed to anything within BODY, but must be equivalent to the corresponding arguments to the function or macro form used in BODY to produce the sample.
Evaluates BODY, which iterates over the elements of a sample taken
from a set. After evaluating BODY, tests the sample against the input
set and the requested sample size. If there is an error in the
resulting sample, an error is signalled. LABEL is included in any
error messages.
ACCUMULATE is defined with MACROLET for the evaluation of BODY. The
result of BODY must be the result a DO-SAMPLE-OF-* macro form that
includes at least the expression (ACCUMULATE ELEMENT) in its body
(where ELEMENT is the variable naming the current element in the loop
over the resulting sample). BODY should consist solely of the
DO-SAMPLE-OF-* macro form, and the body of that macro form should
consist solely of (ACCUMULATE ELEMENT).
INITIAL-FORM is defined with MACROLET for the evaluation of BODY.
(INITIAL-FORM) must be the :INITIAL-FORM argument to the
DO-SAMPLE-OF-* macro form.
RESULT-FORM is defined with MACROLET for the evaluation of BODY.
(RESULT-FORM) must be the :RESULT-FORM argument to the DO-SAMPLE-OF-*
macro form.
INPUT-SET-FORM is evaluated to produce the input set (or an equivalent
copy), as a SEQUENCE.
REQUESTED-SAMPLE-SIZE-FORM is evaluated to produce the requested size
of the sample to take.
Note that the input set and requested sample size are not passed to anything within BODY, but must be equivalent to the corresponding arguments to the DO-SAMPLE-OF-* macro form used in BODY to produce the sample.
Evaluates BODY, which takes a sample from a set, evaluating to the
sample (as a LIST). The sample is tested against the input set and
the requested sample size. If there is an error in the resulting
sample, an error is signalled. LABEL is included in any error
messages.
INPUT-SET-FORM and REQUESTED-SAMPLE-SIZE-FORM have the same meaning as they do in the TEST-ACCUMULATED-SAMPLE macro.
Evaluates BODY, which takes a sample from a set, evaluating to the
sample (as a VECTOR). The sample is tested against the input set and
the requested sample size. If there is an error in the resulting
sample, an error is signalled. LABEL is included in any error
messages.
INPUT-SET-FORM and REQUESTED-SAMPLE-SIZE-FORM have the same meaning as they do in the TEST-ACCUMULATED-SAMPLE macro.
Evaluates BODY, accumulating keys and values to a hash-table,
resulting in the hash-table.
SET-TEST/SIZE is defined with MACROLET. (SET-TEST/SIZE TEST SIZE)
must be evaluated once, before accumulation begins. TEST must be an
acceptable hash-table test function for MAKE-HASH-TABLE. SIZE must be
a non-negative integer indicating the expected final size of the
hash-table (the number of times ACCUMULATE is evaluated with a unique
KEY), which need not be accurate, or NIL to make no guess as to the
final size.
ACCUMULATE is defined with MACROLET. Each time (ACCUMULATE KEY VALUE) is evaluated, KEY and TABLE are added as an entry to the hash-table, replacing any previous entry with the same KEY.
Evaluates BODY, accumulating elements to a list, resulting in the list. The order of the elements of the resulting list is undefined.
ACCUMULATE is defined with MACROLET. Each time (ACCUMULATE ELEMENT) is evaluated, ELEMENT is accumulated to the list.
Evaluates BODY with an iterator on a list.
LIST-FORM is evaluated once to produce the list to iterate upon. The
resulting list is never modified (unless from within BODY), the
consequences of which are undefined).
NEXT is defined with MACROLET. Each evaluation of (NEXT) yields the
next successive element of the list.
SIZE is defined with MACROLET. Each evaluation of (SIZE) yields the
length of the list. The length may or may not be calculated upon each
evaluation; it may (but need not be) be memoized.
EXHAUSTED? is defined with MACROLET?. Each evaluation of (EXHAUSTED?)
yields a generalized boolean indicating whether the list has been
exhausted by evaluations of NEXT.
The effect of calling NEXT more times than the length of the list is undefined.
Evaluates BODY with an iterator on a range of integers.
LOWER-FORM and UPPER-FORM are evaluated once to produce the range of
integers, [LOWER,UPPER), to iterate upon.
NEXT is defined with MACROLET. Each evaluation of (NEXT) yields the
next successive element of the range.
SIZE is defined with MACROLET. Each evaluation of (SIZE) yields the
length of the range.
EXHAUSTED? is defined with MACROLET?. Each evaluation of (EXHAUSTED?)
yields a generalized boolean indicating whether the range has been
exhausted by evaluations of NEXT.
The effect of calling NEXT more times than the length of the range is undefined.
Evaluates BODY, accumulating elements to a vector, resulting in the vector. The order of the elements of the resulting vector is undefined.
SET-SIZE/ELEMENT-TYPE is defined with
MACROLET. (SET-SIZE/ELEMENT-TYPE SIZE ELEMENT-TYPE) must be evaluated
once, before accumulation begins. SIZE dictates the size of the
resulting vector. ELEMENT-TYPE is a designator for the type of
elements to be accumulated. The result of accumulating an element not
of type ELEMENT-TYPE is undefined.
ACCUMULATE is defined with MACROLET. Each time (ACCUMULATE ELEMENT) is evaluated, ELEMENT is accumulated to the vector. It must be evaluated exactly the number of times as given to the SET-SIZE/ELEMENT-TYPE form before control leaves BODY in the normal manner. (It’s acceptable for control to leave BODY due to non-local exits, such as GO, THROW, or a signalled condition.)
Evaluates BODY with an iterator on a vector.
VECTOR-FORM is evaluated once to produce the vector to iterate upon.
The resulting vector is never modified (unless from within BODY, the
consequences of which are undefined).
NEXT is defined with MACROLET. Each evaluation of (NEXT) yields the
next successive element of the vector.
SIZE is defined with MACROLET. Each evaluation of (SIZE) yields the
length of the vector.
EXHAUSTED? is defined with MACROLET?. Each evaluation of (EXHAUSTED?)
yields a generalized boolean indicating whether the vector has been
exhausted by evaluations of NEXT.
The effect of calling NEXT more times than the length of the vector is undefined.
Given LIST, a list of 2-lists of the form (KEY VALUE), returns a hash table mapping each KEY to each corresponding VALUE.
Returns two values: the length of LIST and a function that successively returns the lists of LIST as multiple values.
Returns two values: a function that successively returns the values of LIST, and a function that returns a generalized boolean indicating whether the first function has exhausted LIST.
Returns a sample set (as a list) of lists, each list consisting of two elements.
Returns three values to use as a range set: a lower bound, an upper bound, and a list of the values of the range.
Returns the sample set from MAKE-TEST-SET-AS-LIST, but as a vector.
Given the set of integers [SET-LOWER,SET-UPPER), measures the
selection rates of each element when repeatedly given to SAMPLE-FN,
which takes a simple random sample, without replacement, of the set.
SAMPLE-SIZE is the size of each sample.
The function SAMPLE-FN is called ITERATIONS times. Its arguments are:
SAMPLE-SIZE
The requested size of the sample to take of the set.
SET-SIZE
The size of the set.
SET-NEXT
A function of no arguments returning the next element of the set.
SET-EXHAUSTED?
A function of no arguments returning a generalized boolean
indicating whether the set has been exhausted.
VISIT-SAMPLE-ELEMENT
A function which must be called once for every element of the
chosen sample.
Returns two values: the expected rate of selection for all elements,
based on the set size and sample size, and a vector of the actual
measured rate of selection for each element of the set; each element
of the vector corresponds to [SET-LOWER,SET-UPPER) (in the same
order).
The more any actual rate varies from the expected rate, the more likely there was some bias or error in the sample taken by SAMPLE-FN. A lower number of iterations can also cause this problem; 1,000,000 is a good number of iterations to use to get a clear reading.
Reports EXPECTED-RATE and some trivial statistics on ACTUAL-RATES,
as returned by MEASURE-SELECTION-RATES. Prints the analysis to
STREAM.
When VERBOSE-P is true, prints each element of ACTUAL-RATES, along with its error from EXPECTED-RATE and a graph of its error.
Jump to: | D F G H L M R S T V W |
---|
Jump to: | D F G H L M R S T V W |
---|
Jump to: | *
S |
---|
Jump to: | *
S |
---|
Jump to: | C F G I O P S T U |
---|
Jump to: | C F G I O P S T U |
---|