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

马尔特·斯科鲁帕(Malte Skoruppa)

我一直在想这将是获得最佳的方式很好在bash,即随机性,这将是一个过程,以获得之间的随机正整数MIN,并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相除。例如,如果$MIN为0且$MAX为9,则值0到7比值8和9更有可能,因为$RANDOM永远不会是32768或32769。随着范围的增加,此偏差会变得更糟,例如,如果$MIN为0且$MAX为9999,然后通过2767数字0具有的概率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则为空,因此在这种情况下设置rnd0检查结果是否超出我们的范围,如果超过,请重复。我本着模仿do ... while循环的精神,将while循环的“ body”强制进入了后卫,以强制至少执行一次body ,因为从rnd开始就没有定义。

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

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

答案表

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

  2. 另外,也可以使用外部工具。

    • Perl解决方案
      • 优点:非常轻便,简单,灵活
      • 相反:不适用于2 32 -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 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

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

拉梅什的和l0b0 '使用的回答/dev/urandom/dev/random与组合od很好,但是,他们的方法的缺点是只能对0到2 8n -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我们需要odtr,但是它们由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,我们可以简单地品尝值之间0max-min替代,然后添加min到最终结果。即使min并且可能max负数可以起作用,但是我们需要注意采样一个介于0之间的值 max-min因此,我们可以集中精力研究如何对介于0之间的随机值进行采样max其余的很容易。

步骤1:确定表示整数需要多少位(对数)

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

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

这使用了Eliah Kagan提到想法基本上,由于$RANDOM对15位整数$((RANDOM<<15|RANDOM))进行采样,因此我们可以对30位整数进行采样。这意味着,将第一次调用左移$RANDOM15位,然后按位或第二次调用$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位整数,即bash无法处理的最大2 64 -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现位位串,但我们要样品整数从一个范围0max均匀随机,其中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,其中minmax可以是任意的,甚至是负数。如前所述,这现在是微不足道的。

让我们将其全部放入bash脚本中。做一些参数解析的事情...我们想要两个参数minmax,或者只有一个参数maxmin默认为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] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

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

来自分类Dev

生成具有非均匀分布的随机整数

来自分类Dev

如何生成均匀分布的整数序列?

来自分类Dev

如何生成均匀分布的整数序列?

来自分类Dev

如何更有效地生成大量HTML

来自分类Dev

在C中生成随机,均匀分布的实数

来自分类Dev

如何有效地生成一组具有预定义分布的唯一随机数?

来自分类Dev

有效地在Rcpp中生成随机位流

来自分类Dev

如何在python中生成独立的均匀分布(iid)随机变量

来自分类Dev

从多元正态分布有效地随机抽取

来自分类Dev

生成强连通的,均匀分布的随机有向图

来自分类Dev

有效地生成不同的随机数

来自分类Dev

如何使用OpenMP在C代码中生成介于0和1之间的均匀分布的随机数?

来自分类Dev

如何有效地随机播放位?

来自分类Dev

如何有效地进行多次随机试验?

来自分类Dev

随机均匀分布

来自分类Dev

随机均匀分布

来自分类Dev

如何有效地找到最小的正整数?

来自分类Dev

通过均匀分布的RNG生成3个不同的随机整数

来自分类Dev

使用 cuRand 从均匀分布生成随机整数的正确方法是什么?

来自分类Dev

在具有给定属性的matlab中生成均匀分布的延迟

来自分类Dev

生成具有均匀分布的随机数(循环获得相同的数)

来自分类Dev

随机生成ID并有效地将其持久化在Java中

来自分类Dev

有效地生成一个范围内的随机素数

来自分类Dev

如何有效地语法

来自分类Dev

C ++线程安全的均匀分布随机数生成

来自分类Dev

从均匀分布生成伪随机数

来自分类Dev

在圆角矩形内生成均匀分布的随机位置

来自分类Dev

快速均匀分布随机数生成器

Related 相关文章

热门标签

归档