c++ - 二项分布压缩

Question

我目前很难为某个问题想出一个快速且低内存的解决方案。我正在尝试使用二项分布来解决。我有一个可以取 5 个值的二项式分布，值出现的概率是 1/16、4/16、6/16、4/16、1/16。我目前正在使用 4 位数字来访问大小为 16 的二项式分布数组，该数组包含 5 个值，其出现次数与其概率成正比。有没有一种方法可以将数组压缩到 5 的大小，并且仍然能够快速确定要访问数组中的哪个元素。我考虑过使用卡诺图，但是所需的逻辑操作数量减慢了整个过程。是否存在某种压缩或技术可以快速实现这一点，因为我希望增加二项式分布的大小，由于内存或计算时间的增加，目前这是不可行的。

  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];
  }

对比

 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/2 的概率为 1。如果您只计算位数，它已经为您提供了具有二项式概率的压缩数组中的索引。

 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];
 }