tech.guitarrapc.cóm

C#, PowerShell, Unity, Cloud, Serverless Technical Update and Features

PowerShellでフィボナッチ数列してみる

毎度お馴染み、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を使う状況は全力で回避します。