Dziękuję wszystkim za wszystkie wspaniałe odpowiedzi. Skończyło się na następującym rozwiązaniu, którym chciałbym się podzielić.
Zanim przejdę do bardziej szczegółowych informacji o tym, dlaczego i jak, oto tl; dr : mój błyszczący nowy skrypt :-)
#!/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 ))
Zapisz to ~/bin/randi masz do dyspozycji słodką losową funkcję w bash, która może próbkować liczbę całkowitą w danym arbitralnym zakresie. Zakres ten może zawierać ujemnych i dodatnich liczb całkowitych, i może wynosić do 2 60 -1 długość:
$ 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
Wszystkie pomysły innych odpowiedzi były świetne. Odpowiedzi terdon , JF Sebastian i jimmij wykorzystali narzędzia zewnętrzne do wykonania zadania w prosty i wydajny sposób. Jednak wolałem prawdziwe rozwiązanie bash dla maksymalnej przenośności, a może trochę po prostu z miłości do bash;)
Użyto odpowiedzi Ramesha i 10b0/dev/urandom lub /dev/randomw połączeniu z od. To dobrze, jednak ich podejścia miały tę wadę, że były w stanie próbkować losowe liczby całkowite w zakresie od 0 do 2 8n -1 dla niektórych n, ponieważ ta metoda próbkuje bajty, tj. Ciągi bitów o długości 8. Są to dość duże skoki z zwiększenie n.
Wreszcie odpowiedź Falco opisuje ogólną ideę, jak można to zrobić dla dowolnych zakresów (nie tylko potęg dwóch). Zasadniczo dla danego zakresu {0..max}możemy określić, jaka jest następna potęga dwóch, tj. Dokładnie, ile bitów jest wymaganych do przedstawienia maxjako ciąg bitów . Następnie możemy pobrać próbkę tylu bitów i sprawdzić, czy to dzielenie jako liczba całkowita jest większe niż max. Jeśli tak, powtórz. Ponieważ próbkujemy tyle bitów, ile potrzeba do przedstawienia max, prawdopodobieństwo każdej iteracji jest większe lub równe 50% sukcesu (50% w najgorszym przypadku, 100% w najlepszym przypadku). To jest bardzo wydajne.
Mój skrypt jest w zasadzie konkretną implementacją odpowiedzi Falco, napisaną czystym bashem i bardzo wydajną, ponieważ wykorzystuje wbudowane operacje bitowe basha do próbkowania ciągów bitów o pożądanej długości. Dodatkowo honoruje pomysł Eliasza Kagana, który sugeruje użycie wbudowanej $RANDOMzmiennej poprzez połączenie łańcuchów bitów wynikających z powtarzanych wywołań $RANDOM. W rzeczywistości wdrożyłem zarówno możliwości użycia, jak /dev/urandomi $RANDOM. Domyślnie powyższy skrypt używa $RANDOM. (I ok, jeśli korzystamy /dev/urandom, potrzebujemy od i tr , ale są one wspierane przez POSIX.)
Jak to działa?
Zanim przejdę do tego, dwie obserwacje:
Okazuje się, że bash nie obsługuje liczb całkowitych większych niż 2 63 -1. Sam zobacz:
$ echo $((2**63-1))
9223372036854775807
$ echo $((2**63))
-9223372036854775808
Wygląda na to, że bash wewnętrznie używa 64-bitowych liczb całkowitych ze znakiem do przechowywania liczb całkowitych. Więc przy 2 63 „zawija się” i otrzymujemy ujemną liczbę całkowitą. Dlatego nie możemy mieć nadziei na uzyskanie zakresu większego niż 2 63 -1 z dowolną funkcją losową, której używamy. Bash po prostu nie może tego znieść.
Ilekroć chcemy próbkować wartość w dowolnym przedziale pomiędzy mini maxewentualnie min != 0, możemy po prostu próbkować wartość pomiędzy 0i max-minzamiast, a następnie dodać mindo wyniku końcowego. Działa to nawet jeśli mini ewentualnie również maxsą ujemne , ale musimy być ostrożni, aby spróbować wartość pomiędzy 0i wartość bezwzględną max-min . Zatem możemy skupić się na tym, jak próbkować losową wartość pomiędzy 0i dowolną dodatnią liczbą całkowitą max. Reszta jest łatwa.
Krok 1: Określ, ile bitów jest potrzebnych do przedstawienia liczby całkowitej (logarytmu)
Tak więc dla danej wartości maxchcemy wiedzieć, ile bitów jest potrzebnych do przedstawienia jej jako ciągu bitów. Jest tak, że później możemy losowo próbkować tylko tyle bitów, ile potrzeba, co czyni skrypt tak wydajnym.
Zobaczmy. Ponieważ w przypadku nbitów możemy reprezentować do wartości 2 n -1, wówczas liczba nbitów potrzebna do reprezentowania dowolnej wartości xwynosi pułap (log 2 (x + 1)). Potrzebujemy więc funkcji do obliczenia pułapu logarytmu do podstawy 2. Jest to raczej oczywiste:
log2() {
local x=$1 n=1 l=0
while (( x>n && n>0 ))
do
let n*=2 l++
done
echo $l
}
Potrzebujemy warunku, n>0więc jeśli będzie on zbyt duży, owija się i staje się ujemny, pętla z pewnością się zakończy.
Krok 2: Próbkuj losowo ciąg bitów o długości n
Najbardziej przenośne pomysły to użycie /dev/urandom(lub nawet /dev/randomjeśli jest to uzasadnione) lub wbudowana $RANDOMzmienna bash . Zobaczmy, jak to zrobić w $RANDOMpierwszej kolejności.
Opcja A: Używanie $RANDOM
Wykorzystuje to pomysł wspomniany przez Eliasza Kagana. Zasadniczo, ponieważ $RANDOMpróbki 15-bitowej liczby całkowitej, możemy użyć $((RANDOM<<15|RANDOM))do próbki 30-bitowej liczby całkowitej. Oznacza to, że przesuń pierwsze wywołanie o $RANDOM15 bitów w lewo i zastosuj bitowe lub drugie wywołanie $RANDOM, skutecznie łącząc dwa niezależnie próbkowane ciągi bitów (lub przynajmniej tak niezależne, jak wbudowane bash $RANDOM).
Możemy to powtórzyć, aby uzyskać 45-bitową lub 60-bitową liczbę całkowitą. Po tym bashu nie jest już w stanie sobie z tym poradzić, ale to oznacza, że możemy łatwo próbkować losową wartość z przedziału od 0 do 2 60 -1. Tak więc, aby próbkować n-bitową liczbę całkowitą, powtarzamy procedurę, aż nasz losowy ciąg bitów, którego długość rośnie w 15-bitowych krokach, ma długość większą lub równą n. Wreszcie odcinamy za dużo bitów, odpowiednio przesuwając bitowo w prawo, i otrzymujemy losową liczbę całkowitą n-bit.
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) ))
}
Opcja B: Używanie /dev/urandom
Alternatywnie możemy użyć odi /dev/urandomwypróbować n-bitową liczbę całkowitą. ododczytuje bajty, tj. ciągi bitów o długości 8. Podobnie jak w poprzedniej metodzie, próbkujemy tyle bajtów, że równoważna liczba próbkowanych bitów jest większa lub równa n, i odcinamy za dużo bitów.
Najniższa liczba bajtów potrzebna do uzyskania co najmniej n bitów to najniższa wielokrotność liczby 8, która jest większa lub równa n, tj. Floor ((n + 7) / 8).
Działa to tylko do 56-bitowych liczb całkowitych. Próbkowanie jeszcze jednego bajtu dałoby nam 64-bitową liczbę całkowitą, tj. Wartość do 2 64 -1, której bash nie może obsłużyć.
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) ))
}
Łączenie elementów: zdobądź losowe liczby całkowite w dowolnych zakresach
Możemy nteraz próbkować -bitowe ciągi bitowe, ale chcemy próbkować liczby całkowite w zakresie od 0do max, jednolicie losowo , gdzie maxmogą być dowolne, niekoniecznie potęga dwóch. (Nie możemy używać modulo, ponieważ powoduje to stronniczość.)
Chodzi o to, że tak bardzo staraliśmy się próbkować tyle bitów, ile potrzeba do przedstawienia wartości max, że możemy teraz bezpiecznie (i wydajnie) używać pętli do wielokrotnego próbkowania nciągów bitowych, dopóki nie spróbujemy wartości niższej lub równa max. W najgorszym przypadku ( maxpotęga dwóch) każda iteracja kończy się z prawdopodobieństwem 50%, aw najlepszym przypadku ( maxpotęga dwóch minus jeden) pierwsza iteracja kończy się z pewnością.
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
}
Podsumowując
Na koniec chcemy próbkować liczby całkowite pomiędzy mini max, gdzie mini maxmogą być dowolne, a nawet ujemne. Jak wcześniej wspomniano, jest to teraz trywialne.
Umieśćmy to wszystko w skrypcie bash. Wykonaj kilka analiz składni argumentów ... Chcemy dwa argumenty mini max, lub tylko jeden argument max, mindomyślnie 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
... i wreszcie próbki równomiernie na losowej wartości w między mini max, możemy spróbować losową liczbę całkowitą między 0a wartość bezwzględną max-mini dodać mindo wyniku końcowego. :-)
diff=$((max-min)) && diff=${diff#-}
echo $(( $(rand $diff) + min ))
Zainspirowany tym , mógłbym spróbować użyć zagorzałego testera do przetestowania i przetestowania tego PRNG i umieszczenia tutaj moich wniosków. :-)