Posted at

アルゴリズムって何?

More than 1 year has passed since last update.

プログラミングの勉強を始めた前に、アルゴリズムって何なのか全く分かりませんでした。

GitHubのコードを見ると伝わると思うのですが、私が作ったプログラムはあんまり良くないですww

だからたくさんのプログラマーは上手いことアルゴリズムを活用してるではないかと思うので、この記事を読んでいるあなたはベテランであれば申し訳ないです。

とにかく、私はプログラミングが好きですね。ターミナルで実行できるような小さなプログラムを書いたり、railsでサイトを作ったり、教科書やQiitaの記事を読んだり、色々面白いですよね。

でも、アルゴリズムって言葉を聞いたらなんだか怖い印象がありました。難しくて、本当に頭のいいプログラマーしか使えないような印象が強かったです。

だから別に勉強しなくていいじゃん、プログラミングの入門を読んだら出てこないじゃないかって思ってたけど、やっぱり気になって、アルゴリズムって一体何なんだって探し始めたらこの動画を見つけました:

アルゴリズムの動画

全部視聴してくださいww

なるほど。楽しかったですww


アルゴリズムとは

wikiによってはアルゴリズムというのは:

「問題を解くための手順を定式化した形で表現したもの」

なるほど。決まった関数か、命令か、そのようなものではないですね

まあ、アルゴリスムはものすごく複雑になることはもちろんあるんですけど、アルゴリズムそのものは分かりやすいと思います。

例えば...


total_of_four.rb

1 + 1 + 1 + 1

=> 4
1 + 1 + 2
=> 4
2 + 2
=> 4
3 + 1
=> 4

整数で足し算で4を出力するには、4つの「手順」があります(数字の順番を問わなければ)。

また、すべての「解決の仕方」を見つけ出すのはアルゴリズムですね。

今は上記の手順を見つけ出すもの(アルゴリズム)を書かないけど、アルゴリズムってそういうものだと分かっていただきたいなと思います。

アルゴリズムのコード的な例だと次の感じです:

ary = [2, 3, 1, 7, 10, 5, 4, 9, 8, 6]

1~10までの整数なんですが、順番はバラバラですね。

正しい順番にするアルゴリズムを書きましょう


algorithm.rb

def algorithm(ary)

new_ary = []

1.upto(ary.length) do |n|
ary.each do |val|
if val == n
new_ary << val
end
end
end

new_ary

end

ary = [2, 3, 1, 7, 10, 5, 4, 9, 8, 6]

new_ary = algorithm(ary)
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]


かなり簡単ですね。

後は、プログラミングの例としてはBubble Sortは結構有名なので是非動画の方を見てください。


アルゴリズムの意義

それでも、なんかアルゴリズムの意義がちょっと分かんないな〜と思いました。

アルゴリズムが何なのか分かったけど、なぜ必要なのか分かりませんでした。

リファクトリング?コードの読みやすさ?

で、今年はRubyKaigiに行ってベテランのプログラマーとアルゴリズムについて話せました。

彼の話によると、アルゴリズムによってコートが分かりやすくなることもあるんですけど、まあ、問題を解くためのものですね(最近はamazonはamazon goを発表して「DEEP LEARNING ALGORITHMS」を活用しているし、またGoogleの囲碁のプログラムも有名ですし、色んな問題はアルゴリズムによって解かれています)。で、その中で1つの問題は早さです。つまり、アルゴリズムによってプログラムは早くなります。selection sortは比較的に早いので紹介します。

前のアルゴリズムだと、結構時間かかったんですね。

1.upto(10)が10回呼び出されて、実行ごとにary.eachも呼び出されて、配列の中で1つの数字が抜いていたら壊れるし。なんなんだw

次のはselection sortです


selection_sort.rb

# 選択ソート

def selection_sort ary
0.upto(ary.length - 1).each do |x|
min_num = ary[x]
min_pos = x
range = (( x + 1 )...ary.length)
range.each do |y|
if min_num > ary[y]
min_num = ary[y]
min_pos = y
end
end
ary[x], ary[min_pos] = min_num, ary[x]
end
ary
end

ary = [2, 3, 1, 7, 10, 5, 4, 9, 8, 6]

new_ary = selection_sort ary
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]


このQiitaの記事を参照してください

どんな動作をしているかというと、こうです

0.upto(ary.length - 1).eachは実行ごと一番低い変数が見つかってrangeが短くなるので、次第に早くなります。

p rangeを書くとこんな出力です:


range_output.rb

1...10

2...10
3...10
4...10
5...10
6...10
7...10
8...10
9...10
10...10

アルゴリズムって何なのか分かったら、この動画を見たら結構面白いなと思いましたw

(アルゴリズムの名前は左上にあります)


アルゴリズムの効果

プログラムが早いといいですね。正直は今までは、プログラムを作る時に早さについてあんまり考えたことはありませんでした(とりあえず「動け!」って感じで精一杯ww)。でもこれからはコードの振る舞い、読みやすさ、特別な機能だけじゃなくて、早さや良いアルゴリズムが提供する利点ももっと意識して、活用していきたいなと思います。


アルゴリズムの活用

すぐにアルゴリズムを活用できると思いませんが、また問題にぶつかると、ちょっとだけでもアルゴリズムの知識があればプログラムの品質が上がるんじゃないかなと思います。

私はこのアプリの例を見て、そのアルゴリズムをプログラム化しようとしました。このアプリは全然プログラミングに関係してないから、例を見て、自分でコードで解決するように挑戦してみたらいいかもしれません。

(記事の中でgemのPR申し訳ない)今このgemを作っていますが、配列.eachをするようなことは多いです。アルゴリズムを実装したら品質が上がるんかな〜と思っています(今は実装してないけどw)。

Web APIでも使うかどうかは分からないし、実は要るかどうかはまた別の問題だと思うけど、そもそもその知識はないと活用するのは難しいし、要るかどうかも判断できないから、またアルゴリズムの勉強をしていきたいなと思います。