Tasowanie z Awk - linux, algorytm, bash, shell, awk

Mam tablicę, którą należy przetasować, a jachciałby zoptymalizować szybkość tego algorytmu, używając Awk. Nadal jestem stosunkowo nowy w używaniu Awka i próbowałem wymyślić najlepszy sposób symulowania tego algorytmu. Jak można to właściwie zrobić?

Bash Shuffle:

 shuffle() {

local size limit rand i

size=${#password[*]}
limit=$(( 32768 / size * size))

for ((i=size-1; i > 0; i--)); do
while (((rand=$RANDOM) >= limit)); do :; done
rand=$((rand % (i+1)))
tmp=${password[i]}
password[i]=${password[rand]}
password[rand]=$tmp
done
}

Awk Attempt:

shuffle() {

local size limit rand i

size=${#password[*]}
limit=$(( 32768 / size * size))

awk -v rand=$RANDOM "BEGIN {
srand(rand);
for(i=size-1; i>0; i--) {
while(rand >= limit);
rand=rand % i + 1;
tmp=password[i];
password[i]=password[rand];
password[rand]=tmp;
}
}"
}

Odpowiedzi:

1 dla odpowiedzi № 1

awk ma rand funkcja, która generuje losową liczbę od 0,0 do 1,0 (właściwie dokładnie mniej niż 1,0). Aby uzyskać losową liczbę całkowitą w zakresie [0, i+1), posługiwać się int(rand()*(i+1)). Nie myślę srand robi to, co myślisz; srand ustawia „seed” dla generatora liczb losowych awk, który unika generowania tej samej sekwencji liczb losowych przy każdym wywołaniu awk. Zwykle ziarno jest ustawiane z czegoś, co często się zmienia, jak czas - choć to nie jest idealne - lub wartość wydobyta z /dev/random.

Kilka obserwacji:

1) Rozumiem, że twoja pętla

while (((rand=$RANDOM) >= limit)); do :; done

próbuje uniknąć stronniczości w losowej liczbie generowanej przez $RANDOM, ponieważ liczba ta ma tylko 16 bitów, a więc obciążenie może być zauważalne. Jednak uniknie uprzedzeń tylko po raz pierwszy w pętli, kiedy i+1 == size, od limit został obliczony na podstawie size. Po tym, limit będzie złą wartością. Możesz poprawić obliczenia lub wygenerować losową liczbę z większą liczbą losowych bitów, używając /dev/urandom, ale osobiście używam shuf narzędzie, które robi to, co chcesz (losowo tasuje wejście). Oczywiście jest to bardziej pragmatyczne niż dydaktyczne; nie jest tak edukacyjne, jak pisanie własnego tasowania.

2) Dotyczy to również awk rozwiązanie (tj. dlaczego używać awk kiedy możesz użyć shuf?). Ale w każdym razie przypisanie awk zmienna rand z bash magiczny $RANDOM nie robi rand magiczny. awk i bash nie są połączone w żaden sposób. (I nie możesz po prostu używać zmiennych bash takich jak limit w skrypcie awk.)

---

0 dla odpowiedzi nr 2

Jak chcesz zwiększyć szybkość ... Zamiast używać jednego z tych podejść, narzędzie „shuf” powinno zapewniać preferowaną implementację losowego losowania.

password=( $(printf "%s" "${password[@]}" | shuf -z | xargs -0) )

Jeśli bezpieczeństwo shuffle jest problemem, użycie zewnętrznego losowego źródła jest opcjonalne (z możliwym kosztem szybkości wykonania).

password=( $(printf "%s" "${password[@]}" | shuf -z --random-source=/dev/random | xargs -0) )

---

0 dla odpowiedzi № 3

Oto implementacja tasowania w awk:

Plik a.awk:

function get_rand(max) {
return int(rand()*max)
}

function get_array_length(a) {
k=0
for( i in a) k++
return k
}

function arr2str(a) {
astr=""
for(i in a)
astr=((astr)(a[i])" ")
return astr
}

function shuffle_array(in_array) {
array_size=get_array_length(in_array);
## Initialize the random indexing array
for (i=1;i<=array_size;i++)
rand_select[i]=in_array[i]
ridsz=array_size
for(i=1;i<=array_size;i++) {
ridx=get_rand(ridsz)+1;
newarr[i]=rand_select[ridx];
rand_select[ridx]=rand_select[ridsz] ## Move last element, preserve indx
delete rand_select[ridsz];
ridsz--;
}
return arr2str(newarr);
}

BEGIN {
"date +%N"|getline rseed;
srand(rseed);
close("date +%N");
split(vstr, varr, " ");
split(shuffle_array(varr),shuf_varr, " ");
for (element in shuf_varr)
print "got:",shuf_varr[element]
}

Następnie nazwij to tak: awk -vvstr="$(echo {1..10000})" -f /path/to/a.awk

„Nie jest zbyt zoptymalizowany, pozostawiam wszystko w tobie - na mojej maszynie działa on w ~ 0,25 sekundy na 10000 rekordów.

---