毎度お馴染み、Twitterで刺激を受けてます。
さて、本年第一号は、PowerShellでフィボナッチ数列を考えてみようかと思います。 元ネタはこちら
satosystemsの日記 - [C/C++][Java][Haskell][Scheme][Lua] フィボナッチで各種言語をベンチマーク
なんというか、すごい記事でした。しかしBashがあるのに……PowerShellない。
※環境を見れば致し方ないのですが…
今回は、元記事の再帰で求めるアルゴリズムに沿ったやり方と、PowerShellでやる場合のより適した算出の2パターンです。
フィボナッチ数の漸化式
以下は元記事からの引用です。
フィボナッチ数は以下の漸化式で求められます。F0 = 0 F1 = 1 Fn+2 = Fn+1 + Fn再帰で求めるアルゴリズムは以下です。(C#のサンプル)using System; class Fib { public static int fib(int n) { if (n < 2) return n; return fib(n - 2) + fib(n - 1); } static void Main() { Console.WriteLine(fib(38)); } }
PowerShellで再帰
元ソースのやり方をPowerShellで書くと以下になります。
function fib([int]$n) {
if ($n -lt 2) { return $n }
return (fib($n -2)) + (fib($n -1))
}
fib 38
さて、肝心の実行速度は……… はい、測定不可です。 現実的に待てる程度の実行対象は30程度までです。 n=19 - 20程度まではそれなりなんですけどねー。
蛇足
function名をそれっぽくして、whileをいれて0から29まで順次実行させるとこうでしょうか… ※どんどん遅くなるのが一目瞭然ですねorz
function Get-Fib {
param(
[int]$n
)
if ($n -lt 2) { return $n }
return (fib($n -2)) + (fib($n -1))
}
$x = 0
while ($x -lt 39)
{
Get-Fib $x
$x++
}
whileなんて使うな? はい、そうですね。連番生成して、パイプで渡し、Foreach-Objectにてぐるぐる回しましょう。
function Get-Fib {
param(
[int]$n
)
if ($n -lt 2) { return $n }
return (fib($n -2)) + (fib($n -1))
}
0..38 | ForEach-Object{ Get-Fib $_ }
再帰で時間がかかる原因
これは、以下のサイトで解説している通り、再帰実行での繰り返し呼び出しに依る問題です。
ActionScript入門Wiki - 再帰処理(フィボナッチ数編)
値 関数の呼び出し回数 fibonacci(3) 5 fibonacci(5) 15 fibonacci(8) 67 fibonacci(10) 177 fibonacci(20) 21891 fibonacci(30) 2692537
最適化できないの?
それなら、n-1の実行値を保存させればいいということで、最適化を書こうかと思ったのですが……
function fib([int]$n,[int]$cur=1,[int]$prev=0) {
if ($n -eq 0) { return 0 }
if ($n -eq 1) { return $cur }
return (fib($n -1),($cur + $prev),$cur)
}
fib 10
以下のコード部分がCASTエラーではじかれ…ぐぬぬ
return (fib($n -1),($cur + $prev),$cur)
fib : パラメーター 'n' の引数変換を処理できません。"System.Object" の値を "System.Object" 型から "System.Int32" 型に変換できません。
発生場所 行:5 文字:20
+ return (fib($n -1),($cur + $prev),$cur)
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ CategoryInfo : InvalidData: (:) [fib]、ParameterBindingArgumentTransformationException
+ FullyQualifiedErrorId : ParameterArgumentTransformationError,fib
そもそも、PowerShellの再帰にはこんな制限が……
呼び出しの深さのオーバーフローのため、スクリプトが失敗しました。呼び出しの深さが 101 に達しましたが、最大値は 100 です。
PowerShellならパイプラインでしょ
さて、冷静に考えましょう。PowerShellの武器は。そう、パイプラインですね。で、さくさく書いたら出来ました.
※n=3から出力されています。
1..36 | ForEach-Object{ $i = $prev = 1 }{ $curr = $i+$prev; $i=$prev; $prev=$curr; $curr }
n=0,1,2の場合もいれろ? あ、はい。
begin{$x=0;while($x -lt 2){$x;$x++}if($x -eq 2){$x - ($x-1)}} process{1..36 | ForEach-Object{ $x = $prev = 1; }{[decimal]$curr = $x+$prev; $x = $prev; $prev = $curr; $curr}}
改行ですか…はい、すいません＞＜
begin{
$x=0
while( $x -lt 2 )
{
$x
$x++
}
if ($x -eq 2)
{
$x - ($x-1)
}
}
process{
1..137 `
| ForEach-Object { $x = $prev = 1 } {
[decimal]$curr = $x+$prev
$x = $prev
$prev = $curr
$curr
}
}
[decimal]型の最大として0..137までは出力されます。
begin{$x=0;while($x -lt 2){$x;$x++}if($x -eq 2){$x - ($x-1)}} process{1..137 | ForEach-Object{ $x = $prev = 1; }{[decimal]$curr = $x+$prev; $x=$prev; $prev=$curr; $curr}};
再帰の問題を回避しているので、0..137も一瞬で出力されます。 Measure-Commandで測定すると0.11秒でした。
#Measure-Commandで実行時間測定
begin{$x=0;while($x -lt 2){$x;$x++}if($x -eq 2){$x - ($x-1)}} process{Measure-Command{1..137 | ForEach-Object{ $x = $prev = 1; }{[decimal]$curr = $x+$prev; $x=$prev; $prev=$curr; $curr}}};
Days : 0 Hours : 0 Minutes : 0 Seconds : 0 Milliseconds : 11 Ticks : 119224 TotalDays : 1.37990740740741E-07 TotalHours : 3.31177777777778E-06 TotalMinutes : 0.000198706666666667 TotalSeconds : 0.0119224 TotalMilliseconds : 11.9224
まとめ
言語にあった求め方をしましょう。 そもそもPowerShellはJITで実行時に。
パイプラインは有効に使うと強力ですよーww
え?forってなんですかぁ??PowerShellでforを使う状況は全力で回避します。