株式会社リクルートスタッフィングが運営するITSTAFFINGでは、弊社に派遣登録いただいている皆さまのスキル向上を支援するイベントを、定期的に開催しています。
2018年5月30日のイベントは「話題の人気アプリの作者が登場！エンジニアだからこそ、今さら聞けないアルゴリズムの基本」を開催。
エンジニアなら誰もが耳にしたことがある「アルゴリズム」。なんとなく知ってはいるけれど、細かく学んではいないという人も多いのではないでしょうか。2018年5月現在で100万ダウンロード越えを達成、2016年のApp Store「今年のベストApp 10選」に選出されたアプリ「アルゴリズム図鑑」の作者である石田保輝さんを講師にお迎えして、楽しくアルゴリズムの基礎の基礎を教えていただきました。
■今回のイベントのポイント
・アルゴリズムとは
・具体的なアルゴリズムのご紹介
・アルゴリズムと計算量
・アルゴリズムの理論
東京在住のフリーランスエンジニア。2011年、京都大学大学院修士課程修了。いくつかのベンチャー企業を渡り歩いたのち、フリーランスとして独立。2016年、個人で制作したエンジニア向け学習アプリ「アルゴリズム図鑑」をリリース。世界100万DLを達成。「Appleの選ぶ2016年のベストアプリ」に選出される。
アルゴリズムとは
アルゴリズムとは、ある問題を解決するときの計算の厳密な手順で、例えるなら料理のレシピのようなもの。たとえばカレーを作るレシピならば、玉ねぎを炒める、肉を炒める、野菜と水を入れて煮込む、ルーを入れるという手順が一般的です。しかし、ルーを使わずスパイスを調合して本格的に作るなど、その他のレシピも存在します。同じ料理を作るにも、いくつかのレシピがあるように、アルゴリズムも、同じ問題を解決する複数のアルゴリズムがあるそうです。
また、ソート（バラバラに並んだ数字を小さい順に整列させる）や探索（多数のデータの中から目的の値に一致するデータを探す）など、さまざまな問題を解決するアルゴリズムがあるそうです。
近年ではコンピュータと人間の将棋の対戦が注目されていました。十年前はコンピュータが人間に勝てなかったのですが、今はコンピュータが圧勝しています。「これは将棋のアルゴリズムが、ここ十年で格段に進歩したからなのです」（石田さん）
具体的なアルゴリズムの紹介
ここで、アプリ「アルゴリズム図鑑」を使って、バブルソートやリスト探索のアルゴリズムをデモンストレーションしてくれました。
アプリ「アルゴリズム図鑑」は、アニメーションを使って説明が行われるため、リスト探索では線形探索と2分探索の考え方の違いだけでなく、両者の処理時間の差もよくわかりました。
次に暗号のアルゴリズムについてです。石田さんは「いるぎなえ」という文字列を示し、これはどういう意味かと問います。実は、あいうえお順に1文字ずつ前にずらすと「ありがとう」という文字列になります。昔からある「シーザー暗号」と呼ばれるアルゴリズムですが、暗号は、このように元の文に戻す（復号）方法を相手が知らなければ通用しません。
コンピュータのデータは数値なので、暗号アルゴリズムでは、ある数を別の数に変換します。このときに鍵（何らかの関数）を使います。暗号化と復号化に同じ鍵を使う暗号方式を「共通鍵暗号」と呼び、前述のシーザー暗号のほかにも、AES、DESなどのアルゴリズムが知られているそうです。
共通鍵暗号方式の課題は、鍵を相手にどう渡すかということ。ネット経由で送ると、途中で鍵そのものが盗まれてしまう危険性がありますし、（メモリカード等にコピーして）直接受け渡しするとなると、相手が手渡しできる人に限定されてしまいます。
そこで登場するのが鍵交換プロトコルや、公開鍵暗号というアルゴリズムです。公開鍵暗号は、暗号化に使う公開鍵と復号化に使う秘密鍵という、2つで一組の鍵を使います。そして、公開鍵や暗号化されたデータから、秘密鍵を割り出すことができません。
つまり、公開鍵で暗号化したデータは、秘密鍵を持つ人にしか元に戻せません。そのため公開鍵を文字通り公開し、それを使って暗号化したデータを送ってもらい、自分だけが持っている秘密鍵で復号します。公開鍵暗号方式ではRSA暗号が有名だそうです。
また、ハッシュ関数についての解説もありました。ハッシュ関数は、データを通すと元の状態が失われバラバラになり、また、どのようなデータを入力しても、出力値の桁数（ビット数）が同じになります。しかも、同じデータを入力すると同じ結果になる一方で、1ビットでも違うデータを入力すると全く違う結果になります（ただし、ごく稀に別のデータでも同じ結果になることもあるそうです）。そのため、ハッシュ値から元の状態を推測することはできません。
ハッシュ関数は、パスワードの保存やハッシュテーブル、仮想通貨のマイニングなどにも利用されているそうです。
ハッシュテーブルは「連想配列」とも呼ばれ、最新のプログラミング言語には漏れなく実装されていて、rubyならば次のように記述します。
fruit_colors = {"apple" => "red", "banana" => "yellow"}
上の例ではfruit_colorという配列で「apple」や「banana」という文字列のハッシュ値を添え字にして、色の名前を格納します。もし、同じハッシュ値になる場合は、色名をリストとして保存し、アクセス時は線形探索をするそうです。
ハッシュテーブルは、要素数が増えても、一般に、配列に比べて、速くアクセスできるという特長があるのだそうです。
アルゴリズムと計算量
「バブルソートの計算量は？」と問われたときに、何と答えれば良いでしょうか。「1秒」「1000回」「10Mバイト」という答えは、ハードウェアの処理速度やデータ量により異なるため、いずれも意味がありません。
アルゴリズムにおいては、入力量が変わると実行時間がどのように変化するかが重要で、この変化量を表すためにオーダーという考え方を用いるそうです。たとえば入力量nに対してn~2（nの2乗）に比例して実行時間が増える場合はO(n^2）と記述します。
主要なアルゴリズムの計算量は次の通りだそうです。
線形探索はO(n)で、プログラミングにおいて配列を列挙するのは線形検索と同じなので計算量はO(n)となります。ただし、これを二重ループにしてしまうとO(n^2）となり、処理がとても重くなってしまいます。
したがって大量の要素数になるプログラムでは、極力、配列の二重ループを避けるべきだそうです（意図せず二重ループになっていることもあるので、注意が必要）。
これを回避するには、前述のハッシュテーブルを使うと良いとのことです。ハッシュテーブルの計算量はO(1）で、入力量nに依存せず、定数的な処理ができるため、入力量の増加に伴って急激に処理が重くなるということはなくなります。
石田さんによれば、あらかじめnが小さいことがわかっているならば、人が見てわかりやすい、実装が単純なアルゴリズムを選ぶというのもありなので、状況に合わせて選べば良いということでした。
アルゴリズムの理論
最後に、アルゴリズムでは解けない問題や、アルゴリズムで解くのが難しい問題についても解説してくれました。
その中でも有名な「巡回セールスマン問題」では、計算量nが指数になってしまいます。「オーダーが指数になると、コンピュータで解くのは現実的でなくなる」のだそうです。
アルゴリズムという言葉はよく聞きますし、プログラミングの入門書でもほんの少しだけかじったことがあるものの、計算量がこれほど違うということを知らなかった方も多いのではないでしょうか。大規模なプログラムを開発するときには、本当に大切なことなのですね。また、アルゴリズム図鑑のアプリは、動きで説明してくれるので、とてもわかりやすいです。皆さんもダウンロードしてみてください。
