屑俺日記

☆ シェルスクリプトでも

お決まりの階乗。shはdash。
当初expr(1)を使ったが、20!を越えると駄目なのでbc(1)に変えた。
括弧はもう少し減らせるかも。

#!/bin/sh
export BC_LINE_LENGTH=10000
foo ()
{ if [ $1 -eq 0 ]; then
    echo 1
  else 
    echo $(echo ${1}*$(foo $(echo ${1}-1|bc))|bc)
  fi ; }
 
foo $1

$ ./rec.sh 6
720
 
$ ./rec.sh 20
2432902008176640000
 
$ ./rec.sh 400
64034....途中省略....00000
 
real    0m32.553s
user    0m0.260s
sys     0m32.472s

Core i7 2.8GHz、メモリ6GBのJessieで1000!に 約4分11秒。ps a | grep -c rec の結果が2996まで届き 4GBほどメモリを喰っていたが、スワップはしなかった。

ついでに足すだけのバージョンも試す。

#!/bin/sh
export BC_LINE_LENGTH=10000
plus ()
{ if [ $1 -eq 0 ]; then 
    echo 0
  else 
    echo $(echo 1+$(plus $(echo ${1}-1|bc))|bc)
  fi ; 
}
 
plus $1

$ time sh rec3.sh 1000
1000
 
real    4m12.914s
user    0m1.544s
sys     4m7.408s

こちらも階乗と大体同様。

☆ 少し大きいの

gawkで再帰をやると、メモリがなくなるまで 喰って落ちる、ようである。

$ time awk 'function rec(num)
{ if(num==1) {return 1} 
  else { return 1 + rec(num - 1) }
}
BEGIN {print rec(2^30)+1}'                                                                
強制終了
 
real    0m35.594s
user    0m4.084s
sys     0m4.208s

free(1)で確認できた、落ちる寸前。

$ free
             total  used     free   shared  buffers  cached
Mem:       6119608  6024484  95124     716     2316   15856
-/+ buffers/cache:  6006312  13296
Swap:      2929660  2919828   9832

スワップを適当に足して、引数を少し小さくして試す。
それでもメモリを20GB程(うち15GB程がスワップ)喰っていた。

$ time awk 'function rec(num)
{ if(num==1) {return 1} 
  else { return 1 + rec(num-1) }
}
BEGIN 
{print rec(2**26)+1}'
67108865
 
real    19m51.688s
user    0m24.092s
sys     0m45.088s

☆ original-awk

Debian Stretchにて。例によって再帰の限界。
同じ計算を100回繰り返して、Segmentation faultにならなかった 回数を数える。

$ for x in `seq 100`; do original-awk 'function rec(num)
{ if(num==1) {return 1} else { return 1 + rec(num-1) }}
BEGIN {print rec(6982)}'; done | grep -c 69
85
 
$ for x in `seq 100`; do original-awk 'function rec(num)
{ if(num==1) {return 1} else { return 1 + rec(num-1) }}
BEGIN {print rec(6988)}'; done | grep -c 69
2

☆ あるexif

$ exif -m 
製造	NIKON CORPORATION
モデル	NIKON D40
Orientation	左上
X 解像度	300
Y 解像度	300
解像度の単位	インチ
ソフトウェア	Ver.1.10 
日時	2016:04:26 22:00:46
YCbCr Positioning	Co-sited
圧縮	JPEG 圧縮
X 解像度	300
Y 解像度	300
解像度の単位	インチ
YCbCr Positioning	Co-sited
露出時間	1/30 秒
F 番号	f/4.0
露出プログラム	未定義
ISO 速度評価	720
EXIF バージョン	EXIF バージョン 2.21
日時 (オリジナル)	2016:04:26 22:00:46
Date and Time (Digitized)	2016:04:26 22:00:45
コンポーネント設定	Y Cb Cr -
ピクセル毎の圧縮ビット	 2
露出バイアス	0.00 EV
Maximum Aperture Value	4.00 EV (f/4.0)
Metering Mode	パターン
光源	不明
フラッシュ	フラッシュなし、強制フラッシュ モード
フォーカス長	55.0 mm
メーカーの注釈	32226 バイトの未定義データ
ユーザーのコメント	                                    
Sub-second Time	80
Sub-second Time (Original)	80
Sub-second Time (Digitized)	80
FlashPixVersion	FlashPix バージョン 1.0
色空間	sRGB
Pixel X Dimension	1504
Pixel Y Dimension	1000
Sensing Method	1 チップの色エリア センサー
File Source	DSC
シーンの種類	Directly photographed
CFA パターン	8 バイトの未定義データ
Custom Rendered	通常処理
露出のモード	自動露出
ホワイトバランス	自動ホワイト バランス
デジタル ズーム率	 1
Focal Length in 35mm Film	82
Scene Capture Type	標準
ゲイン制御	ロー ゲインを上げる
コントラスト	通常
彩度	通常
シャープネス	通常
Subject Distance Range	不明
Interoperability Index	R98
Interoperability Version	0100
ThumbnailSize	9076