Рубрики

Отбор проб из водохранилища

Математика, Случайный, Статьи

Выборка из резервуара — это семейство рандомизированных алгоритмов для случайного выбора k выборок из списка из n элементов, где n — либо очень большое, либо неизвестное число. Обычно n достаточно велико, чтобы список не помещался в основную память. Например, список поисковых запросов в Google и Facebook.

Итак, нам дан большой массив (или поток) чисел (для упрощения), и нам нужно написать эффективную функцию для случайного выбора k чисел, где 1 <= k <= n . Пусть входной массив будет stream [].

Простое решение — создать массив резервуара [] максимального размера k . Один за другим случайным образом выбирают элемент из потока [0..n-1] . Если выбранный элемент ранее не был выбран, поместите его в резервуар [] . Чтобы проверить, выбран ли предмет ранее или нет, нам нужно найти предмет в резервуаре [] . Временная сложность этого алгоритма будет O (k ^ 2) . Это может быть дорогостоящим, если k большое. Кроме того, это неэффективно, если ввод осуществляется в форме потока.

Это может быть решено за O (n) время . Решение также хорошо подходит для ввода в виде потока. Идея похожа на этот пост. Ниже приведены шаги.

1) Создайте массив резервуаров [0..k-1] и скопируйте в него первые k элементов потока [] .
2) Теперь один за другим рассмотрим все элементы от (k + 1) -го до n- го.
… А ) Генерация случайного числа от 0 до i, где i — индекс текущего элемента в потоке [] . Пусть сгенерированное случайное число равно j .
… Б) Если j находится в диапазоне от 0 до k-1 , заменить резервуар [j] на arr [i]

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// Эффективная программа для случайного выбора
// k элементов из потока элементов
#include <bits/stdc++.h>
#include <time.h> 

using namespace std; 

  
// Вспомогательная функция для печати массива

void printArray(int stream[], int n) 

{ 

    for (int i = 0; i < n; i++) 

        cout << stream[i] << " "; 

    cout << endl;

} 

  
// Функция для случайного выбора
// k элементов из потока [0..n-1].

void selectKItems(int stream[], int n, int k) 

{ 

    int i; // индекс для элементов в потоке []

  

    // резервуар [] - выходной массив. Initialize

    // это с первыми k элементами из stream []

    int reservoir[k]; 

    for (i = 0; i < k; i++) 

        reservoir[i] = stream[i]; 

  

    // Используем другое начальное значение, чтобы мы не получили

    // один и тот же результат каждый раз, когда мы запускаем эту программу

    srand(time(NULL)); 

  

    // Переходим от (k + 1) -го элемента к n-му элементу

    for (; i < n; i++) 

    { 

        // Выбрать случайный индекс от 0 до i.

        int j = rand() % (i + 1); 

  

        // Если случайно выбранный индекс меньше k,

        // затем заменить элемент, присутствующий в индексе

        // с новым элементом из потока

        if (j < k) 

        reservoir[j] = stream[i]; 

    } 

  

    cout << "Following are k randomly selected items \n"; 

    printArray(reservoir, k); 

} 

  
// Код драйвера

int main() 

{ 

    int stream[] = {1, 2, 3, 4, 5, 6, 

                    7, 8, 9, 10, 11, 12}; 

    int n = sizeof(stream)/sizeof(stream[0]); 

    int k = 5; 

    selectKItems(stream, n, k); 

    return 0; 

} 

  
// Это код, предоставленный rathbhupendra

С

// Эффективная программа для случайного выбора k элементов из потока элементов

  
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

  
// Вспомогательная функция для печати массива

void printArray(int stream[], int n)

{

    for (int i = 0; i < n; i++)

        printf("%d ", stream[i]);

    printf("\n");

}

  
// Функция для случайного выбора k элементов из потока [0..n-1].

void selectKItems(int stream[], int n, int k)

{

    int i;  // индекс для элементов в потоке []

  

    // резервуар [] - выходной массив. Инициализируйте это с

    // первые k элементов из потока []

    int reservoir[k];

    for (i = 0; i < k; i++)

        reservoir[i] = stream[i];

  

    // Используем другое начальное значение, чтобы мы не получили

    // один и тот же результат каждый раз, когда мы запускаем эту программу

    srand(time(NULL));

  

    // Переходим от (k + 1) -го элемента к n-му элементу

    for (; i < n; i++)

    {

        // Выбрать случайный индекс от 0 до i.

        int j = rand() % (i+1);

  

        // Если случайно выбранный индекс меньше k, тогда заменить

        // элемент присутствует в индексе с новым элементом из потока

        if (j < k)

          reservoir[j] = stream[i];

    }

  

    printf("Following are k randomly selected items \n");

    printArray(reservoir, k);

}

  
// Программа драйвера для проверки вышеуказанной функции.

int main()

{

    int stream[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

    int n = sizeof(stream)/sizeof(stream[0]);

    int k = 5;

    selectKItems(stream, n, k);

    return 0;

}

Джава

// Эффективная Java-программа для случайного выбора
// выбираем k предметов из потока предметов

import java.util.Arrays;

import java.util.Random;

public class ReservoirSampling 

{

    // Функция для случайного выбора k элементов из потока [0..n-1].

    static void selectKItems(int stream[], int n, int k)

    {

        int i;   // индекс для элементов в потоке []

          

        // резервуар [] - выходной массив. Инициализируйте это с

        // первые k элементов из потока []

        int reservoir[] = new int[k];

        for (i = 0; i < k; i++)

            reservoir[i] = stream[i];

          

        Random r = new Random();

          

        // Переходим от (k + 1) -го элемента к n-му элементу

        for (; i < n; i++)

        {

            // Выбрать случайный индекс от 0 до i.

            int j = r.nextInt(i + 1);

              

            // Если случайно выбранный индекс меньше k,

            // затем заменить элемент, присутствующий в индексе

            // с новым элементом из потока

            if(j < k)

                reservoir[j] = stream[i];            

        }

          

        System.out.println("Following are k randomly selected items");

        System.out.println(Arrays.toString(reservoir));

    }

      

    // Программа для проверки вышеописанного метода

    public static void main(String[] args) {

        int stream[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

        int n = stream.length;

        int k = 5;

        selectKItems(stream, n, k);

    }

}
// Этот код предоставлен Sumit Ghosh

python3

# Эффективная программа на Python3
# для случайного выбора k элементов
# из потока предметов

import random

# Полезная функция
# распечатать массив

def printArray(stream,n):

    for i in range(n):

        print(stream[i],end=" ");

    print();

  
# Функция для случайного выбора
# k элементов из потока [0..n-1].

def selectKItems(stream, n, k):

        i=0; 

        # индекс для элементов

        # в потоке []

          

        # резервуар [] является выходным

        # массив. Инициализируйте это с

        # первые k элементов из потока []

        reservoir = [0]*k;

        for i in range(k):

            reservoir[i] = stream[i];

          

        # Итерировать с (k + 1) -го

        # элемент в n-й элемент

        while(i < n):

            # Выберите случайный индекс

            # от 0 до i.

            j = random.randrange(i+1);

              

            # Если случайно выбран

            # индекс меньше, чем k,

            # затем заменить элемент

            # присутствует в индексе

            # с новым элементом из потока

            if(j < k):

                reservoir[j] = stream[i];

            i+=1;

          

        print("Following are k randomly selected items");

        printArray(reservoir, k);

      
Код водителя

  

if __name__ == "__main__":

    stream = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];

    n = len(stream);

    k = 5;

    selectKItems(stream, n, k);

  
# Этот код предоставлен mits

C #

// Эффективная программа на C # для случайного выбора
// выбираем k предметов из потока предметов

using System;

using System.Collections;

  

public class ReservoirSampling 

{

    // Функция для случайного выбора k

    // элементы из потока [0..n-1].

    static void selectKItems(int []stream, 

                            int n, int k)

    {

        // индекс для элементов в потоке []

        int i; 

          

        // резервуар [] - выходной массив.

        // Инициализируем это с первым k

        // элементы из потока []

        int[] reservoir = new int[k];

        for (i = 0; i < k; i++)

            reservoir[i] = stream[i];

          

        Random r = new Random();

          

        // Итерация из (k + 1) -го

        // элемент в n-й элемент

        for (; i < n; i++)

        {

            // Выбрать случайный индекс от 0 до i.

            int j = r.Next(i + 1);

              

            // Если случайно выбранный индекс

            // меньше k, затем заменить

            // элемент, присутствующий в индексе

            // с новым элементом из потока

            if(j < k)

                reservoir[j] = stream[i];         

        }

          

        Console.WriteLine("Following are k " +

                    "randomly selected items");

        for (i = 0; i < k; i++)

        Console.Write(reservoir[i]+" ");

    }

      

    // Код драйвера

    static void Main()

    {

        int []stream = {1, 2, 3, 4, 5, 6, 7,

                        8, 9, 10, 11, 12};

        int n = stream.Length;

        int k = 5;

        selectKItems(stream, n, k);

    }

}

  
// Этот код предоставлен mits

PHP

<?php
// Эффективная программа PHP
// случайным образом выбрать k элементов
// из потока предметов

  
// функция полезности
// напечатать массив

function printArray($stream,$n)

{

    for ($i = 0; $i < $n; $i++)

        echo $stream[$i]." ";

    echo "\n";

}

  
// Функция для случайного выбора
// k элементов из потока [0..n-1].

function selectKItems($stream, $n, $k)

    {

        $i; // индекс для элементов

            // в потоке []

          

        // резервуар [] является выходным

        // массив. Инициализируйте это с

        // первые k элементов из потока []

        $reservoir = array_fill(0, $k, 0);

        for ($i = 0; $i < $k; $i++)

            $reservoir[$i] = $stream[$i];

          

        // Итерация из (k + 1) -го

        // элемент в n-й элемент

        for (; $i < $n; $i++)

        {

            // Выбрать случайный индекс

            // от 0 до i.

            $j = rand(0,$i + 1);

              

            // Если случайно выбран

            // индекс меньше чем k,

            // затем заменить элемент

            // присутствует в индексе

            // с новым элементом из потока

            if($j < $k)

                $reservoir[$j] = $stream[$i];     

        }

          

        echo "Following are k randomly ". 

                      "selected items\n";

        printArray($reservoir, $k);

    }

      
// Код драйвера

$stream = array(1, 2, 3, 4, 5, 6, 7, 

                8, 9, 10, 11, 12);

$n = count($stream);

$k = 5;

selectKItems($stream, $n, $k);

  
// Этот код предоставлен mits
?>


Выход:

Following are k randomly selected items
6 2 11 8 12
Note: Output will differ every time as it selects and prints random elements

Сложность времени: O (n)

Как это работает?
Чтобы доказать, что это решение работает идеально, мы должны доказать, что вероятность того, что любой элемент потока [i], где 0 <= i <n будет в конечном резервуаре [], равна k / n . Разделим доказательство на два случая, так как первые k элементов обрабатываются по-разному.

Случай 1: для последних элементов потока nk , т. Е. Для потока [i], где k <= i <n
Для каждого такого элемента потока stream [i] мы выбираем случайный индекс от 0 до i, и если выбранный индекс является одним из первых k индексов, мы заменяем элемент с выбранным индексом на stream [i]

Чтобы упростить доказательство, давайте сначала рассмотрим последний пункт . Вероятность того, что последний элемент находится в конечном резервуаре = Вероятность того, что один из первых k индексов выбран для последнего элемента = k / n (вероятность выбора одного из k элементов из списка размера n )

Давайте теперь рассмотрим второй последний пункт . Вероятность того, что второй последний элемент находится в конечном резервуаре [] = [Вероятность того, что один из первых k индексов будет выбран в итерации для потока [n-2] ] X [Вероятность того, что индекс выбран в итерации для потока [n-1 ] не совпадает с индексом, выбранным для потока [n-2] ] = [ k / (n-1)] * [(n-1) / n ] = k / n .

Точно так же мы можем рассмотреть другие элементы для всех элементов потока от stream [n-1] до stream [k] и обобщить доказательство.

Случай 2: для первых k элементов потока, т. Е. Для потока [i], где 0 <= i <k
Первые k элементов первоначально копируются в резервуар [] и могут быть удалены позже в итерациях для потока [k] в поток [n] .
Вероятность того, что элемент из потока [0..k-1] находится в конечном массиве = вероятность того, что элемент не выбран, когда элементы stream [k], stream [k + 1],…. поток [n-1] считается = [k / (k + 1)] x [(k + 1) / (k + 2)] x [(k + 2) / (k + 3)] x… x [ (n-1) / n] = k / n

Ссылки:
http://en.wikipedia.org/wiki/Reservoir_sampling

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Отбор проб из водохранилища

0.00 (0%) 0 votes