Ruby on Rails アルゴリズム

Question

Ruby on Railsでホームページを作成するために勉強をしているのですが、Ruby on Railsの勉強をする際に、アルゴリズムの勉強って必要なのでしょうか？

Ruby on Railsで、食べログやココナラのようなサイトが作れれば良いなと思っているのですが、アルゴリズムは必要ですか？

また、アルゴリズムが必要な場合、挿入ソート等の基本的なアルゴリズムを知れば良いのか、それとも、それ以上が必要になるのかも教えて頂けたらと思っています。

よろしくお願い致します。

Answer 1

アルゴリズムの本来の意味は「ある解を計算する手続き」です。単純なものから、計算科学の教科書にあるようなもの、競技プログラミングで必要とされるような高度なものまで色々です。アルゴリズムは知っていて損はありませんが、アルゴリズムの種類によって覚えることが異なると私は思っています。

###書き方を覚えるのではなく、使い方や性質を覚えるべきアルゴリズム

例えば下記も単純ですが、アルゴリズムです。

# 配列の最大値を求めるアルゴリズム
a = [16, 52, 9, 31, 38, 8, 96, 69, 97, 37]
max = a.first
a.drop(1).each do |i|
  if max < i
    max = i
  end
end
p max # => 97

でも、Rubyなら下記のようにも書けます。

# 配列の最大値を求めるアルゴリズム？
a = [16, 52, 9, 31, 38, 8, 96, 69, 97, 37]
max = a.max
p max # => 97

さて、後半のコードはアルゴリズムなのでしょうか？いえいえ、単純にEnumerable#maxの使い方に過ぎません。では、どちらが良いコードかというと、前半よりも後半のほうがはるかにいいコードでしょう。つまり、Rubyに初めから用意されているようなアルゴリズムは、用意されたメソッドを使った方が断然早いのです。あれ、結局最大値を求めるアルゴリズムなんて覚えなくて良かったの？そうではありません。最大値を求めるアルゴリズムは単純すぎて計算量が変わるような改良の余地はありませんが、ソートのように複数の方法があり、それぞれ利点や欠点がある場合は、どんなアルゴリズムがあるかを覚えておくことは重要です。

ソートアルゴリズムと言うと、バブルソート、マージソート、クイックソート、イントロソート、ヒープソート、挿入ソート、その他亜種も含めればたくさんあり、かなり研究されている分野です。それぞれ、平均計算量、最悪計算量、メモリ使用量、どのようなデータが得意か苦手かが異なります。また、安定ソートか安定ではないソートかという違いもあります。

Rubyにはsortやsort_byメソッドがあります。CRubyではruby_qsortと言う関数で実装されており、クイックソート(単純なものではなく、中央値を取るなどの工夫はしてある)を採用しています。極めて特殊なデータを除けば、高速で動作しますので、標準のメソッドで十分でしょう。しかし、この実装は安定ソートではありません。もし、安定ソートを期待するような動作を想定している場合は、工夫が必要になります。

つまり、sort(およびsort_by)を知っていれば別にソートアルゴリズムは知らなくてもいい、と言うわけでは無く、Rubyのsortは、工夫されたクイックソートであることから、

• そこそこ速い(特殊な並びのデータを除けば、最速)
• 安定ソートではない

ということは覚えておく必要があります。データの並びに特定の傾向があり、より速いソートアルゴリズムが存在する、同じ値の時に並び順は変えたくないので、安定ソートが必要、と言った場合に、別のソートアルゴリズムを使った方が速くなったり、呼び出し方を工夫する必要があります。

Rubyには他にも、素数の列挙や因数分解ができるprimeライブラリが標準で添付されていたり、外部ライブラリまで広ければ、メモ化を行えるmemoistなど、よく使うようなアルゴリズムについてはライブラリを使って簡単に実装できる場合があります。これらを使う場合も、アルゴリズムの書き方を覚えるのでは無く、それらがどのようなアルゴリズムをつかって、どのような性質を持っているかを覚えておくことの方がは重要だと思います。

###書き方よりもどんなときに使えるかを覚えるべきアルゴリズム

上には単純に当てはまらないアルゴリズムがあります。競技プログラミングでよく目にするような、分割統治法、動的計画法、貪欲法、幅優先探索、深さ優先探索、繰り返し二乗法等々です(一杯ありすぎて私もよくわかりません)。これらは、素因数分解やソートのような何か決まり決まったことを解くための手法と言うよりも、解を求めるための戦術です。実際にはこれらを採用しなくても、単純な全探索で解ける場合が多いです。しかし、データが多い場合は速度が全く異なります。

では、実際に必要になるのかというと、必ずしもそうではありません。数十個のオーダーのデータであれば、全探索でも十分な速度が出ることがありますし、数個しかないデータに対して複雑なアルゴリズムを採用した場合、逆に遅くなる場合もあります。逆に、数百個、数千個、数万個のデータを一気に処理する場合にはアルゴリズムを使っているか使っていないかで目に見えるほどの速度の違いができます。

つまり、どのような時にどのように場面で使うかが問題です。競技プログラミングの問題で出てくるような、あるアルゴリズムを使わないとパフォーマンスに影響がでるような状況はそれほど多くありません。単純な投稿サイトであれば、絶対に必要になるアルゴリズムはランキングを出すためのソートぐらいですが、それもRubyのsortや、DBのorder byを使ってしまえば終わりです。しかし、全く不要というわけでもありません。これまでにあった数千〜数万件という大量の投稿を分析し、何かしらの傾向を探ったり、レポートを生成したりするときには、これらのアルゴリズムが必要になる場合があります。そこで、せっかくアルゴリズムを覚えていても、それを使わずに全探索なんかしていたら意味がありません。なので、どんなときに使えるかを知っておくことこそが重要だと思います。

Comments

[退会済みユーザー]

回答ありがとうございます。

詳しい解説を頂けて、アルゴリズムをどう使うかというのが少しわかったような気がします。

どんなときに使えるかに重点を置いて、アルゴリズムを勉強したいと思います。

ありがとうございました。

Answer 2

Ruby on Railsでホームページを作成するために勉強をしているのですが、Ruby on Railsの勉強をする際に、アルゴリズムの勉強って必要なのでしょうか？

Ruby on Railsで、食べログやココナラのようなサイトが作れれば良いなと思っているのですが、アルゴリズムは必要ですか？

恐らく、勉強することは必要ではないかと思います。必要なアルゴリズムはいくつか考えられますが（ランキングのためのソートや、検索のための文字列サーチなど）、それらはRuby on Railsやその周辺のライブラリが提供してくれるはずです。

しかし、一つ重要なことを説明しておきましょう。先程、私が必要なアルゴリズムを見積ることができたのは、私がアルゴリズムを勉強して、それがどのような問題を解決することができるのかを知っていたからに他なりません。

アルゴリズムとは「問題解決のための決まった手順」のことです。
そして、ソフトウェアやサイトを開発するということは「開発」という大きな問題を一つ一つの小さな問題に分割して、それらに解決の手段（つまりアルゴリズム）を提供していくことです。
このとき、アルゴリズムを知らなければどのような問題があるのか分からず、分割することができません。

そういう意味ではアルゴリズムを学ぶことには十分価値があるかと思います。

サイト作りがんばってください。

Comments

[退会済みユーザー]

回答ありがとうございます。

丁寧な回答ありがとうございます。詳しく解説して頂いたおかげで、アルゴリズムの重要性がわかりました。

問題を分割して、解決の手段を提供していく。なるほどです。

アルゴリズムの勉強の仕方もお聞きしたいところですが、別の質問で質問させて頂こうかと思います。

ありがとうございました。