1

シャッフルする必要がある配列があり、Awk を使用してこのアルゴリズムの速度を最適化したいと考えています。私はまだ Awk の使用に比較的慣れていないため、このアルゴリズムをシミュレートする最良の方法を見つけようとしていました。どうすればこれを適切に行うことができますか？

バッシュシャッフル: 

 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 には、rand0.0 から 1.0 の間 (厳密には 1.0 未満) の乱数を生成する関数があります。範囲内のランダムな整数を取得するには[0, i+1)、 を使用しますint(rand()*(i+1))。私はsrandあなたが思っていることをしないと思います。srandawk の乱数ジェネレーターの「シード」を設定します。これにより、 を呼び出すたびに同じ乱数シーケンスが生成されるのを回避できますawk。通常、シードは、時間 (理想的ではありませんが) や から抽出された値など、頻繁に変更されるものから設定され/dev/randomます。

いくつかの観察：

1) 私はあなたのループを理解しています

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

によって生成される乱数の偏りを回避しようとしています。これは、乱数の数$RANDOMが 16 ビットしかないため、偏りが目立つ可能性があるためです。ただし、は に基づいて計算されているi+1 == sizeため、ループを初めて通過するときにバイアスを回避するだけです。その後、間違った値になります。計算を改善するか、を使用してよりランダムなビットで乱数を生成できますが、個人的には、必要なことを行うユーティリティを使用します (入力をランダムにシャッフルします)。もちろん、これは教訓的というよりも実用的です。独自のシャフラーを作成するほど教育的ではありません。limitsizelimit/dev/urandomshuf

2) それはソリューションにも同様に適用されawkます (つまり、使用awkできるのになぜ使用するのshufですか?)。しかし、いずれにせよ、awk変数をマジカルrandから割り当てても、マジカルにはなりません。であり、いかなる方法でもリンクされていません。(また、awk スクリプトのように bash 変数だけを使用することもできません。)bash$RANDOMrandawkbashlimit

于 2013-05-12T02:10:16.867 に答える
0

シャッフルの 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 に答える