なぜ Ruby の組み込みメソッドを覚えなくてはならないのか？

Advent Calendar 2022

こんにちは、サービスエンジニアリング本部の寺田です。

軽く自己紹介になりますが、私は SIer で SE を2年間経験したのち、現職のエニグモには 2020/7 よりジョインしております。

普段は主に Ruby on Rails を用いた BUYMA のサーバーサイド開発をやっています。

最近興味ある事はアルゴリズムで、週末には Atcoder にちょくちょく挑戦したりしています。

ちなみに、この記事は Enigmo Advent Calendar 2022 の7 日目の記事になります！

12 月はこのように弊社のエンジニアが記事を執筆しますので、ぜひお楽しみに！

組み込みメソッドをなぜ覚える必要があるのか？

私が嫌いなものそれは暗記です...なるべく覚えるものは少なく済ませたい、そんな思いが私にとって常にあるのです。そんな私にとってプログラミングを勉強したての頃に思ったことはこれでした。

「ぶっちゃけ for と if が使えれば何でもできるんじゃないのか？」

そうなんです。たいていのプログラムは for と if を使えば表せるのです。ではなぜ膨大な量の組み込みメソッドを覚える必要があるのか？？

一つ理由となるのは、それは読みやすい（=可読性が高い）からですよね。

ただ、組み込みメソッドを使ったプログラムが誰にとっても読みやすいかと言ったら、そうでもないですよね？

# 配列の合計を計算する

## inject を利用した場合
puts [2, 3, 4, 5].inject { |result, item| result + item }

## for ループを利用した場合
sum = 0
[2, 3, 4, 5].each do |v|
  sum += v
end

puts sum

配列の要素の合計を計算するのに、inject というメソッドを使ってます。これは知ってる人は簡単に読めるかもしれませんが、直感的には for ループを使用したプログラムの方が読みやすい気がします。

では、組み込みメソッドを絶対使った方が良いケースとはどんな場合でしょうか？

それは、

「for や if を使って簡単に書けるプログラムより圧倒的に早い場合」

これは絶対に組み込みメソッドを使ったプログラムの方がいいですよね？

ruby には優れたアルゴリズムを使用して書かれたメソッドがあらかじめ存在しています。今回の記事では4つのメソッドと、これらに使用されているアルゴリズムについて紹介していこうと思います！

array#sort

問題

1~100000 までの数字がランダムに並び替えられた配列を、 昇順に並び替えてください。

for と if を使ったプログラム

len = array.length
len.times do |i| 
    (len - 1 - i).times do |j|
        if array[j] > array[j + 1]
            array[j], array[j + 1] = array[j + 1], array[j]
        end
    end
end

for と if だけを使って簡単にプログラムを作成した場合、こんな感じでしょうか？

ここで用いられているアルゴリズムはバブルソートというものです。

バブルソートのアルゴリズムを図解すると...

隣り合った数値同士を比較し、大小関係が合っていない場合は値を交換する。というのが基本の考え方になります。

  • 1番目の要素と2番目の要素の大小関係を比較
  • 2番目の要素と3番目の要素の大小関係を比較
  • ...
  • 最後から一つ前と最後の要素の大小関係を比較

とすることで、一番最後の要素の値が確定します。

これを要素の数だけ繰り返すというものになります。

なので、ループの回数は要素の個数を n とすると、 n(n-1)/2 回で、計算量は O(n^{2}) となります。

オーダー記法

ここでオーダー記法（例に出てきた O(n^{2}) という書き方）を軽く押さえておきましょう。

オーダー記法はコンピューターによる計算がどれくらいの時間がかかるかを示したものです。

各計算量オーダーに対して、実際にどれくらいの計算回数になるのか表で見てみましょう。

O(n) O(log{n}) O(nlog{n}) O(n^{2})
10 3 33 100
100 7 664 10000
1000 10 9966 1000000
10000 13 132877 100000000
1000000 20 19931569 1000000000000

計算量はオーダーによってかなり異なることがわかります。 O(n) に比べて O(log{n}) はかなり高速ですし、 O(n^{2}) よりは O(nlog{n}) の方がとても高速です。

また、この差は数が大きくなればなるほど広がっていきます。

Ruby の組み込み関数を使用

ここで本題に戻りましょう。

Ruby の組み込みメソッドを使用して、この問題を解くならば、Array#sort が使えます。

array.sort

Array#sort で使われているアルゴリズムは クイックソート というものです。

手順としては以下の流れでソートを行います。

  1. 基準となる数値を決める
  2. 基準より小さい or 以上のグループに配列の要素を振り分けていく
  3. 要素が１つ以上あるグループにおいて、各グループ内で新たに基準を決める
  4. グループ内で基準より小さい or 以上のグループに配列の要素を振り分けていく

この繰り返しを、それぞれのグループの要素が1つずつになるまで繰り返していき、最後に全てを結合することでソートを実現していきます。

計算量ですが、平均で O(log{n}) になります。

最良のケースでは一度のループで各グループの要素数が、前回のループの半分の数になっていきます。

証明は省きますが、このように段々と 1/2 になっていき、最終的にn 個 => 1 個に要素が減っていくまでにかかる計算量は O(log{n}) となると覚えておくと良いでしょう。

さらに、毎回のループで配列の長さである n 回の比較を行うため、 O(nlog{n}) が計算量となります。

実際にプログラムを実行して計算量を比較してみたのが以下の実行結果です。

n = 100000 の場合、for ループによるバブルソートより、Array.sort が 1000 倍も早いです。

Enumerable#bsearch

問題

1000000000 個の要素があるソート済みの配列の中から、 特定の数以上の値が初めて現れるインデックス番号を求めてください。

for と if を使ったプログラム

array.each_with_index do |v, i|
    if (v >= 99999999)
      puts i
      break
    end
end

非常にシンプルに考えるとこうでしょうか？

このようなアルゴリズムは全探索と呼ばれるものです。

配列の全要素に対して一つ一つ比較して答えを求めるものになります。

配列の長さだけループが走るので、長さ n の配列に対して計算量は O(n) です。

Ruby の組み込み関数を使用

では Ruby の組み込み変数、Enumerable#bsearch を使った場合はどのようなアルゴリズムになるでしょうか？

array.bsearch { |x| x >= 99999999 }

こちらで使用されているアルゴリズムは二分探索というものです。

配列の中から 2 という数字を探す場合を考えてみましょう。

こちらのアルゴリズムでは以下の手順で答えを求めます。

  1. 左端と右端の値の中心の値を基準に、探したい数が基準より小さい or 以上かを求める
    • 基準より小さい場合 => 探したい値は左半分にあるとわかる
    • 基準以上の場合 => 探したい値は右半分にあるとわかる
  2. 要素が一つになるまで繰り返す

こちらもループを繰り返すたびに、要素の数は 1/2 => 1/4 => 1/8 ... とどんどん半分になっていきます。

なので、要素が1つになるまでに必要なループのオーダーは O(log{n}) になります。

これは全探索の O(n) よりかなり高速です。実際にプログラムを実行した結果を見てみましょう。

ものすごい違いですね。二分探索は全探索より 1000000 倍も早いという結果となりました。

Integer#pow

問題

3^{10000000} を計算してください。

とても大きな数で累乗の計算をしてくださいというケースですね。

for と if を使ったプログラム

ans = 1
(100000000).times do
    ans = ans * 3
end

puts ans

累乗は言い換えれば底を指数の回数だけ掛け合わせるということです。

これを素直に実装すれば上記のようになるでしょうか。

指数の回数だけループして掛け算を行いますので、指数を n とすると計算量は O(n) になります。

Ruby の組み込み関数を使用

Ruby の組み込み関数には Integer#pow というものがあります。これは Integer#**とアルゴリズムは同じです。

3.pow(100000000)

こちらはアルゴリズムとして繰り返し二乗法が使われています。

例として 3^{8} を考えてみましょう。

愚直に計算するとループの回数は指数の数である 8 回です。

\displaystyle 3^{8} = 3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3 \times 3

しかし 3^{8} は変換してみると、以下のようになることがわかります。

\displaystyle 3^{8} = 3^{4} \times 3^{4} \\ 3^{4} = 3^{2} \times 3^{2} \\ 3^{2} = 3^{1} \times 3^{1} \\ 3^{1} = 3

このように考えれば、ループの回数は4回で済みます。

この手順を一般化して考えると、以下のようになります。

  1. 求めたい値を、指数を 1/2 にした値を掛け合わせた式で表す
  2. 指数が 1 になるまで繰り返す

指数はループを経ることに 1/2 => 1/4 => 1/8 ... と半分になっていきます。指数が n ならば、1 になるまでに発生するループの回数は O(log{n}) で非常に高速です。

実際にプログラムを動かして比較してみました。

非常に高速です。愚直な計算方法より 1000000 倍も早いことがわかります。

Integer#gcd

問題

463836510 と 692647128 の最大公約数を求めてください

for と if を使ったプログラム

ans = 0
    (1...[a, b].max).each do |d|
        ans = d if (a % d == 0 && b % d == 0)
    end

puts ans

最大公約数とは、二つの値を割り切れる最大の整数のことです。

この定義をそのまま実装するならば、上記のようなプログラムになるかと思います。

こちらは全探索のアルゴリズムとなっていて、与えられた数が n とすると計算量は O(n) となります。

Ruby の組み込み関数を使用

最大公約数を求めるメソッドとして、Integer#gcd が用意されています。

a.gcd(b)

こちらはユークリッドの互除法と呼ばれるアルゴリズムが使用されています。

ユークリッドの互除法というのは以下の定義を指します。

2つの自然数 a, b について、a / b = q、a % b = r とすると、
「a, b の最大公約数」は「b と r の最大公約数」に等しい。

式で表すと以下のようになります。

\displaystyle a = b \times q + r \ ならば \ gcd(a, b) = gcd(b, r)

ここで gcd(a, b) は a と b の最大公約数を表します。

これを繰り返すことによって、少ないループの回数で最大公約数を求めることができます。

例えば、629 と 481 の最大公約数を求めてみましょう。

\displaystyle 629 \div 481 = 1 \cdots 148 \\ 481 \div 148 = 3 \cdots 37 \\ 148 \div 37 = 4 \cdots 0

最後のステップでは、148 を 37 で割った際のあまりは 0 になっています。

これは 148 と 37 では 37 が最大公約数になっていることを意味します。

ゆえに、 gcd(148, 38) = gcd(629, 481) = 37 と最大公約数が求まります。

そして、このアルゴリズムの計算量はざっくりと O(log{n}) になります。

a \div b = q 、 a \ (mod{b}) \ = r として、 a = b \times q + r より以下のことが言えます。

\displaystyle a \geq b + r \ (q \geq 1) \\ b + r \geq 2r \ (b > r)

すなわち、

\displaystyle \frac{a}{2} \geq r

が成り立ちます。

2回のループを経ることで、確実に値が 1/2 以下になるわけですね。

先ほどから何度も出てきたパターンですが、値が 1/2 に減少していくアルゴリズムは計算量が O(log{n}) となります。

実際に実行速度を比べてみましょう。

計算速度は 10000000 倍に速くなっています。

まとめ

タイトル詐欺になってしまいますが、大事なことは Ruby のメソッドを覚えることではなく、どういうアルゴリズムがあり、自分が直面した問題を解決するためにどのアルゴリズムを使うべきかを判断できるようになることだと思います。

Web エンジニアの裾野が広がってコンピューターサイエンスを学んだことのないエンジニアの方もいらっしゃるかと思います。この機会にぜひ興味を持ってもらえると嬉しいかなと思います！

明日の記事の担当は サービスエンジニアリング本部 の 後藤 さんです。お楽しみに！

株式会社エニグモ すべての求人一覧

hrmos.co