みんなの MATLAB プログラムを見て、セクシーな書き方を知っておこう（フィボナッチ）

12332 ワード
Fibonacci コンテスト フィボナッチ数列 matlab matlab テキストリンク

プログラムコンテストをやってみました。

　年に１回、MATLAB Expo っていう集会？みたいなのがあったので、そこでコンテストをやってみました。こんな UI を作って、「好きなの解いてね」って書いて、大量のパソコンを放置！

　正解かどうかは自動採点！

採点は「シンプルなプログラム」を評価します。

　シンプルって何なのさ。

　今回は、正解かどうかと、「ノードカウント」っていうのを使ってプログラムのシンプルさを評価しました。ここにプログラムの評価をするプログラムがあります。
https://jp.mathworks.com/matlabcentral/fileexchange/34754-calculate-size

たとえば、「入力に 1 を足して出力してくださいね」っていう問題だと、以下のような感じですね。

12点
function y = plus_one(x)
      y = x+1;
end
16点
function z = plus_one(x)
      z = x;
      y = z+1;
end

点数が「低い」ほうが優秀な成績なので、上のが優秀！

※ 空白やコメントや改行やセミコロンは、ノードカウントの評価対象外なので、安心して余白を開けましょう。

色んな人の正解を見てみよう！

例えばこんな問題がありました。みんな大好きフィボナッチです。

フィボナッチ数列： 1, 1, 2, 3, 5, ...

fib(1) --> 1
fib(5) --> 5
fib(50) --> 12586269025

となるような関数

f = fib(n)

を作成せよ。

採点は、1 から 50 までの入力に対して、1 から 12586269025 が正しく出てくるかどうかを見ています。

一番多かった再帰の解答（C 言語っぽい書き方）

　教科書とかでよく見る再帰ですね。これで30点。

30点
function f = fib(n)

if n > 2
    f = fib(n-1) + fib(n-2);
else
    f = 1;
end

ただ、この書き方だと正解は出るけど計算が遅い。。
試しに時間計測。

tic
f = fib(50);
toc

経過時間は 687.018277 秒です。

11分30秒！
MATLAB だと、あんまりこういう書き方しないほうがいいね。

ループをグルグル回しちゃうパターン

　2番目に多い、FOR文とかWHILE文を使ったやつ。代表的な書き方がこれでした。

38点
function f = fib(n)

f = 0;
f1 = 0;
f2 = 1;
for x = 1:n
    f = f1 + f2;
    f2 = f1;
    f1 = f;
end

点数は再帰より悪いけど、計算は速い。

tic
for n = 1:10000
f = fib(50);
end
t = toc/10000

t =

   1.7706e-07

速すぎるから、10000 回計算させた平均値を取りましたが 0.17(μs) くらいですね。

一般式にしちゃうパターン

　丸め誤差が出るから round してますけど、計算が多いからスコアが良くない。

37点
function f = fib(n)
f = round(((0.5+sqrt(5)/2)^n - (0.5-sqrt(5)/2)^n)/sqrt(5));

　こんな式ですね。

F(n) = \frac{1}{\sqrt{5}}
\left(
\left( 
\frac{1+\sqrt{5}}{2} 
\right) ^n - 
\left( 
\frac{1-\sqrt{5}}{2}
\right) ^n 
\right)

　計算時間は 0.7 (μs) くらい。

（↑↑ 超ひさしぶりに $\TeX$ 書いた。。）

行列計算させちゃうパターン（セクシー）

　いい点数！24点！

24点
function f = fib(n)
x = [1 1;1 0]^n;
f = x(2);

　行列計算は、こういう話ですね。

   \left(
    \begin{array}{l}
      F_{n+2} \\
      F_{n+1}
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      F_{n+1} & F_n \\
      F_n & F_{n-1}
    \end{array}
  \right)
   \left(
    \begin{array}{l}
      1 \\
      1
    \end{array}
  \right)

　具体的に書くと、$F_2 = 1, F_1 = 1$ が初期値として、次の値はこうなります。

   \left(
    \begin{array}{l}
      F_3 \\
      F_2
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)
   \left(
    \begin{array}{l}
      F_2 \\
      F_1
    \end{array}
  \right)

　$F_4$ のときはこうなって、

   \left(
    \begin{array}{l}
      F_4 \\
      F_3
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)
   \left(
    \begin{array}{l}
      F_3 \\
      F_2
    \end{array}
  \right)

　つまり、$F_3, F_2$ に元の式を代入して [1 1;1 0] の２乗になると。

   \left(
    \begin{array}{l}
      F_4 \\
      F_3
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)
   \left(
    \begin{array}{l}
      F_2 \\
      F_1
    \end{array}
  \right)

　なので、大きい数に応用するとこうなるんですが、

   \left(
    \begin{array}{l}
      F_{52} \\
      F_{51}
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)^{50}
   \left(
    \begin{array}{l}
      F_2 \\
      F_1
    \end{array}
  \right)

　最初の式を見ると、真ん中の行列はこうなってるはずなので、左下の値を取ればいいですね。

   \left(
    \begin{array}{cc}
      F_{51} & F_{50} \\
      F_{50} & F_{49}
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)^{50}

　計算時間も速くて、1 (μs) くらい！

ツールボックス使っちゃうパターン（ベスト）

　ノードカウントはツールボックス関数の中身までは見ないので、Symbolic Math Toolbox を使ったやつ。

12点
function f = fib(n)
f = fibonacci(n);

　12点！関数を知ってたらこれでいいね。

　ただ、エラーチェックとか冗長なコードがあるせいか、計算時間は 0.03 秒くらいで、他のよりちょっと遅い。

いろんな人のプログラムを見るのは面白いね。

　とりあえず今のところ、ノードカウント観点でセクシーな MATLAB プログラムは、

  • あったらツールボックスを使おう。
  • 行列演算を使おう。

　ですね。あと、ここに Octave の書き方が書いてあるけど、多分こっちも行列っぽく書くといい速さになるかもね。
https://qiita.com/y_irabu/items/604b0987aa7c8ec52c65