2

私は一定量のサンプルを持っており、各サンプルには確率があります。次に、このデータ ソースからリサンプリングして、同じ確率を持つ同じ量の新しいサンプルを取得します。

例えば：

                                          random | 0.03 | 0.78 | 0.45 | 0.70
                                          -------+------+------+------+------
sample | 0000 | 0001 | 0002 | 0003   RNG  sample | 0000 | 0003 | 0002 | 0003
-------+------+------+------+------ ====> -------+------+------+------+------
 prob. | 0.10 | 0.20 | 0.30 | 0.40         prob. | 0.25 | 0.25 | 0.25 | 0.25

私の場合、確率は直接ではなく重みとして与えられます。ただし、確率はすべての重みの合計がわかっているため (ただし一定ではない)、重みから直接導き出すことができます。

MATLAB の実装では、Statistics Toolbox の関数randsampleを使用して、このリサンプリング プロセスを実現しました。

y = randsample(n,k,true,w)または、長さがy = randsample(population,k,true,w)の正の weights のベクトルを使用して、置換で取得された重み付けされたサンプルを返します。のエントリに整数が選択される確率は です。通常、は確率のベクトルです。置換なしの加重サンプリングはサポートされていません。wniyw(i)/sum(w)wrandsample

function [samples probabilities] = resample(samples, probabilities)
    sampleCount = size(samples, 1);
    indices = randsample(1 : samplecount, samplecount, 
                         true, probabilities);
    samples = samples(indices, :);
    probabilities = repmat(1 / sample count, samplecount, 1);
end

アルゴリズムのこの部分を iPad 2 に移植して、 512 サンプルがリサンプリングされるリアルタイム (~25fps) データを更新するために使用します。したがって、他の計算も実行されるため、時間効率が重要です。メモリを最小化する必要はありません。

Alias メソッドを調べましたが、構造構築プロセスは非常に面倒で、おそらく最も効率的なソリューションではないようです。

リアルタイム要件を満たす他の効率的な方法はありますか、それとも Alias メソッドが適していますか?

4

1 に答える 1

1

resampleC で実装する方法の例を次に示します。

typedef int SampleType;
typedef double ProbabilityType;

static ProbabilityType MyRandomFunction(ProbabilityType total)
{
    static boolean_t isRandomReady = 0;
    if ( ! isRandomReady ) {
        srandomdev();
        isRandomReady = 1;
    }

    long randomMax = INT_MAX;
    return (random() % (randomMax + 1)) * (total / randomMax);
}

static void MyResampleFunction(SampleType *samples, ProbabilityType *probabilities, size_t length)
{
    ProbabilityType total = 0;

    // first, replace probabilities with sums
    for ( size_t i = 0; i < length; i++ )
        probabilities[i] = total += probabilities[i];

    // create a copy of samples as samples will be modified
    SampleType *sampleCopies = malloc(sizeof(SampleType) * length);
    memcpy(sampleCopies, samples, sizeof(SampleType) * length);

    for ( size_t i = 0; i < length; i++ )
    {
        ProbabilityType probability = MyRandomFunction(total);

        // We could iterate through the probablities array but binary search is more efficient

        // This is a block declaration
        int (^comparator)(const void *, const void *);

        // Blocks are the same a function pointers
        // execept they capture their enclosing scope
        comparator = ^(const void *leftPtr, const void *rightPtr) {

            // leftPtr points to probability
            // rightPtr to an element in probabilities

            ProbabilityType curr, prev;
            size_t idx = ((const ProbabilityType *) rightPtr) - probabilities;
            curr = probabilities[idx];                   // current probablity
            prev = idx > 0 ? probabilities[idx - 1] : 0;   // previous probablity

            if ( curr < probability )
                return 1;
            if ( prev > probability )
                return -1;

            return 0;
        };

        void *found = bsearch_b(&probability,            // the searched value
                                probabilities,           // the searched array
                                length,                  // the length of array
                                sizeof(ProbabilityType), // the size of values
                                comparator);             // the comparator

        size_t idx = ((const ProbabilityType *) found) - probabilities;
        samples[i] = sampleCopies[idx];
    }

    // now, probabilities are all the same
    for ( size_t i = 0; i < length; i++ )
        probabilities[i] = 1.0 / length;

    // Now the can dispose of the copies
    free(sampleCopies);
}

static void MyTestFunction()
{
    SampleType samples[4] = {0, 1, 2, 3};
    ProbabilityType probabilities[10] = {0.1, 0.2, 0.3, 0.4};
    MyResampleFunction(samples, probabilities, 4);
}
于 2011-12-22T16:21:47.673 に答える