2

tl;dr: golang の配列内の値 (または値の関数) の相対的な大きさに基づいて加重ランダム選択を実装する方法を探しています。このための標準アルゴリズムまたは推奨パッケージはありますか? 彼らはどのようにスケーリングしますか？

目標

golang で 2D および 3D マルコフ処理プログラムを作成しようとしています。そのような単純な 2D の例は次のとおりです。1 つの格子があり、インデックス (i,j) でラベル付けされた各サイトに n(i,j) 個の粒子があるとします。各時間ステップで、プログラムはサイトを選択し、このサイトから 1 つの粒子をランダムな隣接サイトに移動します。サイトが選択される確率は、その時点での人口 n(i,j) に比例します。

現在の実装

L x L ラティスの 2D ケースなど、現在のアルゴリズムは次のとおりです。

  • 行を順番に連結して、開始配列を長さ L^2 のスライスに変換しますcdfpop[i L +j]=initialpopulation[i][j]。
  • for loop over を実行して、1D スライスを cdf に変換しますcdfpop[i]+=cdfpop[i-1]。
  • 2 つの乱数を生成しますRsite。範囲は 1 から cdf の最大値 (これは最後の値 ですcdfpop[L^2-1]) で、Rhop範囲は 1 から 4 です。ホップするランダムな方向に番号を付ける
  • 二分探索を使用して、より大きいの左端のインデックスindexhopを見つけます。ホップ先のインデックスは、x 方向のホップまたはy 方向のホップのいずれかです。cdfpopRsiteindexhop +-1indexhop +- L
  • cdfpop最後に、ホップ プロセスを反映するようにの値を直接変更します。cdfpopこれは、順序に応じて、ホップ元 (to) のインデックスとホップ先 (from) のインデックスの間のすべての値から 1 を減算 (1 を加算) することを意味します。
  • すすぎ、 for ループで繰り返します。最後に累積分布関数を逆にして、最終的な母集団を決定します。

編集: 要求された擬似コードは次のようになります。

main(){

       //import population LxL array
       population:= import(population array)

       //turn array into slice
       for i number of rows{
          cdf[ith slice of length L] = population[ith row]
          }
       //compute cumulant array
       for i number of total sites{
          cdf[i] = cdf[i-1]+cdf[i]
          }

       for i timesteps{
          site = Randomhopsite(cdf)
          cdf = Dohop(cdf, site)
          } 

       Convertcdftoarrayandsave(cdf)
       }

Randomhopsite(cdf) site{

      //Choose random number in range of the cummulant
      randomnumber=RandomNumber(Range 1 to Max(cdf))


      site = binarysearch(cdf) // finds leftmost index such that                                           
                               // cdf[i] > random number

      return site
      }

Dohop(cdf,site) cdf{ 

      //choose random hop direction and calculate coordinate
      randomnumber=RandomNumber(Range 1 to 4)
      case{
            randomnumber=1 { finalsite= site +1}
            randomnumber=2 { finalsite= site -1}
            randomnumber=3 { finalsite= site + L}
            randomnumber=4 { finalsite= site - L}
           }

      //change the value of the cumulant distribution to reflect change
      if finalsite > site{
           for i between site and finalsite{
                        cdf[i]--
              }
      elseif finalsite < site{
           for i between finalsite and site{
                        cdf[i]++
              }
      else {error: something failed}


      return cdf
      }

このプロセスは、単純な問題に対して非常にうまく機能します。この特定の問題については、現在のセットアップで平均約 2 分で 1000x 1000 格子で約 1 兆ステップを実行できます。また、巨大な関数を使わずに go ルーチンをスピンすることで、10000 程度のステップごとに人口データを GIF にコンパイルできます。徐行。

効率が低下する場所

問題は、サイトの人口に比例しない実数値の係数を持つさまざまなプロセスを追加したいときに発生します。つまり、k_hop *n(i,j) でのホッピング レートと、k_death *(n(i,j))^2 での死亡率 (パーティクルを単純に削除した場合) があるとします。この場合、2 つの速度低下があります。

  • 私の cdf は 2 倍のサイズになります (それほど大きな問題ではありません)。それは実際に評価され、cdfpop[i*L+j]= 4 *k_hop * pop[i][j]fori*L+j<L*Lとcdfpop[i*L+j]= k_death*math. Power(pop[i][j],2)forによって作成されL*L<=i*L+j<2*L*L、その後に が続きcdfpop[i]+=cdfpop[i-1]ます。次に、cdf の範囲内でランダムな実数を選択します。
  • n が 2 乗されているため、各ステップで死亡プロセスの重みに関連付けられた cdf の部分を動的に再計算する必要があります。予想通り、これは大幅な速度低下です。このタイミングは、元のアルゴリズムが 1 ナノ秒未満であったのに比べて、約 3 マイクロ秒です。

この問題は、隣接するサイトの人口の関数としてレートを計算した場合にのみ悪化します。たとえば、自発的な粒子の作成は、隣接するサイトの人口の積に依存します。再計算せずに cdf を修正する方法を真剣に考えて解決したいと思っていますが、複雑さが増す問題をシミュレートしようとしているので、合理的な効率を備えた普遍的な解決策があるかどうか疑問に思わずにはいられません。ランダムなプロセスごとに特別なコードを必要としません。

読んでくれてありがとう！

4

0 に答える 0