アルゴリズム行進こそ至高のアルゴリズムである
NHKで大人気の教育番組「ピタゴラスイッチ」における、アルゴリズム行進やアルゴリズム体操はあまりにも有名です。知ってる人も知らない人も、まずはこの動画を見ていただきましょう。
これが実際にNHKで放送された番組中の動画です。この動画を見ていただければ、タイトルの通りであるという説明をするまでもないとは思いますが、蛇足となることを覚悟しつつ、あえて、『なぜアルゴリズム行進が至高のアルゴリズムであるか』、その一部分を説明しようかと思います。
アルゴリズム行進から見える並列処理
皆さん、コンピュータがどう動いているかはご存知でしょうか？このブログを見てくれている方はかなり詳しく理解されている方が多いかとは思いますが、そうでない方も非常に多いのではないでしょうか？ここで少し難しい話をしますが、コンピュータの頭脳である、CPUがどのような働きをしているかを解説しようと思います。
CPUの場合
CPUは、５つの部分に分かれており、一定時間ごとに１個ずつ命令を処理していきます。５つの部分の名前の役割は、Wikipediaからの引用となりますが、
- IF (Instruction Fetch) 命令を命令キャッシュから読み出す
- ID (Instruction Decode/register read) 制御信号を生成し、レジスタ・ファイルをレジスタ指定子で参照する
- EX (EXecution/address calculation) 数値の計算やロード・ストアのデータやアドレス・分岐先の計算を行う
- MA (Memory Access) ロード（メモリの読み出し）・ストア（メモリへの書き込み）を行う
- WB (Write Back) レジスタにデータを書き込む
この５つの処理を、一つ一つの命令に行う必要があります。これに対して、まず、このように命令を行わせると考えるのが普通でしょう。
| 命令＼時間 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 命令１ | IF | ID | EX | MA | WB | ||||||||||
| 命令２ | IF | ID | EX | MA | WB | ||||||||||
| 命令３ | IF | ID | EX | MA | WB |
このように順番に処理をしていけば、確実に処理することが出来ます。ですが、このような方法で処理を行うと、命令１〜３までの３つの命令を行うだけで、１５回分の時間がかかってしまいます。それでは、次のように処理するとどうでしょう？
| 命令＼時間 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 命令１ | IF | ID | EX | MA | WB | ||
| 命令２ | IF | ID | EX | MA | WB | ||
| 命令３ | IF | ID | EX | MA | WB |
このように処理をしてみたらどうでしょう？また、表を見てもらえれば判るとおり、同じ時間に同じ部分を使ってはいないので大丈夫です。先程１５回分の時間がかかってしまっていたものを、なんと７回分の時間で処理してしまうことができます。このように、並列に処理をすることによって、見事に処理を高速化することができ、この処理をパイプライン処理と呼びます。ただし、実際の場面では、この５つの部分が完全に分かれているわけではなく、同じパーツやメモリを使わなくてはならない、といった問題が発生し、ここまで綺麗に実行できることは稀です。
アルゴリズム行進の場合
さて、アルゴリズム行進の場合はどうでしょう？もう読者の方は、この当たりでニヤリとしている人が殆どでしょう？アルゴリズム行進は、以下のようなパーツで構成されています。
- 一歩進んで 前ならえ
- 一歩進んで えらい人
- ひっくりかえって ぺこりんこ
- よこにあるいて きょろ きょろ
- ちょっと ここらで ひらおよぎ
- ちょっと しゃがんで 栗ひろい
- 空気いれます シュウ シュウ
- 空気が入って ピュウ ピュウ
さて、もはや表にすることもないと思いますが、表にしてみましょう！
| 人＼時間 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 人１ | 前ならえ | えらい人 | ぺこりんこ | きょろきょろ | 栗拾い | シュウシュウ | ピュウピュウ | 前ならえ | えらい人 | ぺこりんこ | きょろきょろ | 栗拾い | シュウシュウ | ピュウピュウ |
| 人２ | 前ならえ | えらい人 | ぺこりんこ | きょろきょろ | 栗拾い | シュウシュウ | ピュウピュウ | 前ならえ | えらい人 | ぺこりんこ | きょろきょろ | 栗拾い | シュウシュウ | |
| 人３ | 前ならえ | えらい人 | ぺこりんこ | きょろきょろ | 栗拾い | シュウシュウ | ピュウピュウ | 前ならえ | えらい人 | ぺこりんこ | きょろきょろ | 栗拾い | ||
| 人４ | 前ならえ | えらい人 | ぺこりんこ | きょろきょろ | 栗拾い | シュウシュウ | ピュウピュウ | 前ならえ | えらい人 | ぺこりんこ | きょろきょろ | |||
| 人５ | 前ならえ | えらい人 | ぺこりんこ | きょろきょろ | 栗拾い | シュウシュウ | ピュウピュウ | 前ならえ | えらい人 | ぺこりんこ | ||||
| 人６ | 前ならえ | えらい人 | ぺこりんこ | きょろきょろ | 栗拾い | シュウシュウ | ピュウピュウ | 前ならえ | えらい人 | |||||
| 人７ | 前ならえ | えらい人 | ぺこりんこ | きょろきょろ | 栗拾い | シュウシュウ | ピュウピュウ | 前ならえ |
さて、先程のパイプライン処理を行われていることは明らかでしょう。しかも、これらの行動は、一つ一つが独立しているわけではなく、他の領域まで割り込んで処理を行う癖に、常に完璧に、全く行進を止めることがなく続けられます。これを見るだけで、アルゴリズム行進がいかに優れたアルゴリズムであるか、というものが判ってもらえるかと思います。これ以外にも様々な要素が詰め込まれているのですが、あまり説明が長くなりすぎても良くないので、これくらいにしておこうかと思います。
広がり続けるアルゴリズム
皆さんご存知のように、アルゴリズム行進は、非常に優れたアルゴリズムであるからこのように広がったのではありません。このように素晴らしいアルゴリズムでありながら、子供にも親しみやすい形に仕上がっているからこそ、広がっているのではないでしょうか？フィリピンの刑務所でアルゴリズム行進が行われているのはあまりにも有名ですし、情報オリンピックでアルゴリズム行進が大流行したという噂も耳にします。ですが、「アルゴリズム」という単語がどういった意味であるかご存知でしょうか？「アルゴリズムって何？」って聞かれた際に、貴方は答えられますか？答えられる人は少ないのではないかと思います。アルゴリズム行進というのは、アルゴリズムの面白さを非常にコミカルな形で伝えておきながら、アルゴリズムが何であるかに触れていないのです。アルゴリズム行進が楽しいと感じた方は、アルゴリズムとは一体何であるか気になったでしょう？きっと貴方は、今すぐbingの検索窓に「アルゴリズム」と打ち込みたくなってしまっているでしょう。だけど、それは少し待ってください。それで検索して、納得してしまっては詰まりません。貴方は、辞書を引いてその単語の意味を知った上で、「面白い」「笑いが止まらない」「魅了された」といった経験をしたことがありますか？恐らくないと思いますし、それではアルゴリズムの楽しさはわかりません。それは機会損失であり、非常に勿体無い行為です。
ではどうすれば良いのでしょうか？答えは簡単です。最強最速アルゴリズマー養成講座を読めば良いのです。そして、コンテストに参加してみれば良いのです。アルゴリズムのかけらに触れ、それを感じた貴方は、アルゴリズムを使いこなし、問題を次々と解決していくことに、きっと今まで味わったことのない快感を味わうことが出来るでしょう。
さあ、貴方も、アルゴリズマーになってみませんか？プログラミングコンテストでお待ちしています。
