如何有效地在bash中生成大的，均匀分布的随机整数？

马尔特·斯科鲁帕（Malte Skoruppa）

我一直在想这将是获得最佳的方式很好在bash，即随机性，这将是一个过程，以获得之间的随机正整数MIN，并MAX使得

的范围内可以任意大（或至少，说，高达2 ³² -1）;
值是均匀分布的（即无偏差）；
这是有效的。

获得bash随机性的有效方法是使用$RANDOM变量。但是，这仅对0到2 ¹⁵ -1之间的值进行采样，该值可能不足以用于所有目的。人们通常会使用模数来使模数达到他们想要的范围，例如，

MIN=0
MAX=12345
rnd=$(( $RANDOM % ($MAX + 1 - $MIN) + $MIN ))

另外，这会产生偏差，除非$MAX碰巧将2 ¹⁵ -1 = 32767相除。例如，如果$MIN为0且$MAX为9，则值0到7比值8和9更有可能，因为$RANDOM永远不会是32768或32769。随着范围的增加，此偏差会变得更糟，例如，如果$MIN为0且$MAX为9999，然后通过2767数字0具有的概率⁴ / ₃₂₇₆₇，而数字2768到9999只的概率³ / ₃₂₇₆₇。

因此，虽然上述方法满足条件3，但不满足条件1和2。

到目前为止，我想尝试满足条件1和2的最佳方法是使用/dev/urandom以下方法：

MIN=0
MAX=1234567890
while
  rnd=$(cat /dev/urandom | tr -dc 0-9 | fold -w${#MAX} | head -1 | sed 's/^0*//;')
  [ -z $rnd ] && rnd=0
  (( $rnd < $MIN || $rnd > $MAX ))
do :
done

基本上，只是从中收集随机性/dev/urandom（/dev/random如果需要加密强度高的伪随机数生成器，并且如果您有很多时间，或者可能是硬件随机数生成器，则可以考虑使用），删除每个不是十进制数字的字符，将其折叠输出到的长度$MAX并削减前导0。如果碰巧只得到0，$rnd则为空，因此在这种情况下设置rnd为0。检查结果是否超出我们的范围，如果超过，请重复。我本着模仿do ... while循环的精神，将while循环的“ body”强制进入了后卫，以强制至少执行一次body ，因为从rnd开始就没有定义。

我认为我满足了这里的条件1和2，但是现在我搞砸了条件3。这有点慢。大约需要一秒钟的时间（如果幸运的话，需要十分之一秒的时间）。实际上，甚至无法保证循环会终止（尽管随着时间的增加，终止的概率收敛到1）。

是否有一种有效的方法来获取bash中预先指定且可能很大范围内的无偏随机整数？（我会在时间允许的情况下继续进行调查，但与此同时，我认为这里的某个人可能有一个很不错的主意！）

答案表

最基本的（也是可移植的）想法是生成足够长的随机位串。使用bash的内置$RANDOM变量或使用odand /dev/urandom（或/dev/random），有多种生成随机位串的方法。如果随机数大于$MAX，则重新开始。
另外，也可以使用外部工具。
- Perl解决方案
  - 优点：非常便携，简单，灵活
  - 相反：不适用于2 ³² -1以上的非常大的数字
- Python解决方案
  - 专业版：简单，灵活，甚至可以大量使用
  - 相反：便携式性较差
- zsh解决方案
  - 优点：还是适合使用zsh的人
  - 相反：可能更不便携

马尔特·斯科鲁帕（Malte Skoruppa）

谢谢大家的出色回答。最后，我想分享以下解决方案。

在我详细介绍为什么和方式之前，这是tl; dr：我闪亮的新脚本:-)

#!/usr/bin/env bash
#
# Generates a random integer in a given range

# computes the ceiling of log2
# i.e., for parameter x returns the lowest integer l such that 2**l >= x
log2() {
  local x=$1 n=1 l=0
  while (( x>n && n>0 ))
  do
    let n*=2 l++
  done
  echo $l
}

# uses $RANDOM to generate an n-bit random bitstring uniformly at random
#  (if we assume $RANDOM is uniformly distributed)
# takes the length n of the bitstring as parameter, n can be up to 60 bits
get_n_rand_bits() {
  local n=$1 rnd=$RANDOM rnd_bitlen=15
  while (( rnd_bitlen < n ))
  do
    rnd=$(( rnd<<15|$RANDOM ))
    let rnd_bitlen+=15
  done
  echo $(( rnd>>(rnd_bitlen-n) ))
}

# alternative implementation of get_n_rand_bits:
# uses /dev/urandom to generate an n-bit random bitstring uniformly at random
#  (if we assume /dev/urandom is uniformly distributed)
# takes the length n of the bitstring as parameter, n can be up to 56 bits
get_n_rand_bits_alt() {
  local n=$1
  local nb_bytes=$(( (n+7)/8 ))
  local rnd=$(od --read-bytes=$nb_bytes --address-radix=n --format=uL /dev/urandom | tr --delete " ")
  echo $(( rnd>>(nb_bytes*8-n) ))
}

# for parameter max, generates an integer in the range {0..max} uniformly at random
# max can be an arbitrary integer, needs not be a power of 2
rand() {
  local rnd max=$1
  # get number of bits needed to represent $max
  local bitlen=$(log2 $((max+1)))
  while
    # could use get_n_rand_bits_alt instead if /dev/urandom is preferred over $RANDOM
    rnd=$(get_n_rand_bits $bitlen)
    (( rnd > max ))
  do :
  done
  echo $rnd
}

# MAIN SCRIPT

# check number of parameters
if (( $# != 1 && $# != 2 ))
then
  cat <<EOF 1>&2
Usage: $(basename $0) [min] max

Returns an integer distributed uniformly at random in the range {min..max}
min defaults to 0
(max - min) can be up to 2**60-1  
EOF
  exit 1
fi

# If we have one parameter, set min to 0 and max to $1
# If we have two parameters, set min to $1 and max to $2
max=0
while (( $# > 0 ))
do
  min=$max
  max=$1
  shift
done

# ensure that min <= max
if (( min > max ))
then
  echo "$(basename $0): error: min is greater than max" 1>&2
  exit 1
fi

# need absolute value of diff since min (and also max) may be negative
diff=$((max-min)) && diff=${diff#-}

echo $(( $(rand $diff) + min ))

将其保存到后~/bin/rand，您将可以在bash中使用一个甜美的随机函数，该函数可以在给定的任意范围内对整数进行采样。该范围可以包含负整数和正整数，并且长度最多可以为2 ⁶⁰ -1：

$ rand 
Usage: rand [min] max

Returns an integer distributed uniformly at random in the range {min..max}
min defaults to 0
(max - min) can be up to 2**60-1  
$ rand 1 10
9
$ rand -43543 -124
-15757
$ rand -3 3
1
$ for i in {0..9}; do rand $((2**60-1)); done
777148045699177620
456074454250332606
95080022501817128
993412753202315192
527158971491831964
336543936737015986
1034537273675883580
127413814010621078
758532158881427336
924637728863691573

其他回答者的所有想法都很棒。通过这些问题的答案terdon，JF塞巴斯蒂安和jimmij使用外部工具做一个简单而有效的方式工作。但是，出于对bash的热爱，我更喜欢真正的bash解决方案，以实现最大的可移植性，也许还需要一点点；

拉梅什的和l0b0 '使用的回答/dev/urandom或/dev/random与组合od。很好，但是，他们的方法的缺点是只能对0到2 ⁸ⁿ -1的n范围内的随机整数进行采样，因为该方法对字节（即长度为8的位串）进行采样。增加

最后，法尔科（Falco）的答案描述了如何在任意范围（不仅是2的幂）上完成此操作的一般想法。基本上，对于给定范围{0..max}，我们可以确定2的下一个幂是多少，即，确切地需要多少位才能表示max为位串。然后，我们可以采样那么多的位，并查看此双串（作为整数）是否大于max。如果是这样，请重复。由于我们采样的位数与表示所需的位数相同max，因此每次迭代的概率都大于或等于成功的50％（在最坏的情况下为50％，在最好的情况下为100％）。因此，这非常有效。

我的脚本基本上是Falco答案的具体实现，使用纯bash编写，效率很高，因为它使用bash的内置按位运算来采样所需长度的位串。此外，它还兑现了Eliah Kagan的一个想法，该想法建议$RANDOM通过将反复调用所导致的位串连接起来来使用内置变量$RANDOM。实际上，我同时实现了使用/dev/urandom和的可能性$RANDOM。默认情况下，以上脚本使用$RANDOM。（好吧，如果使用，/dev/urandom我们需要od和tr，但是它们由POSIX支持。）

那么它是怎样工作的？

在我开始之前，有两个观察：

事实证明，bash无法处理大于2 ⁶³ -1的整数。你自己看：
```
$ echo $((2**63-1))
9223372036854775807
$ echo $((2**63))
-9223372036854775808
```
看来bash在内部使用带符号的64位整数来存储整数。因此，在2 ^63处它“环绕”，我们得到一个负整数。因此，无论我们使用哪种随机函数，我们都不希望得到大于2 ⁶³ -1的范围。Bash根本无法处理它。
每当我们要样品之间的任意范围内的值min，并max有可能min != 0，我们可以简单地品尝值之间0和max-min替代，然后添加min到最终结果。即使min并且可能max是负数都可以起作用，但是我们需要注意采样一个介于0和的绝对值 之间的值max-min。因此，我们可以集中精力研究如何对介于0和之间的随机值进行采样max。其余的很容易。

步骤1：确定表示整数需要多少位（对数）

因此，对于给定的值max，我们想知道将其表示为位串需要多少位。这样一来，以后我们就可以根据需要随机地采样任意数量的位，这使得脚本非常有效。

让我们来看看。由于使用n位，我们最多可以表示2 ⁿ -1值，n因此表示任意值所需的位数x是上限（log ₂（x + 1））。因此，我们需要一个函数来计算以2为底的对数的上限。这是不言而喻的：

log2() {
  local x=$1 n=1 l=0
  while (( x>n && n>0 ))
  do
    let n*=2 l++
  done
  echo $l
}

我们需要条件，n>0以便如果条件变得太大，回绕并变为负值，则保证循环终止。

第2步：对长度为随机的比特串进行采样 n

最可移植的想法是使用/dev/urandom（或即使/dev/random有很强的理由）或bash的内置$RANDOM变量。让我们先来看看如何做$RANDOM。

选项A：使用 $RANDOM

这使用了Eliah Kagan提到的想法。基本上，由于$RANDOM对15位整数$((RANDOM<<15|RANDOM))进行采样，因此我们可以对30位整数进行采样。这意味着，将第一次调用左移$RANDOM15位，然后按位应用或第二次调用$RANDOM，有效地连接两个独立采样的位串（或至少与bash内置函数一样独立$RANDOM）。

我们可以重复此操作以获得45位或60位整数。此后bash无法处理它，但这意味着我们可以轻松地对0到2 ⁶⁰ -1之间的随机值进行采样。因此，要对n位整数进行采样，请重复此过程，直到长度以15位为步长增长的随机位串的长度大于或等于n为止。最后，我们通过向右适当的按位移位来切除过多的位，最后得到一个n位的随机整数。

get_n_rand_bits() {
  local n=$1 rnd=$RANDOM rnd_bitlen=15
  while (( rnd_bitlen < n ))
  do
    rnd=$(( rnd<<15|$RANDOM ))
    let rnd_bitlen+=15
  done
  echo $(( rnd>>(rnd_bitlen-n) ))
}

选项B：使用 /dev/urandom

另外，我们可以使用od和/dev/urandom采样一个n位整数。od它将读取字节，即长度为8的位串。与以前的方法类似，我们对这么多的字节进行采样，以使等效的采样位数大于或等于n，并切掉过多的位。

获取至少n位所需的最低字节数是大于或等于n的8的最低倍数，即floor（（n + 7）/ 8）。

最多只能使用56位整数。再采样一个字节将为我们提供一个64位整数，即bash无法处理的最大2 ⁶⁴ -1值。

get_n_rand_bits_alt() {
  local n=$1
  local nb_bytes=$(( (n+7)/8 ))
  local rnd=$(od --read-bytes=$nb_bytes --address-radix=n --format=uL /dev/urandom | tr --delete " ")
  echo $(( rnd>>(nb_bytes*8-n) ))
}

将各个部分放在一起：获得任意范围内的随机整数

我们可以品尝到n现位位串，但我们要样品整数从一个范围0到max，均匀随机，其中max可以是任意的，不一定是两个电源。（我们不能使用模数，因为这会产生偏差。）

我们之所以如此努力地采样尽可能多的位来表示该值的全部要点max是，我们现在可以安全地（有效地）使用循环来重复采样一个n-bit位串，直到我们采样一个较低的值为止。或等于max。在最坏的情况下（max是2的幂），每次迭代都以50％的概率终止，在最坏的情况下（是max2减去1的幂），第一次迭代必定终止。

rand() {
  local rnd max=$1
  # get number of bits needed to represent $max
  local bitlen=$(log2 $((max+1)))
  while
    # could use get_n_rand_bits_alt instead if /dev/urandom is preferred over $RANDOM
    rnd=$(get_n_rand_bits $bitlen)
    (( rnd > max ))
  do :
  done
  echo $rnd
}

整理东西

最后，我们要对min和之间的整数进行采样max，其中min和max可以是任意的，甚至是负数。如前所述，这现在是微不足道的。

让我们将其全部放入bash脚本中。做一些参数解析的事情...我们想要两个参数min和max，或者只有一个参数max，min默认为0。

# check number of parameters
if (( $# != 1 && $# != 2 ))
then
  cat <<EOF 1>&2
Usage: $(basename $0) [min] max

Returns an integer distributed uniformly at random in the range {min..max}
min defaults to 0
(max - min) can be up to 2**60-1  
EOF
  exit 1
fi

# If we have one parameter, set min to 0 and max to $1
# If we have two parameters, set min to $1 and max to $2
max=0
while (( $# > 0 ))
do
  min=$max
  max=$1
  shift
done

# ensure that min <= max
if (( min > max ))
then
  echo "$(basename $0): error: min is greater than max" 1>&2
  exit 1
fi

...最后，要对min和之间的一个值随机进行均匀max采样，我们对0和的绝对值之间的一个随机整数进行采样max-min，然后将其min加到最终结果中。:-)

diff=$((max-min)) && diff=${diff#-}

echo $(( $(rand $diff) + min ))

灵感来自这个，我可能会尝试使用dieharder测试和基准这个PRNG，并把我的发现这里。:-)

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。

编辑于 2021-03-9

我来说两句

0 条评论

登录后参与评论

上一篇：用于将子文件夹“提取”到父文件夹的脚本

TOP 榜单

文章