均匀分布位但密度增加的算法
Algorithm to distribute bits evenly but with increasing density
我正在寻找一种算法来生成一系列位，使得系列开始时的密度非常低（即大部分为 0），而系列末尾的密度非常高（即大部分1 秒）。我通过改变随机数落在一个范围内的概率来实现这一点，但我想找到一种更结构化的[阅读：确定性]算法，比如某种稳步增加 1s 密度的方法.
有人知道类似的东西吗？或者也许是关于这些主题的一些阅读？事实证明，考虑起来很有趣，但也很有挑战性（除非我遗漏了一些简单的东西）！
有多种方法可以做到这一点，这取决于您想要的发行版。这是一个非常简单的示例，我认为它应该适合您的目的：
for (i=0; i<end; i++)
value = rand(0,1) * (2*i/end) * (2*(end-i)/end);
if(i>end/2)
value = 1 - value;
其中 rand(0,1) 生成一个介于 0 和 1 之间的值。最后您必须对结果进行舍入。
编辑：我快速实现了算法并模拟了 50 次（end = 500）。它显示了 1 和 0 的分布（四舍五入前）。
如果 0 和 1 设置完美，那么你可以在中间划分结果，左半部分应该有 1/3 与右半部分相比（换句话说：左半部分有 1/4所有的，右半部分有 3/4）。所以我们可以使用这个想法来生成位。
private static boolean[] res;
public static boolean[] generate(int len) {
res = new boolean[len];
generate(0, len, len / 2);
return res;
}
private static void generate(int start, int len, int bits) {
if (bits == len)
for (int i = start; i < start + len; i++)
res[i] = true;
else if (bits > 0) {
int l1 = len / 2, l2 = len - l1, b1 = (bits + 2) / 4, b2 = bits - b1;
if (l2 < b2) {
b2 = l2;
b1 = bits - b2;
}
generate(start, l1, b1);
generate(start + l1, l2, b2);
}
}
63、64 和 65 位的输出：
000000100000001000100010001011100010001000111111111111111111111
0000000100000001000100010001011100010001010111111111111111111111
00000001000000010001000100010111000100010001111111111111111111111
您可以使用在许多应用程序中被广泛使用的高斯分布。
我使用了 Matlab，因为它对于这种应用程序来说很容易，但它应该很容易转换成另一种语言。
那么，假设您要根据您要求的条件创建一个包含 20 个值的数组。
len = 20;
x = 1:len;
y = normdist(x, len, len/5); % you can play with mean and standard deviation.
plot(x,y)
然后，将随机性添加到等式中，并根据需要添加阈值。
rn = rand(1,len);
res = y.*rn;
并添加一个阈值，假设低于平均值的为零。
您可以使用这些值并根据需要获取一组值。
一种非常灵活的方法是使用 logistic function 来计算生成 1 与 0 的概率。这假设您知道序列的长度 先验 ，但在提升速率以及获得 1 的最小和最大概率方面为您提供了很大的灵活性。
由于您没有指定语言，我在 Ruby 中制作了原型：
# Creates an array of desired length whose values are symmetric
# about the mid-point of the array, are bounded below and above
# by min & max, and have a ramp up rate determined by steepness.
def logistic_function(length, min, max, steepness)
mid = 0.5 * (length - 1)
range = max - min
# create, initialize elements via logistic fn, and return resulting array
Array.new(length) { |x| min + range / (1 + Math.exp(-steepness * (x - mid))) }
end
length = 80
# 80 probabilities will vary from 0.1 to 0.9, with a relatively slow ramp-up
probability = logistic_function(length, 0.1, 0.9, 0.1)
# Create an array of bits where each entry's probability of being 1
# is determined by the logistic function we generated
bits = Array.new(length) { |i| rand <= probability[i] ? 1 : 0 }
puts bits.join
来自 运行 的示例输出两次：
00000000011000001000001100001101001010000011001011001111000111011111101011111011
10100000000000000000010000010111000000110110111011111000111011111111111110111111
结果是随机的，但您可以通过 min、max 和 steepness.[=18=（随机地）控制 1 的密度和转换率]
注意，根据logistic函数的对称性，1位的整体比例具有期望值(min + max) / 2。对于我在示例中使用的参数化，这是 0.5。为了说明这一点，我计算了一组 80 位中 1 的数量，并重复 generating/counting 进行 10,000 次试验。由于预期比例为 0.5，因此每次试验中 1 的预期数量为 40。以下是实证结果：
确定性地（无随机数）执行此操作的一种非常通用的方法是使用 sigma-delta 调制器。
选择一个从 0 开始到 1 结束的平滑递增函数。然后使用调制器算法以 0 和 1 逼近。
注意：Sigma-delta 调制器在电子产品中非常普遍，用于将模拟信号（声音、视频等）转换为 1/0 比特流。
为了说明，我将在 100 的周期内采用从 0 到 1 的斜坡，并使用一阶转换器。但是你可以选择任何你喜欢的曲线。例如，hyperbolic tangent 水平缩放会给出更小的开始和结束坡度，中间变化更快。二阶转换器可能会提供 "nicer" 模式。他们往往不太规律。
这是一个非常简单的算法。在 C:
#include <stdio.h>
int main(void) {
int x_max = 99;
double vn = 0;
for (int x = 0; x <= x_max; ++x) {
double xn = (double) x / x_max; // linear ramp from 0 to 1.
int yn = vn > 0.5;
printf("%d", yn);
vn += xn - yn;
}
printf("\n");
return 0;
}
如您所见，它是确定性的。它也非常简单和快速：没有三角函数、指数等。这就是为什么它有利于硬件实现。
输出分为 2 行以便于查看：
00000000000100000010000100010001001001001010100101
01010110101011011011011101110111101111110111111111
Here 是一篇关于 sigma-delta 转换的开创性论文。上面程序中的变量与图8匹配。图13显示了一个二阶图，如果你想试试的话。
为了好玩，这里有一个间隔为 1000 的 运行：
00000000000000000000000000000000010000000000000000
00000010000000000000001000000000000100000000001000
00000010000000010000000100000001000000010000001000
00010000010000010000010000010000010000100001000010
00010000100001000010001000010001000100001000100010
00100010001000100100010001001000100100010010001001
00010010010010010001001001001001001001001001001001
00101001001001001010010010100100101001010010010100
10100101010010100101001010100101010010101010010101
01001010101010100101010101010101010010101010101010
10101010101010101101010101010101010110101010101011
01010101101010101101010110101011010110101101010110
10110101101101011010110110101101101011011011011010
11011011011011011011011011011011011101101101101101
11011011101101110110111011011101110110111011101110
11101110111011110111011101111011101111011110111101
11101111011110111101111101111101111101111101111101
11111011111101111111011111110111111101111111101111
11111011111111110111111111111011111111111111101111
11111111111111111101111111111111111111111111111111
我正在寻找一种算法来生成一系列位，使得系列开始时的密度非常低（即大部分为 0），而系列末尾的密度非常高（即大部分1 秒）。我通过改变随机数落在一个范围内的概率来实现这一点，但我想找到一种更结构化的[阅读：确定性]算法，比如某种稳步增加 1s 密度的方法.
有人知道类似的东西吗？或者也许是关于这些主题的一些阅读？事实证明，考虑起来很有趣，但也很有挑战性（除非我遗漏了一些简单的东西）！
有多种方法可以做到这一点，这取决于您想要的发行版。这是一个非常简单的示例，我认为它应该适合您的目的：
for (i=0; i<end; i++)
value = rand(0,1) * (2*i/end) * (2*(end-i)/end);
if(i>end/2)
value = 1 - value;
其中 rand(0,1) 生成一个介于 0 和 1 之间的值。最后您必须对结果进行舍入。
编辑：我快速实现了算法并模拟了 50 次（end = 500）。它显示了 1 和 0 的分布（四舍五入前）。
如果 0 和 1 设置完美，那么你可以在中间划分结果，左半部分应该有 1/3 与右半部分相比（换句话说：左半部分有 1/4所有的，右半部分有 3/4）。所以我们可以使用这个想法来生成位。
private static boolean[] res;
public static boolean[] generate(int len) {
res = new boolean[len];
generate(0, len, len / 2);
return res;
}
private static void generate(int start, int len, int bits) {
if (bits == len)
for (int i = start; i < start + len; i++)
res[i] = true;
else if (bits > 0) {
int l1 = len / 2, l2 = len - l1, b1 = (bits + 2) / 4, b2 = bits - b1;
if (l2 < b2) {
b2 = l2;
b1 = bits - b2;
}
generate(start, l1, b1);
generate(start + l1, l2, b2);
}
}
63、64 和 65 位的输出：
000000100000001000100010001011100010001000111111111111111111111
0000000100000001000100010001011100010001010111111111111111111111
00000001000000010001000100010111000100010001111111111111111111111
您可以使用在许多应用程序中被广泛使用的高斯分布。
我使用了 Matlab，因为它对于这种应用程序来说很容易，但它应该很容易转换成另一种语言。
那么，假设您要根据您要求的条件创建一个包含 20 个值的数组。
len = 20;
x = 1:len;
y = normdist(x, len, len/5); % you can play with mean and standard deviation.
plot(x,y)
然后，将随机性添加到等式中，并根据需要添加阈值。
rn = rand(1,len);
res = y.*rn;
并添加一个阈值，假设低于平均值的为零。
您可以使用这些值并根据需要获取一组值。
一种非常灵活的方法是使用 logistic function 来计算生成 1 与 0 的概率。这假设您知道序列的长度 先验 ，但在提升速率以及获得 1 的最小和最大概率方面为您提供了很大的灵活性。
由于您没有指定语言，我在 Ruby 中制作了原型：
# Creates an array of desired length whose values are symmetric
# about the mid-point of the array, are bounded below and above
# by min & max, and have a ramp up rate determined by steepness.
def logistic_function(length, min, max, steepness)
mid = 0.5 * (length - 1)
range = max - min
# create, initialize elements via logistic fn, and return resulting array
Array.new(length) { |x| min + range / (1 + Math.exp(-steepness * (x - mid))) }
end
length = 80
# 80 probabilities will vary from 0.1 to 0.9, with a relatively slow ramp-up
probability = logistic_function(length, 0.1, 0.9, 0.1)
# Create an array of bits where each entry's probability of being 1
# is determined by the logistic function we generated
bits = Array.new(length) { |i| rand <= probability[i] ? 1 : 0 }
puts bits.join
来自 运行 的示例输出两次：
00000000011000001000001100001101001010000011001011001111000111011111101011111011
10100000000000000000010000010111000000110110111011111000111011111111111110111111
结果是随机的，但您可以通过 min、max 和 steepness.[=18=（随机地）控制 1 的密度和转换率]
注意，根据logistic函数的对称性，1位的整体比例具有期望值(min + max) / 2。对于我在示例中使用的参数化，这是 0.5。为了说明这一点，我计算了一组 80 位中 1 的数量，并重复 generating/counting 进行 10,000 次试验。由于预期比例为 0.5，因此每次试验中 1 的预期数量为 40。以下是实证结果：
确定性地（无随机数）执行此操作的一种非常通用的方法是使用 sigma-delta 调制器。
选择一个从 0 开始到 1 结束的平滑递增函数。然后使用调制器算法以 0 和 1 逼近。
注意：Sigma-delta 调制器在电子产品中非常普遍，用于将模拟信号（声音、视频等）转换为 1/0 比特流。
为了说明，我将在 100 的周期内采用从 0 到 1 的斜坡，并使用一阶转换器。但是你可以选择任何你喜欢的曲线。例如，hyperbolic tangent 水平缩放会给出更小的开始和结束坡度，中间变化更快。二阶转换器可能会提供 "nicer" 模式。他们往往不太规律。
这是一个非常简单的算法。在 C:
#include <stdio.h>
int main(void) {
int x_max = 99;
double vn = 0;
for (int x = 0; x <= x_max; ++x) {
double xn = (double) x / x_max; // linear ramp from 0 to 1.
int yn = vn > 0.5;
printf("%d", yn);
vn += xn - yn;
}
printf("\n");
return 0;
}
如您所见，它是确定性的。它也非常简单和快速：没有三角函数、指数等。这就是为什么它有利于硬件实现。
输出分为 2 行以便于查看：
00000000000100000010000100010001001001001010100101
01010110101011011011011101110111101111110111111111
Here 是一篇关于 sigma-delta 转换的开创性论文。上面程序中的变量与图8匹配。图13显示了一个二阶图，如果你想试试的话。
为了好玩，这里有一个间隔为 1000 的 运行：
00000000000000000000000000000000010000000000000000
00000010000000000000001000000000000100000000001000
00000010000000010000000100000001000000010000001000
00010000010000010000010000010000010000100001000010
00010000100001000010001000010001000100001000100010
00100010001000100100010001001000100100010010001001
00010010010010010001001001001001001001001001001001
00101001001001001010010010100100101001010010010100
10100101010010100101001010100101010010101010010101
01001010101010100101010101010101010010101010101010
10101010101010101101010101010101010110101010101011
01010101101010101101010110101011010110101101010110
10110101101101011010110110101101101011011011011010
11011011011011011011011011011011011101101101101101
11011011101101110110111011011101110110111011101110
11101110111011110111011101111011101111011110111101
11101111011110111101111101111101111101111101111101
11111011111101111111011111110111111101111111101111
11111011111111110111111111111011111111111111101111
11111111111111111101111111111111111111111111111111