プログラムコンテストをやってみました。
年に１回、MATLAB Expo っていう集会？みたいなのがあったので、そこでコンテストをやってみました。こんな UI を作って、「好きなの解いてね」って書いて、大量のパソコンを放置！
正解かどうかは自動採点！
採点は「シンプルなプログラム」を評価します。
シンプルって何なのさ。
今回は、正解かどうかと、「ノードカウント」っていうのを使ってプログラムのシンプルさを評価しました。ここにプログラムの評価をするプログラムがあります。
https://jp.mathworks.com/matlabcentral/fileexchange/34754-calculate-size
たとえば、「入力に 1 を足して出力してくださいね」っていう問題だと、以下のような感じですね。
function y = plus_one(x)
y = x+1;
end
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点。
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文を使ったやつ。代表的な書き方がこれでした。
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 してますけど、計算が多いからスコアが良くない。
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点！
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 を使ったやつ。
function f = fib(n)
f = fibonacci(n);
12点！関数を知ってたらこれでいいね。
ただ、エラーチェックとか冗長なコードがあるせいか、計算時間は 0.03 秒くらいで、他のよりちょっと遅い。
いろんな人のプログラムを見るのは面白いね。
とりあえず今のところ、ノードカウント観点でセクシーな MATLAB プログラムは、
- あったらツールボックスを使おう。
- 行列演算を使おう。
ですね。あと、ここに Octave の書き方が書いてあるけど、多分こっちも行列っぽく書くといい速さになるかもね。
https://qiita.com/y_irabu/items/604b0987aa7c8ec52c65