Common Lisp Package: SIMPSAMP

README:

FUNCTION

Public

Undocumented

HASH-TABLE-SAMPLE-OF-HASH-TABLE (N HASH-TABLE)

LIST-SAMPLE-OF-HASH-TABLE-KEYS (N HASH-TABLE)

LIST-SAMPLE-OF-HASH-TABLE-PAIRS (N HASH-TABLE)

LIST-SAMPLE-OF-HASH-TABLE-VALUES (N HASH-TABLE)

LIST-SAMPLE-OF-ITERATOR (N SIZE NEXT-FN)

LIST-SAMPLE-OF-LIST (N LIST)

LIST-SAMPLE-OF-RANGE (N LOWER UPPER)

LIST-SAMPLE-OF-UNBOUNDED-ITERATOR (N NEXT-FN EXHAUSTED?-FN)

LIST-SAMPLE-OF-VECTOR (N VECTOR)

MAP-SAMPLE-OF-HASH-TABLE (FUNCTION N HASH-TABLE)

MAP-SAMPLE-OF-HASH-TABLE-KEYS (FUNCTION N HASH-TABLE)

MAP-SAMPLE-OF-HASH-TABLE-VALUES (FUNCTION N HASH-TABLE)

MAP-SAMPLE-OF-ITERATOR (FUNCTION N SIZE NEXT-FN)

MAP-SAMPLE-OF-LIST (FUNCTION N LIST)

MAP-SAMPLE-OF-RANGE (FUNCTION N LOWER UPPER)

MAP-SAMPLE-OF-UNBOUNDED-ITERATOR (FUNCTION N NEXT-FN EXHAUSTED?-FN)

MAP-SAMPLE-OF-VECTOR (FUNCTION N VECTOR)

TEST (&REST TEST-CORE-ARGS &KEY (STREAM *STANDARD-OUTPUT*) &ALLOW-OTHER-KEYS)

VECTOR-SAMPLE-OF-HASH-TABLE-KEYS (N HASH-TABLE)

VECTOR-SAMPLE-OF-HASH-TABLE-PAIRS (N HASH-TABLE)

VECTOR-SAMPLE-OF-HASH-TABLE-VALUES (N HASH-TABLE)

VECTOR-SAMPLE-OF-ITERATOR (N SIZE NEXT-FN)

VECTOR-SAMPLE-OF-LIST (N LIST)

VECTOR-SAMPLE-OF-RANGE (N LOWER UPPER)

VECTOR-SAMPLE-OF-UNBOUNDED-ITERATOR (N NEXT-FN EXHAUSTED?-FN)

VECTOR-SAMPLE-OF-VECTOR (N VECTOR)

Private

LIST->HASH-TABLE (LIST)

Given LIST, a list of 2-lists of the form (KEY VALUE), returns a hash table mapping each KEY to each corresponding VALUE.

LIST->ITERATOR-MV (LIST)

Returns two values: the length of LIST and a function that successively returns the lists of LIST as multiple values.

LIST->UNBOUNDED-ITERATOR (LIST)

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.

MAKE-TEST-SET-AS-LIST

Returns a sample set (as a list) of lists, each list consisting of two elements.

MAKE-TEST-SET-AS-RANGE

Returns three values to use as a range set: a lower bound, an upper bound, and a list of the values of the range.

MAKE-TEST-SET-AS-VECTOR

Returns the sample set from MAKE-TEST-SET-AS-LIST, but as a vector.

MEASURE-SELECTION-RATES (ITERATIONS SET-LOWER SET-UPPER SAMPLE-SIZE SAMPLE-FN)

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.

REPORT-SELECTION-RATES (LABEL EXPECTED-RATE ACTUAL-RATES VERBOSE-P STREAM)

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.

Undocumented

TEST-COMPUTED-SAMPLE (LABEL SAMPLE SAMPLE-TYPE INPUT-SET REQUESTED-SAMPLE-SIZE)

TEST-CORE (&KEY (ITERATIONS 100000) (SET-LOWER -100) (SET-UPPER 100) (SAMPLE-SIZE 15) (STREAM *STANDARD-OUTPUT*) (VERBOSE-P T))

TEST-OUTPUT

TEST-OUTPUT-AS-HASH-TABLE (SAMPLE-SIZE)

TEST-OUTPUT-AS-ITERATION (SAMPLE-SIZE)

TEST-OUTPUT-AS-LIST (SAMPLE-SIZE)

TEST-OUTPUT-AS-MAPPING (SAMPLE-SIZE)

TEST-OUTPUT-AS-VECTOR (SAMPLE-SIZE)

TEST-OUTPUT-METHODS (SAMPLE-SIZE)

MACRO

Public

DO-SAMPLE-OF-ITERATOR-EXPR ((VARS N-FORM SIZE-FORM NEXT-FORM &KEY (EFFECTIVE-N-VAR NIL EFFECTIVE-N-VAR-P) (INITIAL-FORM NIL INITIAL-FORM-P) (RESULT-FORM NIL RESULT-FORM-P)) &BODY BODY)

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.

VECTOR-SAMPLE-OF-UNBOUNDED-ITERATOR-EXPR (N-FORM NEXT-FORM EXHAUSTED?-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.

Undocumented

DO-SAMPLE-OF-HASH-TABLE ((KEY-VAR VALUE-VAR N-FORM HASH-TABLE-FORM &REST KW-ARGS &KEY &ALLOW-OTHER-KEYS) &BODY BODY)

DO-SAMPLE-OF-ITERATOR ((VARS N-FORM SIZE-FORM NEXT-FN-FORM &REST KW-ARGS &KEY &ALLOW-OTHER-KEYS) &BODY BODY)

DO-SAMPLE-OF-LIST ((VAR N-FORM LIST-FORM &REST KW-ARGS &KEY &ALLOW-OTHER-KEYS) &BODY BODY)

DO-SAMPLE-OF-RANGE ((VAR N-FORM LOWER-FORM UPPER-FORM &REST KW-ARGS &KEY &ALLOW-OTHER-KEYS) &BODY BODY)

DO-SAMPLE-OF-UNBOUNDED-ITERATOR ((VAR N-FORM NEXT-FN-FORM EXHAUSTED?-FN-FORM &KEY (EFFECTIVE-N-VAR NIL EFFECTIVE-N-VAR-P) (INITIAL-FORM NIL INITIAL-FORM-P) (RESULT-FORM NIL RESULT-FORM-P)) &BODY BODY)

DO-SAMPLE-OF-VECTOR ((VAR N-FORM VECTOR-FORM &REST KW-ARGS &KEY &ALLOW-OTHER-KEYS) &BODY BODY)

Private

TEST-ACCUMULATED-SAMPLE ((LABEL ACCUMULATE INPUT-SET-FORM REQUESTED-SAMPLE-SIZE-FORM) &BODY BODY)

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.

TEST-DO-SAMPLE ((LABEL ACCUMULATE INITIAL-FORM RESULT-FORM INITIAL-SET-FORM REQUESTED-SAMPLE-SIZE-FORM) &BODY BODY)

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.

TEST-LIST-SAMPLE ((LABEL INPUT-SET-FORM REQUESTED-SAMPLE-SIZE-FORM) &BODY BODY)

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.

TEST-VECTOR-SAMPLE ((LABEL INPUT-SET-FORM REQUESTED-SAMPLE-SIZE-FORM) &BODY BODY)

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.

WITH-HASH-TABLE-ACCUMULATOR ((SET-TEST/SIZE ACCUMULATE) &BODY BODY)

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.

WITH-LIST-ACCUMULATOR ((ACCUMULATE) &BODY BODY)

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.

WITH-LIST-ITERATOR ((NEXT SIZE EXHAUSTED? LIST-FORM) &BODY BODY)

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.

WITH-RANGE-ITERATOR ((NEXT SIZE EXHAUSTED? LOWER-FORM UPPER-FORM) &BODY BODY)

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.

WITH-VECTOR-ACCUMULATOR ((SET-SIZE/ELEMENT-TYPE ACCUMULATE) &BODY BODY)

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

WITH-VECTOR-ITERATOR ((NEXT SIZE EXHAUSTED? VECTOR-FORM) &BODY BODY)

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.

Undocumented

DEFINE-TYPICAL-SAMPLE-METHODS (SPECIALIZED-FOR-CLASS-NAME GENERIC-SAMPLE-FUNCTION-NAME LIST-SAMPLE-FUNCTION-NAME VECTOR-SAMPLE-FUNCTION-NAME MAP-SAMPLE-FUNCTION-NAME)

GENERIC-FUNCTION

Public

LIST-SAMPLE (N SET)

Like SAMPLE, but the result is a LIST.

MAP-SAMPLE (FUNCTION N SET)

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.

SAMPLE (N SET)

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.

VECTOR-SAMPLE (N SET)

Like SAMPLE, but the result is a VECTOR.

VARIABLE

Private

Undocumented

*TEST-OUTPUT-LOWER-BOUND*

*TEST-OUTPUT-UPPER-BOUND*