廿TT

譬如水怙牛過窓櫺 頭角四蹄都過了 因甚麼尾巴過不得

AWK で Reservoir Sampling; テキストからランダムに少数の行を抽出

R による溜池サンプリング(Reservoir Sampling)の実験 - 廿TT を踏まえて, AWK でテキストファイルからランダムに1000行非復元抽出するコードを書きました.

テスト用のデータをRで生成します.

set.seed(1)
rmixnorm3 <- function(n) {
  n1 <- round(n*0.5)
  n2 <- round(n*0.2)
  n3 <-n-(n1+n2)
  c( rnorm(n1,-3), rnorm(n2,3),rnorm(n3,9) )
}
N <-100000
n <-5000
allX <-rmixnorm3(N)
write.table(allX,file = "rmixnorm.csv",sep=",",col.names = FALSE)

ヒストグラムを書くとこのような分布です.

hist(allX,breaks = "FD")

f:id:abrahamcow:20161118014036p:plain

Reservoir Sampling を行う awk のコードは以下です.

#ReservoirSampling.awk
BEGIN {srand();}
{
	if (NR <=1000){ sample[NR] = $0;}
	else{
		j = int(rand()*NR)+1;
		if (j <= 1000) sample[j] = $0;
		}
}
END{
	for (i = 1; i <= 1000; i++) {
       	print sample[i];
       	}
}

比較対象として, ぜんぶの行を読み込んでから改めてランダムサンプリングを実行するコードも書きました.

#srs.awk
BEGIN{srand();}
{a[NR]=$0}
END{for(i=1;i<=1000;i++){x=int(rand()*NR+1);print a[x];}}

時間をはかってやると, Reservoir Sampling のほうが速いことがわかります.

$ time awk -f 'ReservoirSampling.awk' rmixnorm.csv > sub_rmixnorm.csv

real	0m0.163s
user	0m0.157s
sys	0m0.005s

$ time awk -f 'srs.awk' rmixnorm.csv > sub_rmixnorm2.csv

real	0m0.223s
user	0m0.204s
sys	0m0.010s

確認のため, ちゃんとランダムになっているか R でプロットしてみます.

sub1 <-read.csv("sub_rmixnorm.csv",header  = FALSE)
hist(sub1[,2],breaks = "FD")

f:id:abrahamcow:20161118014133p:plain

3つ山があり, 元の分布の形状を保っていることがわかります.

行番号のヒストグラムを描いてやると, 一様分布になっていることがわかります.

sub1 <-read.csv("sub_rmixnorm.csv",header  = FALSE)
hist(sub1[,1],breaks = "FD")

f:id:abrahamcow:20161118014321p:plain

以上です.

プログラミング言語AWK

プログラミング言語AWK

  • 作者: A.V.エイホ,P.J.ワインバーガー,B.W.カーニハン,足立高徳
  • 出版社/メーカー: USP研究所
  • 発売日: 2010/01/01
  • メディア: 単行本(ソフトカバー)
  • クリック: 1回
  • この商品を含むブログを見る