0

データ ポイントに対するイテレータit、データ ポイントの数、n計算に使用するサンプルの最大数 ( maxSamples) が与えられます。

関数を想像してみてくださいcalculateStatistics(Iterator it, int n, int maxSamples)。この関数は、反復子を使用してデータを取得し、取得したデータ要素に対していくつかの (重い) 計算を実行する必要があります。

  • n <= maxSamplesもちろん、イテレータから取得した各要素を使用する場合
  • n > maxSamples見る要素とスキップする要素を選択する必要がある場合

私はこれにかなりの時間を費やしてきました。問題はもちろん、要素をスキップするタイミングと保持するタイミングをどのように選択するかです。これまでの私のアプローチ：

  • maxSamples値が均等に分散されない可能性があるため、イテレータから最初に取得したくありません。
  • もう 1 つのアイデアは、乱数ジェネレーターを使用して、 と の間の (異なる) 乱数を作成しmaxSamples、これらの位置の要素を取得することでした。しかし、たとえば、まだリストにない新しい固有の番号を見つけることがますます難しくなり、乱数の生成だけで多くの時間を失う場合0nn = 101maxSamples = 100
  • 私の最後のアイデアは、逆のことをすることでした:n - maxSamples乱数を生成し、これらの位置要素のデータ要素を除外します。しかし、これもあまり良い解決策ではないようです。

この問題について良いアイデアはありますか？これにはおそらく標準的な既知のアルゴリズムがありますか?

4

4 に答える 4

1 
interval = n/(n-maxSamples) //an euclidian division of course
offset = random(0..(n-1)) //a random number between 0 and n-1
totalSkip = 0
indexSample = 0;
FOR it IN samples DO
    indexSample++ // goes from 1 to n
    IF totalSkip < (n-maxSamples) AND indexSample+offset % interval == 0 THEN
        //do nothing with this sample
        totalSkip++
    ELSE
        //work with this sample
    ENDIF
ENDFOR
ASSERT(totalSkip == n-maxSamples) //to be sure

intervalスキップする 2 つのサンプル間の距離を表します。 offset必須ではありませんが、多様性をほとんど持たせることができません。

于 2013-05-15T15:15:02.423 に答える
1

議論に基づいて、問題をより深く理解した上で、次のことをお勧めします。疑似乱数を取得するように見える、非常に優れたソリューションが得られると思われる素数のプロパティを利用できます。次のコードで説明します。

#include <iostream>
using namespace std;


int main() {
    const int SOME_LARGE_PRIME = 577;  //This prime should be larger than the size of your data set.  
    const int NUM_ELEMENTS = 100;
    int lastValue = 0;
    for(int i = 0; i < NUM_ELEMENTS; i++) {
        lastValue += SOME_LARGE_PRIME;
        cout << lastValue % NUM_ELEMENTS << endl;
    }
}

ここに示すロジックを使用して、1 から "NUM_ELEMENTS" までのすべての値のテーブルを作成できます。素数の特性により、回転してデータ セットのサイズに戻るまで、重複は発生しません。次に、これらの最初の「NUM_SAMPLES」を取得して並べ替えると、データ構造を反復処理し、数値の疑似ランダム分布を取得できます (あまり良いランダムではありませんが、事前に決定された間隔よりもランダムです)。余分なスペースがあり、データを 1 回だけ通過します。さらに良いことに、ランダムな素数を毎回取得することで分布のレイアウトを変更できます。これも、データ セットよりも大きくなければなりません。そうしないと、次の例が壊れます。

PRIME = 3、データ セット サイズ = 99。機能しません。

もちろん、最終的にはこれは事前に決定された間隔と非常に似ていますが、単純に「size/num_samples」番目の要素をすべて取得するだけでは得られないレベルのランダム性が挿入されます。

于 2013-05-15T16:51:47.080 に答える
1

いくつかの答えを提供するために、コレクションサイズ>必要な要素を指定して一連の乱数を収集する良い方法は次のとおりです。(C++っぽい疑似コードで)。

編集:最初に「someElements」ベクトルを反復して作成する必要がある場合があります。要素が大きい場合は、これらの要素への「ポインター」にしてスペースを節約できます。

vector randomCollectionFromVector(someElements, numElementsToGrab) {
    while(numElementsToGrab--) {
         randPosition = rand() % someElements.size();
         resultVector.push(someElements.get(randPosition))
         someElements.remove(randPosition);
    }
    return resultVector;
}

要素のベクトルを変更することを気にしない場合は、言及したように、someElements からランダムな要素を削除することもできます。アルゴリズムは非常に似ていますが、これも概念的には同じ考えです。参照によって someElements を渡し、それを操作するだけです。

注目に値するのは、使用した分布のサイズが大きくなるにつれて、疑似ランダム分布の品質がどれほどランダムであるかということです。したがって、より多くの乱数を使用する方法に基づいて使用する方法を選択すると、より良い結果が得られる傾向があります。例: 100 個の値があり、99 個が必要な場合、おそらく 99 個の値を選択する必要があります。これにより、1 個だけではなく、99 個の疑似乱数を使用することになります。逆に、1000 個の値があり、99 個が必要な場合は、擬似ランダム分布からより多くの数値を使用するため、おそらく 901 値を削除したバージョンを好むでしょう。しっかりとしたランダムな分布が必要な場合、これは非常に単純な最適化であり、表示される「偽のランダム性」の品質が大幅に向上します。あるいは、

于 2013-05-15T14:28:30.150 に答える