14

各数値を生成する前にシードが与えられたときに高速に動作するように特化された疑似乱数ジェネレーターを探しています。私がこれまで見てきたほとんどのジェネレーターは、シードを一度設定してから、長い数列を生成することを前提としています。これまで見てきたのと少し似ているのはパーリン ノイズだけですが、あまりにも「滑らかな」データを生成します。同様の入力に対して、同様の結果が生成される傾向があります。

ジェネレーターの宣言は次のようになります。

int RandomNumber1(int seed);

または：

int RandomNumber3(int seedX, int seedY, int seedZ);

入力をハッシュして結果を RandomNumber1 に渡すことで RandomNumber3 を実装することができるため、適切な RandomNumber1 があれば十分だと思いますが、一部の実装で独立した入力を使用できる場合に備えて、2 番目のプロトタイプを作成しました。

このジェネレーターの使用目的は、グリッドに木を配置し、ランダムな樹種と各場所のランダムな空間オフセットを決定することで森林を生成するなど、手続き型コンテンツ ジェネレーターに使用することです。

プロシージャルコンテンツはレンダリング中にリアルタイムで大量に作成されるため、ジェネレーターは非常に効率的 (500 CPU サイクル未満) である必要があります。

4

6 に答える 6

21

PRNGではなくハッシュ関数を求めているようです。「高速ハッシュ関数」をグーグルで検索すると、いくつかの有望な結果が得られます。

例:

uint32_t hash( uint32_t a)
    a = (a ^ 61) ^ (a >> 16);
    a = a + (a << 3);
    a = a ^ (a >> 4);
    a = a * 0x27d4eb2d;
    a = a ^ (a >> 15);
    return a;
}

編集：はい、いくつかのハッシュ関数は間違いなく他のものよりも適切に見えます。

あなたの目的のためには、関数を観察し、入力の単一ビットの変化が多くの出力ビットに伝播することを確認するだけで十分なはずです。

于 2008-10-03T16:30:53.197 に答える
9

はい、PRNG ではなく、高速な整数ハッシュ アルゴリズムを探しています。

このページにはいくつかのアルゴリズムがあります。正しい検索用語がわかれば、さらに多くのアルゴリズムが見つかるはずです。

編集: 元のページは削除されました。ライブ バージョンはGitHub にあります。

于 2008-10-03T16:38:44.973 に答える
5

これは、George Marsaglia によって開発された小さな乱数ジェネレーターです。彼はこの分野の専門家であるため、ジェネレーターが優れた統計的特性を持っていることを確信できます。

v = 36969*(v & 65535) + (v >> 16);
u = 18000*(u & 65535) + (u >> 16);
return (v << 16) + (u & 65535);

ここで u と v は unsigned int です。それらをゼロ以外の値に初期化します。乱数を生成するたびに、u と v をどこかに保存します。これを関数でラップして、上記の署名に一致させることができます (ただし、int は署名されていません)。

于 2008-10-19T01:07:03.630 に答える
2

std::tr1::ranlux3、または標準 C++ ライブラリへの TR1 追加の一部であるその他の乱数ジェネレーターを参照してください。最初はmt19937を提案しましたが、非常に高速である必要があるというあなたのメモを見ました。TR1 は、 Microsoft VC++および GCC で利用できるはずであり、さらに多くのコンパイラをサポートするブースト ライブラリにも含まれています。

ブーストのドキュメントから適用された例: 

#include <random>
#include <iostream>
#include <iterator>
#include <functional>
#include <algorithm>
#include <ctime>
using namespace std;
using namespace std::tr1;
int main(){
    random_device trueRand;
    ranlux3 rng(trueRand);  // produces randomness out of thin air
                            // see pseudo-random number generators
    uniform_int<> six(1,6); // distribution that maps to 1..6
                            // see random number distributions
    variate_generator<ranlux3&, uniform_int<> >
           die(rng, six);   // glues randomness with mapping

    // simulate rolling a die
    generate_n( ostream_iterator<int>(cout, " "), 10, ref(die));
}

出力例:

2 4 4 2 4 5 4 3 6 2

どの TR1 乱数ジェネレーターでも、他の乱数ジェネレーターをシードできます。より高品質の結果が必要な場合は、mt19937 (低速ですが高品質) の出力を、より高速なジェネレーターである minstd_rand または randlux3 にフィードすることを検討してください。

于 2008-10-03T17:48:36.923 に答える
0

私はJava乱数ライブラリで次のコードを使用しています-これは私にとってはかなりうまくいきました。これは、手続き型コンテンツの生成にも使用します。

/**
 * State for random number generation
 */
private static volatile long state=xorShift64(System.nanoTime()|0xCAFEBABE);

/**
 * Gets a long random value
 * @return Random long value based on static state
 */
public static long nextLong() {
    long a=state;
    state = xorShift64(a);
    return a;
}

/**
 * XORShift algorithm - credit to George Marsaglia!
 * @param a initial state
 * @return new state
 */
public static final long xorShift64(long a) {
    a ^= (a << 21);
    a ^= (a >>> 35);
    a ^= (a << 4);
    return a;
}
于 2009-11-18T21:21:05.170 に答える
0

メモリが実際には問題ではなく、速度が最も重要である場合は、多数の乱数の配列を事前に作成し、実行時にそれを反復処理することができます。たとえば、別のプログラムで100,000の乱数を生成し、次のような独自のファイルとして保存するようにします。

unsigned int randarray [] = {1,2,3、....}

次に、そのファイルをコンパイルに含めます。実行時に、乱数関数はその配列から数値をプルし、最後に到達したときに最初にループバックするだけで済みます。

于 2008-10-05T00:04:19.253 に答える