3がつ１２にち
きょうは、ちかくのレストランにいった。
となりのボックス席のおじさんたちがプログラマだったらしく、どんなコードがよいコードなのか？という話しでもり上がっていました。
そうしてしばらくすると、よいコードは
「みじかいコード」
「しょ心しゃにもわかりやすいコード」
のことだと言うけつろんにたっしていました。
ぼくはそのかいわから、なんとなくおじさんたちのつかっているモニタは小さいのかな？チームメンバーにしょ心しゃがおおいのかな？あまり計算りょうやメモリなどシビアでないのかな？とおもいました。
プログラムの良さとは？
プログラムの良さの条件は
- 計算量
- メモリ消費量
- 仕様変更に対する柔軟性
- 可読性
この全てを兼ね備えたコードというのは中々難しく、実際にはそのシステムの使われ方やハード、開発チームの構成などの条件によってこれらの要素の重要度は変わってきます。
状況によって重要度の低い項目を妥協していくことになります。
例えばメモリやCPUの制限が厳しい機器に組み込むプログラムであればメモリ消費量と計算量が少ないコードを良いコードと呼ぶと思います。
また、頻繁に仕様変更がおきるような現場では計算量やメモリ消費量を多少犠牲にしてでも柔軟性を最優先したコードになるかもしれません。
そして、チームメンバーが頻繁に変わるような開発現場では、可読性を最重視するでしょう。
というように、良いコード、悪いコードの条件は状況によって変わるのです。（という相対主義的な主張です。プロタゴラス！）
しかし巷は短いコード信者にあふれています。
が、短くてわかりやすくても条件によっては悪いコードというものが世の中には存在します。
極端な例え
さて、今回は
「短くてわかりやすくても条件によっては悪いコード」
を、みんな大好きフィボナッチ数列のN番目の数値をJavaScriptで求めるいろいろな方法を例にして考えてみます。
フィボナッチ数列とは？
まず、フィボナッチ数列とはなんのか？Wikipediaには次のようにあります。
概要
n 番目のフィボナッチ数を Fn で表すと、Fn は再帰的に
F0 = 0,
F1 = 1,
Fn + 2 = Fn + Fn + 1 (n ≧ 0)
で定義される。これは、2つの初期条件を持つ漸化式である。
この数列 (Fn)はフィボナッチ数列（フィボナッチすうれつ、（英: Fibonacci sequence）と呼ばれ、
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …（オンライン整数列大辞典の数列 A45）
と続く。最初の二項は 0, 1 であり、以後どの項もその直前の2つの項の和となっている。
引用元： Wikipedia https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0
要は、最初の二項が0,1で、以降は直前2つの数字の和の数列です。
フィボナッチ数列について語りだすと日が暮れてしまいますので、今回はこれ以上のことには触れないでおきます。
漸化式を普通にコーディングすると...
短いコード
function fib(n) {
return n == 0 ? 0 : n == 1 ? 1 : fib(n - 2) + fib(n - 1);
}
このようにそれなりに短く、可読性も悪くないコードです。
でもこのコード、計算量はかなり多いです。ブラウザで実行するとNが40を超える辺りから極端に遅くなってきます。
Nが50を超えるともう動きません。
試しに、以下の一見凡長なfor文と実効速度を比較してみます。
早いコード
let a = 0, b = 1, c;
let ans = 0;
if (N <= 0) {
ans = a;
} else if (N === 1) {
ans = b;
} else {
for (let i = 2; i <= N; i++) {
c = a + b;
a = b;
b = c;
}
ans = c;
}
console.log(ans);
Nを24とし、実行回数を１００とし、1000回の平均値を比較しました。
その結果...
for文=4.602 (µs)
再帰関数=59265.059 (µs)
と、実に10000倍ほどの遅さを記録してしまいました。
それもそのはず。フィボナッチ関数の漸化式をそのままコーディングしたファンクションの処理を丁寧に一つづつ追っていくと、何回も何回も同じ引数を持った関数が出てくることに気づくと思います。
例として、Nが５だった場合に呼ばれる関数は以下の図のようになります。
同じ関数を何度も何度も実行してしまっていて、とても無駄なことをしているのがわかります。
そこで、一度計算したことはメモしておくことにしましょう。
メモ化したもの
function fib(n) {
if (this.memo == null) {
this.memo = {}
} else if (n in this.memo) {
return this.memo[n];
}
if (n <= 0) {
return this.memo[n] = 0;
} else if (n == 1) {
return this.memo[n] = 1;
}
else {
return this.memo[n] = fib(n - 1) + fib(n - 2);
}
}
これで一度計算した値は保存して無駄に何度も同じ計算することはなくなりました。
この実効速度は60(µs)と、実に1000分の１にまで高速化することができました。
しかし、for文に負けず劣らず長くなりました。
しかも速度でもfor文に遠く及びません。
二回目以降はただキャッシュを参照するだけですので更に早くなります。
キャッシュを使うのでその分メモリ消費します。
仕様変更対応コード
また、ありえないですが、フィボナッチ数列というものの定義が偉い人によって頻繁に変えられてしまう世界でも柔軟に対応できるコードを考えてみます。
下のコードであれば、フィボナッチ数列というものの仕様が「最初が2,1,5の三項とし、
直前の値３つ分を足し合わせる」という定義になったとしても対応できます。
初期値の配列をそのままリングバッファとして使用したものです。
const ar = [0, 1];
const arSize = ar.length;
let ans;
if (N < ar.length) {
ans = ar[N];
} else {
for (let i = 2; i <= N; i++) {
let temp = 0;
for (let j = arSize; j > 0; j--) {
temp += ar[(i - j) % arSize];
}
ar[i % arSize] = temp;
}
ans = ar[N % arSize];
}
console.log(ans);
しかし、コードは長く、実行速度はもとの10倍程度になりました。
まとめ
- 良いコードは短い場合が多いが、短くても良くないコードは存在する。
- 初心者が読みやすいコードが良いコードかどうかは状況次第。