読者です 読者をやめる 読者になる 読者になる

labunix's blog

labunixのラボUnix

シェル芸で1億までの素数抽出にかかった時間は約7分35秒でした。

■シェル芸で1億までの素数抽出にかかった時間は約735秒でした。
 コンパイル言語では無いので、まあまあ許容範囲内の速さ。

 前回は1から100までのファイルから素数では無いファイルを作成するシェル芸でした。

 「ゴールデンウイークシェル芸問題」を解いてみた。
 http://labunix.hateblo.jp/entry/20150502/1430494727

■エラトステネスの篩方式では無いのでメモリも消費しないだろうと予測。
 ちょっと気になってしまったので試してみた。

 clispで素数と素数の数を得る(1億まで)
 http://d.hatena.ne.jp/labunix/20111207

■私のPC環境は以下。クライアント用途のDebian。

$ sudo dmidecode -t processor | grep "Version"
	Version: Intel(R) Core(TM) i5-3317U CPU @ 1.70GHz

$ sudo dmidecode -t memory| grep "  Type:\| Size\|Speed:"
	Maximum Memory Module Size: 8192 MB
	Maximum Total Memory Size: 16384 MB
	Current Speed: Unknown
	Installed Size: 4096 MB (Single-bank Connection)
	Enabled Size: 4096 MB (Single-bank Connection)
	Current Speed: Unknown
	Installed Size: 4096 MB (Single-bank Connection)
	Enabled Size: 4096 MB (Single-bank Connection)
	Speed: 1600 MHz
	Configured Clock Speed: 1600 MHz
	Speed: 1600 MHz
	Configured Clock Speed: 1600 MHz

■1千万で約25秒。これはもしや。。。

$ time seq 1 10000000 | awk '{myprime = "factor | sed s/://";print $0 | myprime}' | \
  awk '(NF<3){print $1 > "prime.txt"}'

real	0m25.229s
user	0m51.299s
sys	0m4.148s

$ wc -l prime.txt 
664580 prime.txt

■1億で約735秒
 ※1は素数としてカウントしないので、素数の数は以降それぞれ1個少ない。

$ time seq 1 100000000 | awk '{myprime = "factor | sed s/://";print $0 | myprime}' | \
  awk '(NF<3){print $1 > "prime.txt"}'

real	7m35.191s
user	12m12.218s
sys	0m43.219s

$ wc -l prime.txt
5761456 prime.txt

$ du -h prime.txt
49M	prime.txt

$ awk '(NR==1){print};END{print}' prime.txt 
1
9999991

■ただのテキストにしてはサイズが大きいので、ブラウザで見るのには向いていない。
 ということでgithubに置いた。

$ wget -O prime.zip https://github.com/labunix/prime/archive/master.zip
$ zipinfo prime.zip 
Archive:  prime.zip
Zip file size: 14374929 bytes, number of entries: 3
drwx---     0.0 fat        0 bx stor 15-May-03 15:17 prime-master/
-rw----     0.0 fat        8 bx stor 15-May-03 15:17 prime-master/README.md
-rw----     0.0 fat 51099002 bx defN 15-May-03 15:17 prime-master/prime_hundred_million.txt
3 files, 51099010 bytes uncompressed, 14374439 bytes compressed:  71.9%

$ unzip prime.zip prime-master/prime_hundred_million.txt
Archive:  prime.zip
a215bd765916add75ce79dfbc4d6accb9008e064
  inflating: prime-master/prime_hundred_million.txt  

$ md5sum prime-master/prime_hundred_million.txt \
         git_working/prime/prime_hundred_million.txt 
3cd7fcae2732e23d66fa1cd92e64b8b1  prime-master/prime_hundred_million.txt
3cd7fcae2732e23d66fa1cd92e64b8b1  git_working/prime/prime_hundred_million.txt

$ awk '(NR==1){print};END{print}' prime-master/prime_hundred_million.txt 
1
99999989