サイトアイコン 高性能計算研究室@静岡理工科大学

「効率的な手順とは?」 : 2/1 裾野高校模擬講義

1.初めに
 世の中にはいろいろな「作業」があります。楽しい作業,苦しい作業,大変な作業,楽な作業・・・傍から見ているのと実際にその作業を行ってみるのでは全く異なる感想を持つ,なんてことはよくあることです。「計算」なんてその最たるものでしょう。数学と聞くともう数式を見るのも嫌い!,という人は多いですが,小学校の時に習った四則演算(足し算,引き算,掛算,割算)であれば,楽しかったかどうかはともかく,少ない桁数の自然数どうしでしたらそれほど時間をかけることなく実行できるはずです。例えば\[2\times 2\times 2\times 2\times 2 = 2^5 = 32\]なんて計算ができないという人はまずいないでしょう。

 さて「作業」にもイロイロありますが,ここではその開始から終了までに要する「時間」を考えてみたいと思います。作業に要する時間は,どのぐらいの手間がかかるのか,つまり,その作業を行うために必要となる最も簡単かつ短時間で終わる小作業の回数をカウントすることで大体の見積もりを取ることができます。先に挙げた\(2^5\)を計算する作業は,2を掛けるという小作業を4回繰り返すことで32という結果を得て完了することができました。従って,これが\(2^6\), \(2^7\), …, \(2^n\)であっても,掛算をそれぞれ5回,6回,…, \(n\)回実行すれば,計算結果を得ることができ,作業を完了することができるわけです。

 しかしもっとこの作業を効率的にできないものでしょうか? 同じ作業を実行するにしても,初めて経験する人よりは,普通は,その作業を経験したことのある人の方が「効率的」=「短い時間で済む」=「少ない小作業の回数で済ませる」ことができますよね? それは同じ作業を繰り返すことで,「この小作業は不要,ここでこの小作業をすることで効率的になる」ということに気が付くからです。現在はどんな工場でも,どんな事務所でも,どんな会社でも,短い時間で効率的に作業を行うことが求められます。これができないとどうなるか? そう,同じ仕事量でも完了までにいたずらに時間がかかり,いつまでたっても帰れない「ブラック企業」と言われることになってしまうわけです。サービス残業させられて残業代も出ないようなら,短い時間で済ませてさっさと定時退社した方がいいですよね?

 さて,先ほど実行した\(2^n\)の計算ですが,もっと効率的に実行する方法がありますよね? そう,掛算の回数を減らすことはそんなに難しくないですよね? まぁ電卓が手元にあれば,という前提で考えてもらうと,例えば\[2^5 = (2\times 2)^2 \times 2 = 32\]という手順であれば,3回の掛算で済むことになります。\(2^6\)ですと,\[ (2\times 2)^3 = (4\times 4) \times 4 = 64\] となってこれも3回で済みます。・・・と考えていくと,一般に\(2^n\)の場合,\(n\)の2進表記が\(n = (p_k p_{k-1} \cdots p_1 p_0)_2\)であれば,\[2^n = 2^{2^k\cdot p_k} \times 2^{2^{k-1}p_{k-1}} \times \cdots \times 2^{2{p_1}}\times 2^{p_0} \]という手順で済むことが分かります。つまり\(2^{100}\)であれば,99回の掛算が必要になるところを,\(100 = (110010)_2\)より,\[ 2^{100} = 2^{2^6+2^5+2^2} = 2^{64 + 32 + 4} = 2^{64}\times 2^{32} \times 2^4 \]となり,\[ 2^{64} = (((((2^2)^2)^2)^2)^2)^2 \] ですから6回の掛算で済み,この途中結果を覚えておくとすると自動的に\(2^{32}\)と\(2^4\)が得られますので,合計8回の掛算で済むわけです。ちなみに答えは\[\begin{split} 2^{100} &= 18446744073709551616\times 4294967296\times 16\\ &= 1267650600228229401496703205376\end{split} \] となります。

 単純な掛算でも計算回数を減らすことができるわけです。これが膨大な数の掛算を行うとなると,効率的な「手順」=「アルゴリズム」を使わない手はありません。

2.ハノイの塔問題
 ではもう少しゲーム的な「作業」を行ってみましょう。アルゴリズムを考えるときには必ず題材になる有名なパズル「ハノイの塔」というものです。
 次のような積木があるとします。

 この積木を一番端の棒に移動させて下さい。但し次の条件を必ず守って下さい。

 さて,ではこの3枚のハノイの塔問題を,なるべく「効率的」に解いて下さい。

 解答は下記のYouTube動画にあります。

3.トランプの並べ替え:クイックソート
 日常的に良くある作業として「並べ替え」があります。これを効率的にできないものでしょうか?

 例えばジョーカーの入っていない52枚のトランプをスペード,クローバー,ハート,ダイヤモンドの組に分け,それぞれ番号の小さい順に並べ替える問題を考えてみます。どうすればなるべく早くに並べ替えが完了するでしょうか?

 例えば,下記のYouTube動画に示す「クイックソート」という手順は如何でしょうか?

4.おわりに
 コンピューターは人間と違って莫大なデータ量(ビッグデータ)を扱うために使用されます。従ってちょっとでも非効率的なアルゴリズムを使うと途端に膨大な時間を無駄にすることになりかねません。効率的な手順を考えることは,コンピューターを効率的に使うことにもつながります。作業が早く完了すればそれだけ電気代が節約できますからね。
 我々コンピューターの専門家はこのような「効率的」なアルゴリズムを考えることが重要な仕事の一つなのです。

モバイルバージョンを終了