March 15, 2016

アルゴリズムを、はじめよう

posted at 2016.3.14

伊藤静香
インプレス
売り上げランキング: 12988

いやー、なんで今までこれを買わなかったんだろうと思うほどよかった。というか、今の自分に必要な1冊だった。

自分はエンジニアのバックグラウンドがないまま、Webフロントエンド開発でJavaScriptを書いている。アルゴリズムってなんじゃい！って自分だったが、バンクーバーで就活していた時、Webテストとかさせられたのだけど、こうゆうアルゴリズムというか数学的な問題が出るとさっぱりでお手上げだった。そうゆう自分にさよならバイバイしたかったので、いっちゃん易しそうなやつ買ってみたのだった。

例えば、配列の中から最大値を求めるアルゴリズムについて考えてみよう。

_.max([4, 2, 8, 6]); // → 8

Lodash/Underscoreが使えれば、一発だよねー。でもそれが使えなかったら？

Math.max.apply(null, [4, 2, 8, 6]); // → 8

Math.maxメソッドで一発だよねー。でも、それが思い浮かばなかったら？

var array = [4, 2, 8, 6];
var max = array[0];
array.forEach((value) => {
    if(max < value) {
        max = value;
    }
});
console.log(max); // → 8

こんなかんじ？forEachも使えないとしたら？

// JavaScript
var array = [4, 2, 8, 6];
var max = array[0];
for (var i = 0; i < array.length; i++) {
    if(max < array[i]) {
        max = array[i];
    }
}
console.log(max); // → 8

ここまでくると、すごくプリミティブなコードになったので、

# Ruby
array = [4, 2, 8, 6]
max = array[0]
for value in array do
    if max < value then
        max = value
    end
end
puts max # → 8

// golang
package main

import "fmt"

func main() {
    array := []int{4, 2, 8, 6}
    max := array[0]
    for i := 0; i < len(array); i++ {
        if max < array[i] {
            max = array[i]
        }
    }
    fmt.Print(max) // → 8
}

他の言語に置き換えても大差ない。てか、ほぼ、擬似言語だ。

要は、

先頭の要素を暫定チャンピオンとして変数maxに代入する
次の要素と比較し大きければmaxに代入する、小さければスルー
2.を繰り返し

こうゆうことを理解しているのか？という問題。事実、前に「一番近い座標をもとめろ」的な問題をといた時に、こうゆうの必要だったなぁと思い出にふける。よく分からないまま、StackOverflowで似たような質問さがして、コピペ・改変して、案の定、落ちたけど。

とにかく、アルゴリズムを学ぶってこうゆうことなんだと理解した気がする。ちょっと前まで、エンジニアさんが、プログラミング言語何でも書けますよー！って人を理解できなくて、なんだよ新人類か！、神か！と思ってたけど、プログラミング言語が書けるってのはすべてのメソッド名を覚えるってことではないんだよなと。

言語毎に有名なライブラリやフレームワークの使い方まで覚えていたらそりゃすげーと思うけど、基本的なアルゴリズムを理解して、繰り返し処理と条件分岐さえできれば、あとはなんとか書けるんだよなって理解した。

最大値を求めるアルゴリズム自体は肩慣らし程度で、本書では以下の9つのアルゴリズムに関して解説している。

線形探索法（リニアサーチ）
二分探索法（バイナリサーチ）
ハッシュ探索法
単純選択法（選択ソート）
単純交換法（バブルソート）
単純挿入法（挿入ソート）
クイックソート
エラトステネスのふるい（素数を求めるアルゴリズム）
ユークリッドの互除法（最大公約数を求めるアルゴリズム）

ソートとかArray.prototype.sort()使えるじゃんと思いつつも、ちゃんと書けるようになりたいものだと思った。

僕みたいなデザイナー上がりのへっぽこデベロッパーにとっても非常にわかりやすくて、挫折しないで読めた。ほかのアルゴリズムの本は難しそうだし、このレベルでもう何冊か読んでみたいと思った。