☰

答案表

tag-icon • tag-icon bash shell-script command-line
答案表

我一直想知道什么是最好的方法好的MINbash 中的随机性，即，获得和MAX之间的随机正整数的过程是什么

  1. 该范围可以是任意大（或者至少，比如说，高达 2 32 -1）；
  2. 值均匀分布（即无偏差）；
  3. 它是有效的。

在 bash 中获得随机性的一个有效方法是使用$RANDOM变量。然而，这仅对 0 到 2 15 -1之间的值进行采样，该值可能不足以满足所有目的。人们通常使用模来使其进入他们想要的范围，例如，

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

$MAX此外，除非恰好能整除 2 15 -1=32767，否则这会产生偏差。例如，如果$MINis 0 和$MAXis 9，则值 0 到 7 的可能性比值 8 和 9 稍大，因为$RANDOM永远不会是 32768 或 32769。随着范围的增加，这种偏差会变得更糟，例如，如果$MINis 0 和$MAXis 9999，那么数字 0 到 2767 的概率为4 / 32767，而数字 2768 到 9999 的概率仅为3 / 32767。

因此，虽然上述方法满足条件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。检查结果是否超出我们的范围，如果超出，则重复。我将 while 循环的“主体”强制放入守卫中，以便本着模拟循环的精神，强制主体至少执行一次，do ... while因为rnd一开始是未定义的。

我想我在这里满足了条件 1 和 2，但现在我搞砸了条件 3。这有点慢。最多需要一秒左右（幸运的话只需十分之一秒）。实际上，循环甚至不能保证终止（尽管随着时间的增加终止概率收敛到 1）。

在 bash 中，是否有一种有效的方法可以在预先指定的且可能很大的范围内获取无偏随机整数？ （如果时间允许，我会继续调查，但与此同时，我认为这里有人可能有一个很酷的想法！）

答案表

  1. 最基本的（因此可移植的）想法是生成一个足够长的随机位串。生成随机位串的方法有多种，可以使用 bash 的内置$RANDOM变量，也可以使用odand /dev/urandom（或/dev/random）。如果随机数大于$MAX，则重新开始。

  2. 或者，可以使用外部工具。

    • Perl 解决方案
      • 优点：非常便携、简单、灵活
      • Contra：不适用于 2 32 -1以上的非常大的数字
    • Python 解决方案
      • 优点：简单、灵活，甚至适用于大量数据
      • 缺点：便携性较差
    • zsh 解决方案
      • 优点：对于使用 zsh 的人来说还是有好处的
      • 魂斗罗：可能更不便携

答案1

我看到另一个有趣的方法这里。

rand=$(openssl rand 4 | od -DAn)

这一个似乎也是一个不错的选择。它从随机设备读取 4 个字节，并将它们格式化为0和之间的无符号整数2^32-1。

rand=$(od -N 4 -t uL -An /dev/urandom | tr -d " ")

答案2

感谢大家的精彩回答。我最终得到了以下解决方案，我想与大家分享。

在我详细介绍原因和方法之前，先介绍一下太长了；博士：我闪亮的新脚本:-)

#!/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/randbash 中，您就可以在可用时获得一个甜蜜的随机函数，它可以对给定任意范围内的整数进行采样。该范围可以包含负整数和正整数，长度最大可达 2 60 -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

其他回答者的所有想法都很棒。答案由特登,JF塞巴斯蒂安， 和吉米使用外部工具以简单有效的方式完成任务。然而，我更喜欢真正的 bash 解决方案，以实现最大的可移植性，也许有一点，只是出于对 bash 的热爱;)

拉梅什'沙l0b0的答案使用/dev/urandom或/dev/random与 结合使用od。这很好，但是，他们的方法的缺点是只能对某些 n 的 0 到 2 8n -1 范围内的随机整数进行采样，因为该方法采样字节，即长度为 8 的位串。这些是相当大的跳跃增加 n.

最后，法尔科的答案描述了如何做到这一点的总体思路随意的范围（不仅仅是二的幂）。基本上，对于给定范围{0..max}，我们可以确定 2 的下一个幂是什么，即到底有多少位需要表示max为位串。然后我们可以采样那么多位，看看这个双串作为整数是否大于max。如果是这样，请重复。由于我们采样表示 所需的位数max，因此每次迭代成功的概率大于或等于 50%（最坏情况下为 50%，最好情况下为 100%）。所以这是非常有效的。

我的脚本基本上是 Falco 答案的具体实现，用纯 bash 编写，效率很高，因为它使用 bash 的内置按位运算来采样所需长度的位串。它还尊重一个想法埃利亚·卡根$RANDOM这建议通过连接重复调用产生的位串来使用内置变量$RANDOM。我实际上实现了使用/dev/urandom和 的可能性$RANDOM。默认情况下，上面的脚本使用$RANDOM. （好吧，如果使用/dev/urandom我们需要OD和t，但这些都是由 POSIX 支持的。）

那么它是怎样工作的？

在开始讨论之前，我先说两个观察结果：

  1. 事实证明 bash 无法处理大于 2 63 -1 的整数。你自己看：

    $ echo $((2**63-1))
9223372036854775807
$ echo $((2**63))
-9223372036854775808

    bash 内部似乎使用有符号 64 位整数来存储整数。因此，在 2 63处“环绕”，我们得到一个负整数。因此，无论我们使用什么随机函数，我们都不能希望获得大于 2 63 -1 的任何范围。 Bash 根本无法处理它。

  2. 每当我们想要在min和max之间的任意范围内采样可能 的值时min != 0，我们可以简单地在0和之间采样一个值max-min，然后添加min到最终结果。即使min并且也可能max是，这仍然有效消极的，但我们需要小心地对0和之间的值进行采样的绝对值 max-min。那么，我们可以专注于如何采样 和 之间的随机值0和 任意正整数max。剩下的就很容易了。

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

因此，对于给定的值max，我们想知道需要多少位才能将其表示为位串。这样稍后我们就可以仅随机采样所需数量的位，这使得脚本非常高效。

让我们来看看。由于使用n位，我们最多可以表示值 2 n -1，因此n表示任意值所需的位数x是上限（log 2 (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

这使用了主意伊利亚·卡根提到过。基本上，由于$RANDOM采样的是 15 位整数，因此我们可以用来$((RANDOM<<15|RANDOM))采样 30 位整数。这意味着，将第一次调用$RANDOM向左移动 15 位，并在第二次调用 时应用按位 or $RANDOM，有效地连接两个独立采样的位串（或至少与 bash 的内置一样独立$RANDOM）。

我们可以重复此操作以获得 45 位或 60 位整数。之后 bash 就无法再处理它了，但这意味着我们可以轻松地采样 0 到 2 60 -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 位整数，即最大为 2 64 -1 的值，这是 bash 无法处理的。

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现在可以对 -bit 位串进行采样，但我们想要采样范围从 到0的整数max，均匀随机，其中max可以是任意的，不一定是二的幂。 （我们不能使用模，因为这会产生偏差。）

我们如此努力地采样表示该值所需的位数的全部原因max是，我们现在可以安全（高效）地使用循环来重复采样n-bit 位串，直到采样到较低的值。或等于max.在最坏的情况下（max是 2 的幂），每次迭代以 50% 的概率终止，而在最好的情况下（max是 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
}

把事情包起来

最后，我们想要对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之间的随机整数，并添加到最终结果。 :-)0max-minmin

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

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

灵感来自这，我可能会尝试使用顽固分子测试和基准化这个 PRNG，并将我的发现放在这里。 :-)

答案3

可以是zsh吗？

zmodload zsh/mathfunc
max=1000
integer rnd='rand48() * max'

（对于 0 到 999 之间的随机数）

您可能还想将种子与 一起使用rand48(seed)。如果有兴趣，请参阅man zshmodules和man 3 erand48获取详细描述。

答案4

如果您想要一个号码0通过(2^n)-1在哪里n 模 8 = 0你可以简单地得到n/8来自 的字节/dev/random。例如，要获取随机数的十进制表示形式，int您可以：

od --read-bytes=4 --address-radix=n --format=u4 /dev/random | awk '{print $1}'

如果你想只拿n 位你可以先采取天花板(n / 8)字节和右移到您想要的金额。例如，如果您想要 15 位：

echo $(($(od --read-bytes=2 --address-radix=n --format=u4 /dev/random | awk '{print $1}') >> 1))

如果您绝对确定您不关心随机性的质量并且您想保证最短运行时间你可以使用/dev/urandom代替/dev/random.使用前请确保您知道自己在做什么/dev/urandom！

相关内容