Как эффективно генерировать большие, равномерно распределенные, случайные целые числа в ударе?

Или, найдите свои файлы и извлеките имена каталогов оптом:

find starting_directory –name level.dat –print | sed 's@/level.dat$@@'

30
13.04.2017, 15:36
8 ответов

Спасибо всем за прекрасные ответы. В итоге я получил следующее решение, которым я хотел бы поделиться.

Прежде чем я углублюсь в подробности того, почему и как, вот 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

Все идеи других респондентов были великолепны. Ответы тердона , J.F. Себастьян и jimmij использовали внешние инструменты для простого и эффективного выполнения задачи. Однако я предпочел истинное решение bash для максимальной переносимости и, возможно, немного, просто из любви к bash;)

Использовались ответы Рамеша и l0b0 / dev / urandom или / dev / random в сочетании с od . Это хорошо, однако их подходы имели недостаток, заключающийся в возможности выборки случайных целых чисел в диапазоне от 0 до 2 8n -1 для некоторого n, поскольку этот метод выбирает байты, то есть строки битов длиной 8. Это довольно большие скачки с увеличением n.

Наконец, ответ Фалько описывает общую идею, как это может быть сделано для произвольных диапазонов (не только степеней двойки). По сути, для заданного диапазона {0..max} мы можем определить следующую степень двойки, т. Е., сколько именно битов требуется для представления max в виде цепочки битов. Затем мы можем выполнить выборку именно этого количества битов и посмотреть, больше ли эта цепочка в виде целого числа, чем max . Если да, то повторите. Поскольку мы выбираем ровно столько битов, сколько требуется для представления max , каждая итерация имеет вероятность, большую или равную 50% успеха (50% в худшем случае, 100% в лучшем случае). Так что это очень эффективно.

Мой сценарий - это, по сути, конкретная реализация ответа Falco, написанная на чистом bash и очень эффективная, поскольку он использует встроенные побитовые операции bash для выборки битовых строк желаемой длины. Кроме того, он поддерживает идею Элиа Кагана , которая предлагает использовать встроенную переменную $ RANDOM путем объединения цепочек битов, полученных в результате повторных вызовов $ RANDOM . Я фактически реализовал обе возможности использования / dev / urandom и $ RANDOM . По умолчанию в приведенном выше сценарии используется $ RANDOM . (И хорошо, если используется / dev / urandom , нам нужны od и tr , но они поддерживаются POSIX.)

Итак, как это работает ?

Прежде чем я перейду к этому, два наблюдения:

  1. Оказывается, bash не может обрабатывать целые числа больше 2 63 -1. Убедитесь сами:

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

    Похоже, что bash внутренне использует 64-битные целые числа со знаком для хранения целых чисел.Итак, в 2 63 он «оборачивается», и мы получаем отрицательное целое число. Таким образом, мы не можем надеяться получить какой-либо диапазон больше 2 63 -1 с любой случайной функцией, которую мы используем. Баш просто не может с этим справиться.

  2. Если мы хотим выбрать значение в произвольном диапазоне от min до max с возможным min! = 0 , мы можем просто выбрать значение между 0 и max-min вместо этого, а затем добавьте min к окончательному результату. Это работает, даже если min и, возможно, также max имеют отрицательные , но мы должны быть осторожны, выбирая значение между 0 и абсолютное значение max-min . Итак, мы можем сосредоточиться на том, как выбрать случайное значение между 0 и произвольным положительным целым числом max . Остальное легко.

Шаг 1: Определите, сколько битов необходимо для представления целого числа (логарифм)

Итак, для данного значения max мы хотим знать, сколько битов необходимо, чтобы представить его как неприятная нить. Это сделано для того, чтобы позже мы могли случайным образом выбирать ровно столько битов, сколько необходимо, что делает сценарий настолько эффективным.

Посмотрим. Поскольку с n битами мы можем представить до значения 2 n -1, то количество n битов, необходимых для представления произвольного значения x - потолок (журнал 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 бит влево и примените побитовый вызов или второй вызов $ RANDOM , эффективно объединяя две независимо выбранные строки битов (или по крайней мере, столь же независимый, как встроенный $ RANDOM в bash).

Мы можем повторить это, чтобы получить 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 битов, является наименьшим кратным 8, которое больше или равно n, то есть пол ((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 -битовых цепочек битов, но мы хотим выбрать целые числа в диапазоне от ] 0 до max , равномерно случайно , где max может быть произвольным, не обязательно степенью двойки. (Мы не можем использовать модуль по модулю, поскольку это создает смещение.)

Весь смысл в том, что мы так старались отобрать столько битов, сколько необходимо для представления значения max , заключается в том, что мы можем теперь безопасно (и эффективно) используйте цикл для многократной выборки n -битовой строки, пока мы не выберем значение, которое меньше или равно max . В худшем случае ( max - степень двойки) каждая итерация завершается с вероятностью 50%, а в лучшем случае ( max - степень двойки минус один) , первая итерация обязательно завершится.

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 ))

Вдохновленный этим , я мог бы попробовать использовать упорнее для тестирования и тестирования этого ГПСЧ и выложить здесь свои выводы. : -)

8
27.01.2020, 19:38

Я вижу еще один интересный метод из здесь .

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

Этот тоже кажется хорошим вариантом. Он считывает 4 байта со случайного устройства и форматирует их как целое число без знака между 0 и 2 ^ 32-1 .

rand=$(od -N 4 -t uL -An /dev/urandom | tr -d " ")
17
27.01.2020, 19:38

Если вы не возражаете против использования внешних инструментов, это должно соответствовать вашим требованиям:

rand=$(perl -e 'print int(rand(2**32-1))'); 

Используется функция perl rand , которая принимает верхний предел в качестве параметра. Вы можете установить все, что захотите. Насколько это близко к истинной случайности в абстрактном математическом определении, выходит за рамки этого сайта, но это должно быть нормально, если оно вам не понадобится для чрезвычайно чувствительного шифрования или тому подобного. Возможно, даже там, но я не рискну высказывать свое мнение.

3
27.01.2020, 19:38

Если вам нужно число от 0 до (2 ^ n) -1 , где n mod 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 !

5
27.01.2020, 19:38

Может быть, zsh?

max=1000
integer rnd=$(( $(( rand48() )) * $max ))

Вы также можете использовать seed с rand48 (seed) . См. man zshmodules и man 3 erand48 для подробного описания, если это интересно.

6
27.01.2020, 19:38
$ python -c 'import random as R; print(R.randint(-3, 5**1234))'

Python доступно на Redhat, Debian на основе систем.

5
27.01.2020, 19:38

Вы должны получить ближайший (2 ^ X) -1 равную или терску, чем желаемый максимум и получить количество битов. Тогда просто вызовите / dev / случайные несколько раз и добавьте все биты вместе, пока у вас недостаточно, усеяв все биты, которые слишком много. Если полученный номер больше вашего максимального повторения. В худшем случае у вас есть больше 50% шансов получить случайное число ниже вашего максимума, так что (для этого наихудшего случая) вы получите два звонка в среднем.

2
27.01.2020, 19:38

Ваш ответ интересный, но довольно длинный.

Если вам нужны произвольно большие числа, вы можете объединить несколько случайных чисел в помощнике:

# $1 - number of 'digits' of size base
function random_helper()
{
  base=32768
  random=0
  for((i=0; i<$1; ++i)); do
    let "random+=$RANDOM*($base**$i)"
  done
  echo $random
}

Если проблема в предвзятости, просто удалите ее.

# $1 - min value wanted
# $2 - max value wanted
function random()
{
  MAX=32767
  min=$1
  max=$(($2+1))
  size=$((max-min))
  bias_range=$((MAX/size))
  while
    random=$RANDOM
  [ $((random/size)) -eq $bias_range ]; do :; done
  echo $((random%size+min))
}

Объединение этих функций вместе

# $1 - min value wanted
# $2 - max value wanted
# $3 - number of 'digits' of size base
function random()
{
  base=32768
  MAX=$((base**$3-1))
  min=$1
  max=$(($2+1))
  size=$((max-min))
  bias_range=$((MAX/size))
  while
    random=$(random_helper)
  [ $((random/size)) -eq $bias_range ]; do :; done
  echo $((random%size+min))
}
0
27.01.2020, 19:38

Теги

Похожие вопросы