Non Uniform Random Number II

Description:

自己编的，particle filter里面需要resample N个random number，如果用上一种方法，则time O(nlogn), 这个方法是O(n).

Given n numbers, each with some frequency of occurrence. Return a random number with probability proportional to its frequency of occurrence.

Example:

Note

Idea:

Resampling wheel.

Algorithm:

p3 = []
index = int(random.random() * N)
beta = 0.0
mw = max(w)
for i in range(N):
    beta += random.random() * 2.0 * mw
    while beta > w[index]:
        beta -= w[index]
        index = (index + 1) % N
    p3.append(p[index])
p = p3

Code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;


class NonUniformRandom 
{
public:
    NonUniformRandom(vector<int> arr, vector<double> weight)
    : arr(arr)
    , weight(weight)
    {}    

    vector<int> getRandomNumbers() const{
        int sizeN = arr.size();
        int index = rand()%sizeN;
        double maxWeidght = *max_element(weight.begin(), weight.end());
        double beta = 0;
        vector<int> result;

        for(int i=0; i<sizeN; i++){
            beta += randDouble() * 2.0 * maxWeidght;
            while(beta>weight[index]){
                beta -= weight[index];
                index = (index+1)%sizeN;
            }
            result.push_back(arr[index]);
        }
        return result;
    }

private:
    double randDouble() const {
        return rand()/double(RAND_MAX);
    }
    vector<int> arr;
    vector<double> weight;
};

int main(){
    vector<int> arr={10, 30, 20, 40};
    vector<double> weight={1, 6, 2, 1};

    NonUniformRandom nonUniformRnd(arr, weight);

    for(auto elem: nonUniformRnd.getRandomNumbers()){
        cout<<elem<<' ';
    }
}