概要
プログラミングを始めた当初、アルゴリズムというものが全くわかりませんでした。
マージソート？ バイナリサーチ？ クイックソート？
アルゴリズムにまつわるどんなコードと向き合ってもちっとも楽しくないし、ちっともわかりませんでした。
でも、アルゴリズムって言葉を聞いたらなんだか怖い印象がありました。難しくて、本当に頭のいいプログラマーしか使えないような印象が強かったです。
アルゴリズムってなに？
本当にその通りで、僕も同じように感じていました
しかし、ようやく最近、アルゴリズムと向き合えるようになりました。
どんなアルゴリズムも、何かしらの問題を解決するために作られています。
ランダムな数字の羅列が1万個入ったデータの中から、目的のデータを一つだけ取り出したい
データを途中で盗聴されても決してバレないようにしたい
僕たちの世界はたくさんの問題を抱えています
そして、そんなときに、アルゴリズムはとっても役に立ちます
どんなアルゴリズムを理解するに当たっても、これから紹介する２点に注目しましょう
そしたら、思いの外アルゴリズムの世界は厳しくないことがわかるかと思います
アルゴリズムとは何か？
アルゴリズム（英: algorithm [ˈælgəˌrɪðəm]）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。
Wikipedia
つまり、アルゴリズムとは問題を解くための手順ということです
より噛み砕いて説明するために、僕たちにとって、身近なアルゴリズムを出すと、
円の面積を求める公式が挙げられます
これも立派なアルゴリズムの一つです
円の面積を求める代表的な式と言えば、
円の面積 = 半径 × 半径 × π
ですね。
『素早く、なるべく正確に円の面積を求めたい！』という問題にぶつかったときに、
この問題を解くために、大昔ギリシャで生まれたのが、このアルゴリズムです。
この公式は、円の面積を求めるという問題を解くための手順です
これで少しアルゴリズムに対して、敷居が下がったのではないでしょうか？
アルゴリズムについて理解を深めるには、
■ 何が問題か、そして
■ このアルゴリズムは何を解決しているのか
の以上２点を考えると理解が進みます！
円の公式なら、
素早く、なるべく正確に円の面積を求めたい！という問題が最初にあって、
円の半径さえ、入れれば、簡単に円の面積をこのアルゴリズムは求めることができます
その他のアルゴリズムも同じように考えることができます。
まず前提として、
問題があって、
それを解決するために、アルゴリズムは存在しています。
ここから頑張っていきましょう！
アルゴリズムの種類
今回は2つの種類のアルゴリズムに絞り、次の順で説明します
■ 探索アルゴリズム
■ ソートアルゴリズム
もちろん、他にもたくさんのアルゴリズムが存在します
しかし、大学の授業の試験や、情報技術者試験の問題に出てくるようなアルゴリズムというと、この2つが代表的と言えるでしょう。
またアルゴリズムと検索すると、真っ先にソートアルゴリズムがヒットしますが、
ソートアルゴリズムについて理解するには、まず、探索アルゴリズムについて理解しないと、何のためにソートアルゴリズムが存在するのかわからなくて、全く理解できません。
なので、まず探索アルゴリズムを学び、そのあと、ソートアルゴリズムについて学びます
探索アルゴリズム
まず、覚えて欲しいアルゴリズムに探索アルゴリズムがあります。
一見難しく聞こえますが、とっても簡単です。
膨大なデータ群の中から目的のデータを探しだすアルゴリズムのことを
探索アルゴリズムと言います。
■ 線形探索アルゴリズム
まず、トランプでイメージしてみましょう
ハートのトランプが1~Kまで13枚ランダムに並べられています。
このとき、「どこにハートの7のトランプがあるか答えなさい」と聞かれたら、どうしますか？
おそらく多くの人は、カードを一枚ずつめくって、ハードの7のトランプを探すことかと思います
これをアルゴリズムの世界では、線形探索アルゴリズム(もしくは逐次探索アルゴリズム)と言います。
一枚一枚まっすぐにめくっていくことから逐次探索と呼ばれ、
途中で一枚飛ばしたり、途中からめくり始めたりせず、最初から最後まで目的のデータが見つかるまで探索を続けることから線形探索と呼ばれています。
これをプログラムに置き換えると簡単です
for文で回すだけです
# coding: utf-8
# Here your code !
def linear_search(card_list, card):
for i,element in enumerate(card_list):
if element == card:
print("{0}番目に{1}はあります".format(i+1,card))
return
print("{0}はありませんでした".format(card))
return
if __name__ == '__main__':
heart_cards = ["h-5","h-J","h-2","h-9","h-1","h-7","h-K","h-4","h-10","h-3","h-6","h-8","h-Q"]
heart_king = "h-K"
linear_search(heart_cards,heart_king)
ただし、この線形探索アルゴリズム、とっても簡単でわかりやすいですが、実際の場面においては非効率であることが多いです
今回のように、データ数が少ない場合は、問題ありませんが、データが１万、１０万、１００万と増えていったらどうでしょうか？
一つずつデータを確認していく時間が膨大になりませんか？
線形探索リストの
最大探索回数はN(Nはデータの個数分)
平均探索回数はN/2
となります。
なので、線形探索アルゴリズムだと、100万個のデータを探索するとなると、最大で100万回、平均でも50万回トランプをめくらないといけません。
とっても時間がかかりますね
■ ２分探索アルゴリズム
次に、トランプのお題を変えてみます
今度は、ハートのトランプ1~Kまでの内、10枚だけが昇順(必ず小さいものから並べられている)で並べられています。
このとき、「どこにハートの8のトランプがあるか答えなさい」と聞かれたら、どうしますか？
また線形探索しますか？
いえ、実は、データが昇順で並べられているという条件がある時のみ、僕たちはより効率的なアルゴリズムを使うことができます
それを２分探索(バイナリサーチ)アルゴリズムと言います
まずトランプの中から真ん中のトランプをめくります
すると、6が出てきました
僕たちが探し出したいトランプは8です
昇順でトランプは並べられているので、この真ん中のトランプよりも右側に目的のトランプは存在していることがわかります。
今度は右側の真ん中のトランプをめくります
すると10が出てきますね
今度はこれよりも小さいので左側に存在していることがわかります
もう一度真ん中のトランプをめくると、無事に見つかりました。
つまり、バイナリーサーチ(二分探索とも呼ばれる)とは、整列済みの要素を半分にして、目的のデータが前にあるのか、後ろにあるのかを比べながら、目的のデータを見つけ出すアルゴリズムになります
プログラムに置き換えてみましょう
# coding: utf-8
# Here your code !
def binary_search(card_list, card):
low = 0
high = len(card_list) - 1
print(high)
while low <= high:
mid = (low + high) // 2
#print(mid)
#print(card_list[mid])
if card_list[mid] == card:
print("{0}番目に{1}はあります".format(mid,card))
return
elif card_list[mid] < card:
low = mid + 1
else:
high = mid - 1
return
if __name__ == '__main__':
heart_cards = [1,2,4,5,6,8,9,10,12,13]
heart_eight = 8
binary_search(heart_cards, heart_eight)
線形探索リストの最大探索回数はN(Nはデータの個数分)で、平均探索回数はN/2
でしたね。
一方、二分探索アルゴリズムの
最大探索回数はlog2N＋1
平均探索回数はlog2N
になります
つまり、２分探索アルゴリズムで、100万個のデータを探索するとなると、最大で21回、平均でも20回トランプをめくるだけですみます。
探索アルゴリズムの時、最大で100万回トランプをめくっていた時を振り返って見てください
線形探索の時よりも、よっぽど効率的ですね
しかし、冒頭でも説明しましたが、この２分探索アルゴリズム、必ずデータが整列されていないと使えません！
ここまで理解できていたら、当然ですよね
データが必ず、左側が一番小さく、右側にいけば大きくなるという条件があるから、この２分探索アルゴリズムは成立します。
でも、実際世の中のデータは、生まれながらに整列されていることはまずありません。
では、どうしたら良いでしょうか？
そんな時の出番になるのが、ソートアルゴリズムになります
ランダムで、規則性もないバラバラに並べられたデータ群を、昇順なり、降順なり、整列するアルゴリズムがソートアルゴリズムです。
■ 探索アルゴリズムまとめ
以上で探索アルゴリズムの説明はおしまいです。
『データ群の中から、ある目的のデータを入手したい！』という問題があった時に
私たちは、線形探索アルゴリズムを使うことができます
これは、簡単でわかりやすく、初心者でも、この問題を解くことができるアルゴリズムになります。
しかし、この線形探索アルゴリズムはまた別の問題を孕みます
それは、非効率的であるということ
100万個あるデータなら100万回探索する可能性があるのがこのアルゴリズムです
そして、この問題を解決するのが、２分探索アルゴリズムです
『効率的に、データ群の中から、ある目的のデータを入手したい！』という問題に、この２分探索アルゴリズムを使うことができます。
しかし、またこの２分探索アルゴリズムは、また問題を抱えています
それは、データが整列されていないと使用することができないということ
データが昇順、降順に整列されているという前提があるから、この２分探索アルゴリズムは使用することができます
そして、この問題を解決するのがこの後紹介するソートアルゴリズムになります。
このソートアルゴリズムには実はたくさん種類があります。
それぞれによって、効率性が違ったり、組み合わせて使う場合もあります。
しかし、どのソートアルゴリズムも目的は一つです。
バラバラに並べられたデータ群を整列すること
次から見ていきましょう
また、他の探索アルゴリズムに
ハッシュ探索アルゴリズム
と呼ばれるものがあります。
それは今回省かせていただきます
またどこかで紹介できたらなと思っています