1

我有一个需要洗牌的数组，我想通过使用 Awk 来优化这个算法的速度。我对使用 Awk 还是比较陌生，我试图找出模拟这个算法的最佳方法。如何正确地做到这一点？

Bash 随机播​​放： 

 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 尝试：

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;
  }
}'
}
4

3 回答 3

1

awk 有这个rand函数，它生成一个介于 0.0 和 1.0 之间的随机数（实际上，严格小于 1.0）。要获取范围内的随机整数[0, i+1)，请使用int(rand()*(i+1)). 我不认为srand你认为它会做。srand为 awk 的随机数生成器设置“种子”，避免每次调用时生成相同的随机数序列awk。通常，种子是从经常变化的东西中设置的，比如时间——尽管这并不理想——或者从/dev/random.

几点观察：

1) 我了解您的循环

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

正试图避免由 生成的随机数中的偏差$RANDOM，因为该数字只有 16 位，因此偏差可能很明显。但是，它只会在第一次通过循环时避免偏差i+1 == size，因为limit是基于 计算的size。之后，limit将是错误的值。您可以改进计算，或者您可以使用 生成具有更多随机位的随机数/dev/urandom，但我个人只会使用该shuf实用程序，它可以执行您想要的操作（随机打乱输入）。当然，这比说教更实用。它不像编写自己的洗牌器那样具有教育意义。

2）这同样适用于awk解决方案（即，为什么awk在可以使用时使用shuf？）。但无论如何，从魔法中分配awk变量并不神奇。并且没有以任何方式链接。（而且您也不能像在 awk 脚本中那样只使用 bash 变量。）randbash$RANDOMrandawkbashlimit

于 2013-05-12T02:10:16.867 回答
0

当您希望提高速度时......“shuf”实用程序应该提供随机随机播放的首选实现，而不是使用这些方法中的任何一种。

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

如果需要考虑 shuffle 的安全性，则可以选择使用外部随机源（可能会降低执行速度）。

password=( $(printf '%s\0' "${password[@]}" | shuf -z --random-source=/dev/random | xargs -0) )
于 2015-10-24T01:35:11.887 回答
0

这是 shuffle 的 awk 实现：

文件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]
}

然后像这样调用它：awk -vvstr="$(echo {1..10000})" -f /path/to/a.awk

它没有太多优化，我将把任何事情留给你——在我的机器上，它以每 10000 条记录约 0.25 秒的速度运行。

于 2016-05-25T18:46:54.473 回答