二項分布圧縮

Question

私は現在、問題に対して高速で低メモリのソリューションを考え出すのが難しいです。私は二項分布を使って解くことを試みています。私は5つの値を取ることができる二項分布を持ち、発生する確率の確率は1/16、4/16、6/16、4/16、1/16です。私は現在、4ビットの数値を使用して、その確率に比例した5つの値を含むサイズ16の2項分布アレイにアクセスしています。配列をサイズ5に圧縮する方法がありますが、アクセスする配列のどの要素をすばやく判断できるかどうかです。私はKarnaughマップを使用することを検討しましたが、必要な論理操作の数によってプロセス全体が遅くなりました。メモリや計算時間の増加のために現時点では実行不可能な二項分布のサイズを増やしたいので、これを迅速に実装するための圧縮や技術がありますか？

binomialCoefficients[16]= {v1, v2, v2, v2, v2, v3, v3, v3, v3, v3, v3, v3, v4, v4, v4, v4, v5}; 
    for (int i = 0; i < steps; i++) { 
    uint random = MWC64X(&seed2); 
    currentValue = currentValue * binomialCoefficients[random & 0b1111]; 
    } 

VS

binomialCompressed[5]={v1,v2,v3,v4,v5}; 
for (int i = 0; i < steps; i++) { 
    uint random = MWC64X(&seed2); 
    bool A = (random & 0b1000) >>3; 
    bool B = (random & 0b0100) >>2; 
    bool C = (random & 0b0010) >>1; 
    bool D = (random & 0b0001); 
    uint logicMappedIndex = (A&B&C&D)<<2 + (A&!B|...)<<1 +...; 
    currentValue = currentValue * binomialCompressed[logMappedIndex]; 
} 

Answer 1

あなたは乱数を生成する場合、各ビットは、あなただけのビットをカウントした場合、それはすでに与えている1 という1/2の確率を持っています圧縮された配列のインデックスを二項確率で表します。

binomialCompressed[5]={v1,v2,v3,v4,v5}; 
for (int i = 0; i < steps; i++) { 
    uint random = MWC64X(&seed2) & 0b1111; //Get 4 bits only 
    uint count = popcount(random); 
    currentValue = currentValue * binomialCompressed[count]; 
}