通过排除 C 中的一个值来改变离散概率数组-解网

问：

我正在 C 语言的一个项目中工作，我想在以下条件下逐步改变 a：uint32_t

位翻转的概率开始时，最低有效位（LSB）的概率为 1/2，左侧的下一个位的概率为 1/4，下一个位的概率为 1/8，依此类推（参见示例数组）。
翻转位后，概率（k）的值将根据步骤一中列出的分布重新分配给所有其他位。k
然后将 probability（k）设置为零。

我想这些概率最好存储在长度为 32 的双精度数组中，因此一个非常有用的答案是一个函数，它接受长度为 32 的双精度数组和一些要排除的位整数，并返回修改后的长度 32 数组。

这是否可以通过生成一个长度为 31 的数组来实现，使用步骤 1 中的过程排除，将每个值乘以的值，然后创建一个长度为 32 的数组并将其添加到输入数组中（在设置？karray[k]array[k] = 0input[k] = 0

我想象可能会发生一个问题，但我不确定如何解决：

在第一步中，这些概率均为 1。大到足以用双打和 2 表示。2 的幂，因此它们被准确表示。但是，没有充分的理由让他们保持这种状态。下面的示例数组总和为 1，因为它们都是完全可表示的。同样，我没有理由认为其他值也是如此。我不清楚如何保持粗略的实用能力，以一种相当于从总和为一的分布中抽取的方式进行选择。

答案

解决方案必须是 C 语言，因为项目中的其余代码是 C。对不起，我敢肯定有非常酷的方法可以用其他语言解决这个问题。可能 R 中的二项式包会有一些这样做的东西，但这无济于事。类似 C 的语言，我可以手动调整代码以在 C 中工作也很好。

我在台式计算机上控制着开发环境，因此欢迎任何能够简化此操作的库。谢谢。此外，我不希望有任何性能限制，因此速度慢或需要存储表的代码很好。

我在这里的例子使用了双打，但这不是确定的。我来这里问这个问题，因为我不知道该怎么做。如果你有一个完全适用于整数的答案，那么我很想看到这一点。

示例数组

void create_array32(double array[32]) {
    int i;
    for (i = 0; i < 32; i++) {
        array[i] = pow(2, -(32 - i));
    }
}
// The output, if that is easier to work with
double example[32] = {
0.0000000002328306, 0.0000000004656613,
0.0000000009313226, 0.0000000018626451,
0.0000000037252903, 0.0000000074505806,
0.0000000149011612, 0.0000000298023224,
0.0000000596046448, 0.0000001192092896,
0.0000002384185791, 0.0000004768371582,
0.0000009536743164, 0.0000019073486328,
0.0000038146972656, 0.0000076293945312,
0.0000152587890625, 0.0000305175781250,
0.0000610351562500, 0.0001220703125000,
0.0002441406250000, 0.0004882812500000,
0.0009765625000000, 0.0019531250000000,
0.0039062500000000, 0.0078125000000000,
0.0156250000000000, 0.0312500000000000,
0.0625000000000000, 0.1250000000000000,
0.2500000000000000, 0.5000000000000000}

数组 C 浮点概率离散空间

虽然 TL;DR 方法是使用，并且您经常这样做，您可能希望使用“缩放整数”数字来表示概率。例如，概率 1/2 是 500,1/4 是 250，[除以 1000] ......或者，“诀窍”是使用 2 的幂：512-->1/2、256-->1/4，[然后你可以用右移代替 1024 的除法]......double

答：

2赞 John Bollinger 4/6/2023 #1

与其维护概率数组，不如维护相应的选择频率数组：

uint32_t frequencies[32];

for (int i = 0; i < 32; i++) {
    frequencies[i] = (uint32_t) 1 << (31 - i);
}

如果您愿意，可以预先计算这些起始频率并将它们放入初始值设定项中，而不是在运行时计算它们。

每次你想做出选择时，

计算频率累积总和的数组：

uint32_t cumulative[33] = {0};

for (int i = 0; i < 32; i++) {
    cumulative[i + 1] = cumulative[i] + frequencies[i];
}

生成一个介于 0（含）和（不含）之间的（均匀分布）随机数。xcumulative[32]
找到这样的值。这是选定的位号。您可以使用二进制搜索，但线性搜索会更简单，并且仅对 32 个项目进行搜索，速度大致相同。ncumulative[n] <= x && x < cumulative[n + 1]n

要从进一步的考虑中删除位，只需将其频率设置为 0：n

frequencies[n] = 0;

当您计算下一个选项的新累积总和时，自然会排除在考虑之外，并通过计算修订后的总数来调整所有剩余选项的概率。n

0赞 Adam Hyland 4/7/2023 #2


int choose_bit(double array[32]) {
  double cumsum[32] = { 0 };
  compute_cumulative_sum(array, cumsum);
  // https://stackoverflow.com/a/6219525
  double r = (double)rand() / (double)RAND_MAX;
  int i = 0;
  for (i = 0; i < 32; i++) {
    if (r <= cumsum[i]) {
      return i;
    }
  }
}

int mutate_and_advance(double array[32]) {
    double gapped[32];
    float chosen_prob;

    int bit = choose_bit(array);
    create_gapped_array32(gapped, bit);
    chosen_prob = array[bit];
    array[bit] = 0;
    multiply_array_by_scalar(gapped, chosen_prob);
    add_32_arrays(array, gapped, array);
    return bit;
}

我认为以上内容可以满足我的需求。它现在返回一个 int，因此我可以测试它是否以我想要的方式循环遍历索引。

下面的辅助函数和库，以及一个（非常）粗略的测试：


#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

void create_array32(double array[32]) {
  int i;
  for (i = 0; i < 32; i++) {
    array[i] = ldexp(1, -(32 - i));
  }
}

void create_gapped_array32(double array[32], int location) {
    int i;
    for (i = 0; i < 32; i++) {
        if (i == location) {
            array[i] = 0;
        } else {
            array[i] = ldexp(1, -(32 - i));
        }
    }
}

void compute_cumulative_sum(double arr[32], double sum[32]) {
  sum[0] = arr[0];
  for (int i = 1; i < 32; i++) {
    sum[i] = sum[i - 1] + arr[i];
  }
}

void multiply_array_by_scalar(double array[32], double scalar) {
  int i;
  for (i = 0; i < 32; i++) {
    array[i] *= scalar;
  }
}

void add_32_arrays(double left[32], double right[32], double output[32]) {
  int i;
  for (i = 0; i < 32; i++) {
    output[i] += left[i] + right[i];
  }
}

// Test 

int main() {
  int k = 0;
  double probabilties[32] = { 0 };
  create_array32(probabilties);
  for (k = 0; k < 55; k++) {
    printf("Index: %d\n", mutate_and_advance(probabilties));
  }

  return 0;
}

上一个：最大的 uint64，可以在 C/C++ 的浮点数中准确表示 [重复]

下一个：创建 JSON 对象时，数字的显示方式会有所不同

通过排除 C 中的一个值来改变离散概率数组

Mutate an array of discrete probabilities by excluding one value in C

答案

示例数组

评论