Algorithms

2. アルゴリズム

2.1. 概要

学校のコンピュータから電卓に至るまで,今まで使ったことのあるあらゆるコンピュータ端末は,何をするにせよ「どのようにするか」を示す,アルゴリズムが使われています.アルゴリズムは,情報科学ではとても重要です.というのも,ソフトウェア開発者が効率的な,エラーのないプログラムを作る助けとなるからです.アルゴリズムについて覚えておくべき最も重要なことは,同じ問題に対してもたくさん異なるアルゴリズムがあるけれども,そのうちいくつかは残りと比べてはるかに「よい」,ということです.

コンピュータは,データを計算,移動,検索するのはとてつもなく速いです.
ところが,しばしばコンピュータが扱うデータは非常に大量になるので,コンピュータがどれだけ速いかにかかわらず,データを一つ一つ評価するのにものすごく長い時間がかかってしまうのです(たとえば,GoogleやFacebook, Twitterのような会社は,1日に10億ものデータを扱っています).ここでアルゴリズムの出番.データを処理するのによりよいアルゴリズムがコンピュータに与えられれば,チェックしないといけない情報がどれだけあっても,実用的な時間内で処理することができるようになるわけです.

「はじめに」の章を読んでいれば,コンピュータでのアプリケーションソフトの動作速度が,それを使う人間にも大きな違いを生む,ということを思い出したでしょうか.もし作ったアプリケーションが遅すぎると,人々はそれにいらいらしてしまい,使おうとしないでしょう.例えそのプログラムが全ての人生の問題を解決できようが,動作に時間がかかりすぎたら,きっと退屈してプログラムを終了させてしまう!

2.1.1. アルゴリズム,プログラム,インフォーマルインストラクション

今のところ,アルゴリズムとコンピュータプログラムは一種似たようなものだと思っているかもしれません,が,実際は非常に異なる概念です.これから,これらともう一つ重要なコンセプト「インフォーマルインストラクション(非定型指示)」の説明を行います.これらは,あることをどのように行うかを記述するためのそれぞれ異なる方法となります.

  • インフォーマルインストラクション: | 自然言語を使った指示です.厳密に正確ではないのでコンピュータは理解することができないのですが,人間はその知性をもって翻訳することができます.何かを行う時に,3つのうちで正確さがもっとも低いものです.
  • アルゴリズム: | どのように問題を解き,かつ(あるいは)作業を完了させるかを表現するステップ単位の処理であり,常にある結果が返ってきます.インフォーマル指示よりも正確であり,手順を追うのに知識や知性は必要ありません.ですが,コンピュータが手順を追うにはまだ十分正確ではありません.
  • プログラム | あるアルゴリズムの特定の実装(特定のプログラム言語で書かれたもの)であり,ある結果を与えてくれるものです.3つの表現のなかで最も正確で,コンピュータが処理を追って理解することができます.

例えば・・・

  • インフォーマル指示: | 「水を1杯取ってきて」.人間はその言葉が何を意味するか理解し,作業を成し遂げる方法を考えて導き出せますが,コンピュータはどうやってこれをやるのか全く見当も付きません!
  • アルゴリズム | 1) キッチンに行きなさい. 2) グラスを取りなさい. 3) 蛇口を開きなさい. 4) 流れ出る水の下にグラスを置き,ほぼ一杯になったらグラスを取りなさい. 5) 蛇口を閉めなさい. 6) そのグラスを持って指示を出した人の所に戻りなさい. 人間はこれらの指示を簡単に遂行できますが,コンピュータは正確に何をすればよいかはわかりません.
  • プログラム | あるプログラミング言語で書かれたコンピュータプログラムで,どのように水を取ってその水を求めた人へ持ってくるのかを正確にロボットに指示できるものです.

画像の説明

2.1.2. アルゴリズムのコスト

情報科学の学者はアルゴリズムを比較するとき,しばしばアルゴリズムの「コスト」について語ります.アルゴリズムのコストはいくつかの異なる方法で表すことができますが,入力サイズ"n"を基準としてどれだけアルゴリズムがいい性能を示すか,ということに常に関係してきます.
この節ではアルゴリズムのコストを,(アルゴリズムを処理する)プログラムの所要時間,もしくは処理終了までにアルゴリズムが行う比較回数で議論します.

アルゴリズムを実行するプログラムが完了まで費やす時間というのは,一見もっともシンプルなコスト表現のように見えます.が,実際は,たとえば使用するコンピュータの速度,記述に使ったプログラミング言語などのような,たくさんの異なる要素の影響を受けてしまいます.つまり,もしプログラムの処理時間をアルゴリズムのコスト評価に使うならば,重要なのは,異なる入力サイズのアルゴリズムをテストする場合に同じプログラム,同じコンピュータ(あるいは同速度の別のコンピュータ)を使うことです.

一方,アルゴリズムが行う比較回数は,コンピュータの速度やアルゴリズム記述に使うプログラミング言語に依存しません.様々な入力サイズに対して常に同じ比較回数のアルゴリズムもあれば,比較回数が変化するアルゴリズムもあります.

アルゴリズムのコストが専門家の世界で,「Big-O記法」でどのように表現されているかを知りたい場合は,この章の最後のまとめをチェックしましょう.

2.1.3. 検索&整列

この章では,最もよくある,かつ重要な2種類のアルゴリズム,検索(searching)と整列(sorting)を見ていきます.おそらくこれらのアルゴリズムは,コンピュータを使ってるといつも,たとえ意識してなくても(!)遭遇することでしょう.

2.2. 探索

データの集まりの中での探索は,ある意味コンピュータが常時行わなければならない処理です.Googleで検索をかけるときや,コンピュータでファイル名を入力して検索する時などで,毎回発生します.コンピュータは莫大な量のデータを扱うので,情報を即座に見つけ出す助けとなる高速なアルゴリズムが必要になります.

さて,あるゲームで探索をしてみましょう・・・

★コンテンツは準備中です★

気がついたと思いますが,このゲーム中では,たくさんのモンスターとペットがバラバラの順番に並んでいて,つまりペットを見つけるのは基本的に"運"!一番最初の試行で見つかったかもしれませんし,運が悪いとほぼ全部のプレゼント箱を調べないと見つからなかったかもしれません.ゲームでは全部の箱を調べるくらい十分な体力があるので,そんな悪いことにも見えなかったかもしれません.が,でもこれでもし箱が1000個ある,あるいは最悪100万個ある,と想像してみましょう.全部の箱を調べるのに途方もない時間がかかってしまい,ペットも決して見つかることはないでしょう.

★コンテンツは準備中です★

ゲームをクリアできた(幸いにも全ての迷子のペットを見つけた)今なら気がついたと思いますが,2番目のゲームでは1番目より少ない体力しかなく,探索すべきプレゼント箱も大量にあった,にもかかわずペットを見つけることができました.なぜこれが可能となったのでしょう?

2.2.1. 線形探索

1番目のゲームでは箱の順番がバラバラだったので,ペットを見つけるのに単に「ペットが見つかるまで一つ一つプレゼント箱を開き続ける」以外には何も戦略が使えませんでした.これは,線形探索アルゴリズム(逐次探索とも言います)に非常に似ています.平易な言葉で書けば,このアルゴリズムは以下の通りです.

  • リストの最初のアイテムが探しているものかどうかをチェックしなさい.もしそれがまさに探しているものであったら,終了.
  • そのアイテムが探しているものでなかった場合,次のアイテムに移ってチェックしなさい.
  • 探しているものが見つかるまで,各アイテムをチェックし続けなさい.

このアルゴリズムを使う場合,運良く最初に探しているものを見つけるかもしれませんが,すごく運が悪ければ,探しているものを見つけるまでにリスト内の全部を調べなければいけないかもしれません!アイテム10個のリストについては,平均では5回だけチェックすれば探すものが見つかりますが,10000個のリストだと平均で5000回チェックしなければいけません.

閑話: オマヌケ探索

章の最初にあるビデオを見ると,プレゼント探索ゲーム(1番目)でやったことは,線形探索というよりオマヌケ探索に近いと思うかもしれません.でもオマヌケ探索はもっと"オマヌケ".オマヌケ探索をやると,一つのプレゼントを開いて中身がモンスターだった時に,次のプレゼントを開く前にそのプレゼントをラッピングして戻してしまう!つまり,全く同じプレゼント箱を何度も何度も何度もチェックするはめになり,プレゼント箱が少ない場合ですらペットを全く見つけられない可能性もあるのです!

2.2.2.二分探索

こんな方法より遙かによいアルゴリズムの一つが,二分探索と呼ばれるものです.2つめのプレゼント探索ゲームでは,箱は順番になっていた(つまりペットを探す時にはるかに賢くできる)ので,もしかすると意識することなく二分探索を使っていたかもしれないですね...

各段階で二分探索を使えば,常に十分体力を残してペットを発見することができるはず!日本語で簡潔に説明するなら,二分探索アルゴリズムは以下の通りになります.

  • リストの真ん中のアイテムを見て,自分の探しているものかどうかを比較しなさい
  • もしそのアイテムが,まさに探しているものであれば,終了.
  • もしそのアイテムが,探しているものより大きい場合,リスト内でそのアイテムより大きいアイテムは全て無視できる.
    (リストが左から小さい順に並んでいるのであれば,つまり真ん中のアイテムより「右側」のアイテム全てを無視できるということ)
  • 逆にもしそのアイテムが探しているものより小さいなら,リスト内でそのアイテムより小さいアイテムは全て無視できる.
  • 後は探しているアイテムが見つかるまで,リストの残り半分に対してこのアルゴリズムを繰り返しなさい.

二分探索はとても強力なアルゴリズムです.探索対象が1000個のプレゼントの場合は,二分探索で多くても10回チェックすれば目的のものが見つかるのに対し,線形探索は最大で1000回のチェックが必要ですが,もし探索すべきプレゼントの数が2倍になったら,二分探索と線形探索によるチェック回数は,どのように変化するのでしょう?

Spoiler: How does doubling the number of boxes affect the number of checks required?
The answer to the above question is that the maximum number of checks for Linear Search would double, but the maximum number for Binary Search would only increase by one.

忘れてはいけない重要なことは,二分探索は,探索対象のアイテムが順番に整列している場合だけ有効であるということです.これはつまり,むしろ次に説明する整列アルゴリズムがより重要であるということになるのです・・・整列アルゴリズムなしには,二分探索によってデータを素早く見渡すことはできないのですから!

Project: Code to run linear and binary search for yourself
The following files will run linear and binary search in various languages; you can use them to generate random lists of values and measure how long they take to find a given value. Your project is to measure the amount of time taken as the number of items (n) increases; try drawing a graph showing this.

2.3. 整列

「整列」は,「探索」と並んでアルゴリズムの非常に重要な領域の一つです.コンピュータではしばしば大量のデータを,たいてい探索処理を容易にする目的で,そのデータの何らかの属性に従って順番に並べる必要がでてきます.例えば,大量のデータがあり,各データは名前とその人の電話番号から成り立っているとしましょう.もし誰かを名前で探索したいとすれば,最初に名前のアイウエオ順やABC順で並べ替えておくと探索の助けとなるでしょう.一方,ある特定の電話番号を探したいのであれば,データを電話番号で整列しておいた方が便利です.

探索と同様,整列アルゴリズムもたくさん異なるものが存在しますが,ある整列アルゴリズムが他のものより遙かに時間がかかることがあります.この章では,2つの遅いアルゴリズムを紹介した後で,1つ遙かに良いアルゴリズムを紹介します.

2.3.1. インタラクティブ天秤

このセクションでは,「インタラクティブ天秤」を使って,今議論しているアルゴリズムを試行できます(箱が整列できれば,音楽が流れます!).このツールを使用しているとき,天秤を使って2つの箱の比較を何回行っているか数えておいてください.2つの箱を比較するごとに,アルゴリズムが「1回の比較」を行うことになり,そのアルゴリズムでやらなければならない比較回数の合計が,8個の箱に対するそのアルゴリズムの「コスト」になるのです.

天秤を使って箱を比較して(1度に2つの箱の比較しかできません),それから画面下の地面で箱を並べ替えてください.並べ替えは,一番軽い箱が一番左端に,一番重い箱が一番右にくるようにしてください.箱を順番に並べ終わったと思ったら,"Test Order"をクリックしましょう.もし順番通りに並べられていれば,メッセージが表示されて曲が流れ出します!もし順番に並んでいなければ,箱の一部だけしかライトアップされず,メッセージも表示されず,曲全体も流れてきません.

もしあなたのパソコンでインタラクティブ天秤がうまく動かない場合,代わりに実物の天秤を使うこともできます. ・・・ただ,「一方の箱が他方より重い」だけがわかり,実際の重さはわからないことに留意してください.

★コンテンツは準備中です★

2.3.2. 選択ソート

一連の箱を,最も軽いものから順に最も重いものまで整列するのに,一番直感的に理解しやすい方法として,最初に最も軽い(もしくは最も重い)箱を見つけ,その箱を脇に置くことから始める方法があります.この方法を,インタラクティブ天秤で試してみましょう.

一番軽い箱を見つけた後は,単純に残りの箱に対して同じ手順を繰り返して2番目に軽い箱を見つけ,その箱を一番軽い箱の隣りに置きましょう.この手順を繰り返し続けることで,やがてそれぞれの箱が順番に並んだ状態で置かれることになります.インタラクティブ天秤にて,この方法を使って箱全部を順番に整列する作業を行い,何回の比較をしなければいけないかをカウントしてみましょう.

コツ: 最初に全部の箱を画面の右側に移動させましょう.その後一番軽い箱を見つけたら,それを一番左端に置きましょう(逆に一番重いものを最初に見つけたい場合は,全部の箱をまず左端に集めておきましょう).

次に軽い箱を見つけるのに必要となる毎回の比較回数を記録していくと,あるパターンに気づくことでしょう(ヒント:一番軽い箱を見つけるには7回の比較が必要,次に2番目に軽い箱を見つけるのには6回の比較が必要,...).もしこのパターンがわかれば,次は9個の箱を並べ替えるのに,何回の比較が必要になるでしょうか?20個の時は?1000個の箱の整列に必要な比較回数もわかるなら,代わりに1001個を整列する場合には何回余分に比較を行うことになる?

このアルゴリズムは,選択ソートといいます.この名前は,毎回全体をチェックして次の最も軽い箱を「選択」し,それを正しい位置に置くということから来ています.

選択ソートアルゴリズムを記述すると以下の通りです.

  • リスト内で最も小さいアイテムを見つけ,脇に置きなさい.これが整列済みリストになります.
  • 次に,リストの残りの中で一番小さいアイテムを見つけ,そこから取り出して,先に整列済みリストに置いたアイテムの横に置きなさい.
  • この作業を,全アイテムを選択して整列済みの正しい場所に移動させ終わるまで繰り返しなさい.

「最も小さい」という言葉を「最も大きい」に置き換えても,このアルゴリズムはうまく動きます.毎回一貫していれば,最も小さい方と最も大きい方どちらを探すかは特に問題ではありません.

2.3.3. 挿入ソート

このアルゴリズムは,それぞれの箱を元のグループから取り除き,新しい整列済みグループの正しい場所に挿入するものです.選択ソートと同様,挿入ソートは非常に直感的で,多くの人が自分で何かものを整列する,例えば手の中でカードを整列する時などによく使う手法です.

このアルゴリズムをインタラクティブ天秤で試してみましょう.まず全ての箱を画面の片側に集めます - これが元の"未整列"グループになります.では,適当に一つ箱を選んでそれを画面のもう一方の片側に置きましょう - これが整列済みグループの始点になります.

次の箱を整列済グループに挿入するときは,整列済グループ内に既にある箱と比較し,2つの箱を正しい順番に並べ替えましょう.次の箱を加える時には,これらの箱(箱の重さによっては1個だけ)と比較し,3つの箱を正しい順番に並べ替えましょう.この箱挿入作業を,整列済グループが完成するまで続けましょう.何回比較しなければならなかったか数えるのをお忘れ無く!

このアルゴリズムは「挿入ソート」と呼びます.このアルゴリズムの考え方を理解できたかどうかまだ自信が無い人は,Wikipediaの英語版「挿入ソート」ページにある,こちらのアニメーションをご覧下さい.

挿入ソートをinformal instructionsで表現すると以下の通りです.

  • 未整列リストからアイテムを取り,端に置きなさい.これが整列済リストになります.
  • 一つずつ,未整列リストからアイテムを取り,整列済リスト内の正しい位置にそのアイテムを挿入しなさい.
  • これを全てのアイテムが整列された状態になるまで続けなさい.

これは,物理的にアイテムを並べる時によくやる方法です.さらに,もし既に整列されたデータセットを持っていて,新しいデータをそのセットに追加したいときには,とても有用なアルゴリズムです.例えば,あなたが書斎を持っていて,新しい本を買ってきた場合,その本を棚にしまうためだけに書斎全体を選択ソートしたりはせず,単に書斎の中の正しい場所へ新しい本を「挿入」するでしょう.

2.3.4. クイックソート

挿入ソートや選択ソートは,整列する方法として理に適った方法のように見えるかもしれません,が,どちらのソート法も大量のデータに対して使うと,はるかに膨大な比較作業を行うハメになります.思い出してください.コンピュータはしばしば,莫大な量のデータを検索しなければならないのです.なので,データの探索に二分探索のような有用な探索アルゴリズムを使ったとしても,最初のデータ整列に性能の悪い整列アルゴリズムを使うと,何か探し出すのにあまりに長時間かかってしまうのです!

はるかに性能の良い整列アルゴリズムの一つが,クイックソートです!(この名前がちょっとしたネタバレですが)

★コンテンツは準備中です★

このアルゴリズムは若干複雑になりますが,とても強力です.クイックソートをインタラクティブ天秤で行う場合,まず適当に1つ箱を選んで秤の上に置きましょう.次にこの箱と他の全ての箱を比較して,もしこの箱より重ければ右の山に積み,軽ければ左の山に積みます.終わったら,他の全てと比較した最初の箱を,二つの山の間に置きましょう.

Now choose one of your piles and repeat the same process with it, choose a box from the pile and compare all the other boxes in the pile to it. This will split your pile into smaller sub piles and if you repeat this method on each pile you should eventually be left with 8 small sub piles, each of which contains only one box. The boxes should then be in sorted order!

画像の説明

このアルゴリズムを数回繰り返してみて,各回で行った比較回数を測っておくといいでしょう.というのも,時に不幸にも一番重い,あるいは一番軽い箱を最初に選ぶかもしれません.一方で,運が良ければ丁度真ん中の重さの箱を最初に選ぶかもしれません.この違いによって,比較を行う回数は変化してくるのです.

クイックソートを記述すると以下の通りです.

  • リストから一つアイテムを選び,残りのアイテムそれぞれと比較しなさい(一つ選んだアイテムを,「ピボット」とよく呼びます)
  • この「ピボット」より大きなアイテムを1つの部分集合に,小さなアイテムを別の部分集合にまとめなさい.ピボットのアイテムは,これら2つの集合の間に置きなさい.
  • 1つ部分集合を選んで,同じプロセスを繰り返しなさい.やがて各部分集合が1つだけアイテムを含む状態になるので,その時点でアイテムが整列された順番に並んでいます.

Project: Code to run selection sort and quicksort for yourself
The following files will run selection sort and quicksort in various languages; you can use them to generate random lists of values and measure how long they take to be sorted. Note how long these take for various amounts of input (n), and show it in a table or graph. You should notice that the time taken by Quicksort is quite different to that taken by selection sort.
Scratch
Python (Version 2)
Python (Version 3)

There are dozens of sorting algorithms that have been invented; most of the ones that are used in practice are based on quicksort and/or mergesort. These, and many others, can be seen in this intriguing animated video.

2.4. まとめ

この章では,アルゴリズムのごくごく一部をひもといただけで,世の中には無数の問題に対して,無数のアルゴリズムが存在します! アルゴリズムが使われているのは,数学,経路選択,ネットワーク計画&制御,問題解決,人工知能,遺伝プログラミング,コンピュータビジョン,まだまだたくさん! でもこの章を通して,アルゴリズムの肝となる概念について理解が得られたはずなので,今後より複雑な問題へも立ち向かうための十分な準備ができるでしょう.

この章では,アルゴリズムが行う比較の回数と,プログラムがかける処理時間を,アルゴリズムの「コスト」として話してきました.実際には,他にもたくさんのアルゴリズムのコスト評価の方法があります.その中に,アルゴリズムが使用するメモリ量と,アルゴリズムの計算複雑度があります.コンピュータ科学者は,アルゴリズムの性能と複雑度をより正確に表現するために,「Big-O記法」を用います.なのでアルゴリズムの性能を調べる時には,すぐにこの表記法に出会うことでしょう.Big-O記法はアルゴリズムが必要とする資源を特徴付けたもので,必要な実行時間や,時にはアルゴリズムが使用するメモリスペースに適用されます.

以下がBig-O記法の例です.

  • O(1) - O(1) 複雑度のアルゴリズムは,処理すべきデータサイズの大きさにかかわらず,常に同じ時間量で実行します.
  • O(n) - O(n)複雑度のアルゴリズムが実行に要する時間量は,処理するデータ量に正比例する形で線形増加します.Big-Oは最悪時の表現なので,場合によってはアルゴリズム実行にかかる時間がより少なくなることもありますが,取り得る最大の時間量は,与えられたデータのサイズに比例で増加します.
  • O( n2 ) - この複雑度であるアルゴリズムの性能は,入力データセットのサイズの2乗に比例します.
  • O( 2n ) - この複雑度であるアルゴリズムの時間量は,データセットに要素が1つ増える毎に2倍に増加します! この章で見てきたどのアルゴリズムがそうだったか,思い出せますか?

Big-O記法を細かく探るには少し高レベルの数学が必要になるので,この章ではあえて触れてきませんでしたが,もしもっと学びたい場合は,この下のリンク集をチェックしてみてください."複雑度と計算可能性"の章ではより深くこれらの話題を掘り下げています.

もう少し複雑なことを言えば,実際にはアルゴリズムはキャッシュメモリや仮想メモリを有するコンピュータ上で動作するので,特定の値へのアクセス速度が特に速くなったり,遅くなったりということがあります.これらの状況下においても効率的に動くことを保証するアルゴリズムも様々に存在します.これらのアルゴリズムも本章で見てきたアイデアを基礎としていますが,効果的な動作をするように若干巧みな調整を必要とします.

2.5. 参考文献

2.5.1 アルゴリズムその他の話題

  • 他にも二分探索より性能が良い探索アルゴリズムがあります.ハッシュという名前のもので,CSアンプラグドの戦艦ゲームで確認できます.
  • 良いアルゴリズムが未だ見つかっていない(そして多くの人が見つかることはないと考えている)問題がいくつかあります.そういったアルゴリズムの詳細は,フィールドガイドの「計算の複雑さと扱いやすさ」の章を見てください.

2.5.2. リンク集

powered by Quick Homepage Maker 5.1
based on PukiWiki 1.4.7 License is GPL. QHM

最新の更新 RSS  Valid XHTML 1.0 Transitional