Документация Engee

Выборка из совокупности

API выборки

Этот пакет содержит функции для выполнения выборки из заданной совокупности (с заменой или без нее).

sample([rng], a, [wv::AbstractWeights])

Выбирает один случайный элемент из a. Вероятности выборки пропорциональны весам в векторе wv, если он передан.

При необходимости первым аргументом можно указать генератор случайных чисел rng (по умолчанию Random.GLOBAL_RNG).

sample([rng], a, [wv::AbstractWeights], n::Integer; replace=true, ordered=false)

Выполняет случайную выборку (возможно, взвешенную) размера n из массива a с помощью полиалгоритма. Вероятности выборки пропорциональны весам, в векторе wv, если он передан. Аргумент replace определяет, выполняется ли выборка с заменой. Аргумент ordered определяет, следует ли получить упорядоченную выборку (также называемую последовательной; это такая выборка, в которой элементы следуют в том же порядке, что и в a).

При необходимости первым аргументом можно указать генератор случайных чисел rng (по умолчанию Random.GLOBAL_RNG).

sample([rng], a, [wv::AbstractWeights], dims::Dims; replace=true, ordered=false)

Выполняет случайную выборку (возможно, взвешенную) из массива a с указанием измерений dims выходного массива. Вероятности выборки пропорциональны весам в векторе wv, если он передан. Аргумент replace определяет, выполняется ли выборка с заменой. Аргумент ordered определяет, следует ли получить упорядоченную выборку (также называемую последовательной; это такая выборка, в которой элементы следуют в том же порядке, что и в a).

При необходимости первым аргументом можно указать генератор случайных чисел rng (по умолчанию Random.GLOBAL_RNG).

sample([rng], wv::AbstractWeights)

Выбирает одно случайное целое число из диапазона 1:length(wv) с вероятностями, пропорциональными весам в векторе wv.

При необходимости первым аргументом можно указать генератор случайных чисел rng (по умолчанию Random.GLOBAL_RNG).

sample!([rng], a, [wv::AbstractWeights], x; replace=true, ordered=false)

Выполняет случайную выборку length(x) элементов из массива a и сохраняет результат в x. Для выборки используется полиалгоритм. Вероятности выборки пропорциональны весам в векторе wv, если он передан. Аргумент replace определяет, выполняется ли выборка с заменой. Аргумент ordered определяет, следует ли получить упорядоченную выборку (также называемую последовательной; это такая выборка, в которой элементы следуют в том же порядке, что и в a).

При необходимости первым аргументом можно указать генератор случайных чисел rng (по умолчанию Random.GLOBAL_RNG).

Выходной массив a не должен быть тем же объектом, что и x или wv, и не должен размещаться в той же области памяти, иначе результат может быть неверным.

wsample([rng], [a], w)

Выполняет взвешенную случайную выборку размера 1 из a с вероятностями, пропорциональными весам в w. Если аргумент a отсутствует, выбирает случайный вес из w.

При необходимости первым аргументом можно указать генератор случайных чисел rng (по умолчанию Random.GLOBAL_RNG).

wsample([rng], [a], w, n::Integer; replace=true, ordered=false)

Выполняет взвешенную случайную выборку размера n из a с вероятностями, пропорциональными весам в w, если задан аргумент a; в противном случае выполняет случайную выборку размера n из весов в w. Аргумент replace определяет, выполняется ли выборка с заменой. Аргумент ordered определяет, следует ли получить упорядоченную выборку (также называемую последовательной; это такая выборка, в которой элементы следуют в том же порядке, что и в a).

При необходимости первым аргументом можно указать генератор случайных чисел rng (по умолчанию Random.GLOBAL_RNG).

wsample([rng], [a], w, dims::Dims; replace=true, ordered=false)

Выполняет взвешенную случайную выборку из a с вероятностями, пропорциональными весам в w, если задан аргумент a; в противном случае выполняет случайную выборку размера n из весов в w. Измерения выходного массива указываются в dims.

При необходимости первым аргументом можно указать генератор случайных чисел rng (по умолчанию Random.GLOBAL_RNG).

wsample!([rng], a, w, x; replace=true, ordered=false)

Выполняет взвешенную выборку из массива a и сохраняет результат в x. Вероятности выборки пропорциональны весам в w. Аргумент replace определяет, выполняется ли выборка с заменой. Аргумент ordered определяет, следует ли получить упорядоченную выборку (также называемую последовательной; это такая выборка, в которой элементы следуют в том же порядке, что и в a).

При необходимости первым аргументом можно указать генератор случайных чисел rng (по умолчанию Random.GLOBAL_RNG).

Алгоритмы

На внутреннем уровне в этом пакете реализовано множество алгоритмов, а методы sample (и sample!) объединяют их в полиалгоритм, который выбирает конкретный алгоритм в зависимости от входных данных.

Обратите внимание, что выбор алгоритма в sample выполняется на основе результатов тщательного тестирования (см. perf/sampling.jl и perf/wsampling.jl). В большинстве случаев скорость выполнения будет достаточно высокой. Однако если вам известно, что в вашей ситуации особенно хорошо подходит определенный алгоритм, вы можете вызвать реализующую его внутреннюю функцию напрямую, чтобы немного повысить эффективность.

Ниже приводится список алгоритмов, реализованных в пакете. Эти функции не экспортируются (однако их все же можно импортировать из StatsBase с помощью директивы using).

Нотация

  • a: исходный массив, представляющий совокупность

  • x: конечный массив

  • wv: весовой вектор (типа AbstractWeights) для взвешенной выборки

  • n: длина a

  • k: длина x. При выборке без замены k не должно быть больше n.

  • rng: необязательный генератор случайных чисел (по умолчанию Random.default_rng() начиная с версии Julia 1.3 и Random.GLOBAL_RNG в более ранних версиях)

Все приведенные ниже функции записывают результаты в массив x (предварительно выделенный в памяти) и возвращают x.

Алгоритмы выборки (не взвешенной)

direct_sample!([rng], a::AbstractArray, x::AbstractArray)

Прямая выборка: для каждого j в диапазоне 1:k случайно выбирает i из диапазона 1:n и задает x[j] = a[i] с n=length(a) и k=length(x).

Этот алгоритм использует k случайных чисел.

samplepair([rng], n)

Выбирает пару уникальных целых чисел от 1 до n без замены.

При необходимости первым аргументом можно указать генератор случайных чисел rng (по умолчанию Random.GLOBAL_RNG).

samplepair([rng], a)

Выбирает пару уникальных элементов из массива a без замены.

При необходимости первым аргументом можно указать генератор случайных чисел rng (по умолчанию Random.GLOBAL_RNG).

knuths_sample!([rng], a, x)

Алгоритм Кнута S для случайной выборки без замены.

Справочные материалы: D. Knuth. The Art of Computer Programming. Vol 2, 3.4.2, стр. 142.

Этот алгоритм использует length(a) случайных чисел. Дополнительного места в памяти не требуется. Подходит для случаев, когда объем памяти ограничен.

fisher_yates_sample!([rng], a::AbstractArray, x::AbstractArray)

Тасование Фишера-Йетса (с преждевременным завершением).

Псевдокод:

n = length(a)
k = length(x)

# Создаем массив индексов
inds = collect(1:n)

for i = 1:k
    # меняем элемент `i` местами с другим случайным элементом в inds[i:n]
    # задаем элемент `i` в `x`
end

Этот алгоритм использует k=length(x) случайных чисел. На внутреннем уровне он использует целочисленный массив длиной n=length(a) для хранения тасуемых индексов. Он выполняется существенно быстрее алгоритма Кнута, особенно когда n больше k. Его сложность составляет для инициализации плюс для случайного тасования.

self_avoid_sample!([rng], a::AbstractArray, x::AbstractArray)

Самоизбегающая выборка: выбранный индекс сохраняется в множестве. Если индекс уже был выбран ранее, выборка повторяется до тех пор, пока не будет выбран новый индекс.

Этот алгоритм использует примерно k=length(x) случайных чисел (или немного больше) и требует памяти для хранения множества выбранных индексов. Выполняется очень быстро при с n=length(a).

Однако если значение k велико и приближается к , частота отклонений резко возрастает, из-за чего производительность снижается.

seqsample_a!([rng], a::AbstractArray, x::AbstractArray)

Выборка случайных подпоследовательностей с использованием алгоритма A, описанного в следующей работе (стр. 714): Jeffrey Scott Vitter. Faster Methods for Random Sampling. Communications of the ACM, 27 (7), July 1984.

Этот алгоритм использует случайных чисел при n=length(a). Выходные данные упорядочены.

seqsample_c!([rng], a::AbstractArray, x::AbstractArray)

Выборка случайных подпоследовательностей с использованием алгоритма C, описанного в следующей работе (стр. 715): Jeffrey Scott Vitter. Faster Methods for Random Sampling. Communications of the ACM, 27 (7), July 1984.

Этот алгоритм использует случайных чисел при k=length(x). Выходные данные упорядочены.

seqsample_d!([rng], a::AbstractArray, x::AbstractArray)

Выборка случайных подпоследовательностей с использованием алгоритма D, описанного в следующей работе (стр. 716—​717): Jeffrey Scott Vitter. Faster Methods for Random Sampling. Communications of the ACM, 27 (7), July 1984.

Этот алгоритм использует случайных чисел при k=length(x). Выходные данные упорядочены.

Алгоритмы взвешенной выборки

direct_sample!([rng], a::AbstractArray, wv::AbstractWeights, x::AbstractArray)

Прямая выборка.

Каждая выборка производится путем сканирования весового вектора.

При k=length(x) и n=length(a) этот алгоритм:

  • использует k случайных чисел;

  • имеет временную сложность , так как для каждого сканирования весового вектора требуется ;

  • не требует дополнительного места в памяти.

alias_sample!([rng], a::AbstractArray, wv::AbstractWeights, x::AbstractArray)

Метод псевдонимов.

Строит таблицу псевдонимов и выполняет выборку из нее.

Справочные материалы: Walker, A. J. An Efficient Method for Generating Discrete Random Variables with General Distributions. ACM Transactions on Mathematical Software 3 (3): 253, 1977.

При k=length(x) и n=length(a) этот алгоритм имеет временную сложность , связанную с построением таблицы псевдонимов, и сложность , связанную с каждой выборкой. Он использует случайных чисел.

naive_wsample_norep!([rng], a::AbstractArray, wv::AbstractWeights, x::AbstractArray)

Примитивная реализация взвешенной выборки без замены.

При инициализации создается копия весового вектора, а затем при выборе соответствующего элемента его вес задается равным нулю.

При k=length(x) и n=length(a) этот алгоритм использует случайных чисел и имеет общую временную сложность .

efraimidis_a_wsample_norep!([rng], a::AbstractArray, wv::AbstractWeights, x::AbstractArray)

Взвешенная выборка без замены с использованием алгоритма Эфраимидиса-Спиракиса.

Справочные материалы: Efraimidis, P. S., Spirakis, P. G. Weighted random sampling with a reservoir. Information Processing Letters, 97 (5), 181—​185, 2006. doi:10.1016/j.ipl.2005.11.003.

При k=length(x) и n=length(a) этот алгоритм имеет временную сложность при выборке элементов. Он использует случайных чисел.

efraimidis_ares_wsample_norep!([rng], a::AbstractArray, wv::AbstractWeights, x::AbstractArray)

Реализация взвешенной выборки без замены с использованием алгоритма A-Res Эфраимидиса-Спиракиса.

Справочные материалы: Efraimidis, P. S., Spirakis, P. G. Weighted random sampling with a reservoir. Information Processing Letters, 97 (5), 181—​185, 2006. doi:10.1016/j.ipl.2005.11.003.

При k=length(x) и n=length(a) этот алгоритм имеет временную сложность при выборке элементов. Он использует случайных чисел.