計算量について意識してプログラムを書くための第一歩

#はじめに
プログラミングをやり始めてから間もなく1年になりますが、基本的な知識である計算量について気にすることがほとんどなかったことが発覚したので、しっかり勉強しようと思いました。
at_coderの問題を例に計算量を意識しない書き方と意識した書き方での性能比較を行います。
計算量意識するの大事だなという実感を持ってもらえたら嬉しいです。

#計算量を意識していないコード
下記の問いに答えるように実装していきました。
まずは、特に計算量を意識することなく実装していきます。

正の整数Kが与えられます。正の整数の 3つ組 (A,B,C)であって、ABC≤Kなるものの個数を求めてください。 ただし、A,B,Cの順番が異なるだけの組も異なる組として数えます。

###サンプルコード1（自分が元々書いていたもの）
実装方針は下記です。
A,B,Cのそれぞれの変数に対して、1からKまでの数を順次代入していき、それぞれの場合のAとBとCの積がK以下の場合の数をカウントしました。

n = gets.chomp!.to_i
count = 0

n.times do |i|
  n.times do |j|
    if (i+1) * (j+1) <= n
      n.times do |k|
        if (i+1) * (j+1) * (k+1) <= n
          count += 1
        end
      end
    end
  end
end

puts count

いくつかの値を入力してみて、想定する結果が得られたので処理自体は問題ありませんでした。
だけど、入力値nを10000くらいにすると全然終わりませんでした。。。

#計算量を意識したコード
サンプルコード1だと、入力する値nが小さい場合は問題ありませんが、大きくすると処理自体が完了しませんでした。
これじゃ、機能が仕様通りになっていても、性能が悪すぎて使えません。
なので、サンプルコード1を改善していきます!

###サンプルコード2（break処理を入れたもの）
サンプルコード1の一番の問題点は、行っていた計算の半分以上が無駄になっていることでした。
問題になっているのは、ここの部分です。

if (i+1) * (j+1) <= n

2数の積がnの大きさを超える場合でも、毎回ここの条件を評価することになり、無駄な計算が発生しています。
jはインクリメントなので、一定の数をを超えたら評価する必要がなくなります。
そのため、下記のようにコードを変えました。

n = gets.chomp!.to_i

count = 0
n.times do |i|
  n.times do |j|
  break if (i+1) * (j+1) > n
    n.times do |k|
      break if (i+1) * (j+1) * (k+1) > n
        count += 1
    end
  end
end

puts count

これだとnの入力値を10000くらいにしても、すぐに結果を返してくれます。
ただ、もう少し計算量を減らすことができるのではと思い、サンプルコード3も描いてみました。

###サンプルコード3（break処理を入れ、かつ、計算量少し減らしたもの）
実装方針は下記です。
3数の組み合わせを出した上で、3数の並び替えの通りを数えたのでそれに沿ったやり方を試してみました。

n = ６の時には、
(A,B,C) = (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)
の6通りがありますが、これを個別で数えるのではなく、
(A,B,C) = (1,2,3)の組み合わせを見つけて、その並び替えの数を計算します。

n = gets.chomp!.to_i

count = 0
n.times do |i|
  (i+1).times do |j|
    break if (i+1)*(j+1) > n
      (j+1).times do |k|
        break if (i+1)*(j+1)*(k+1) > n
          if (i == j) && (j == k)
            count += 1
          elsif (i == j) ^ (j == k)
            count += 3
          else
            count += 6
          end
      end
  end
end

気持ち的に早くなったような気がしました。
正確にはわからないので、実際にサンプルコードを比較していきます。

#性能比較
実際に早くなったのか3つのコードをBenchmarkを用いて下記のように計測します。

https://qiita.com/scivola/items/c5b2aeaf7d67a9ef310a

Benchmark.bm(10) do |x|
  n = 100
  x.report("サンプルコード1") do ##自分が元々書いていたもの
    counter_1(n)
  end
  x.report("サンプルコード2") do ##break処理を入れたもの
    counter_2(n)
  end
  x.report("サンプルコード3") do ##break処理を入れ、かつ、計算量少し減らしたもの
    counter_3(n)
  end
end

n = 10
                 user     system      total        real
サンプルコード1    0.000033   0.000004   0.000037 (  0.000033)
サンプルコード2    0.000015   0.000000   0.000015 (  0.000015)
サンプルコード3    0.000009   0.000000   0.000009 (  0.000010)

結果の見方は、こちら参照してください今回はtotalの値を見れば良いと思います。

https://qiita.com/scivola/items/c5b2aeaf7d67a9ef310a

自分の期待値としては、計測時間がサンプルコード1 > サンプルコード2 > サンプルコード3
となると思っていましたが、サンプルコード2とサンプルコード3の結果が逆でした。
もう少し、nの値を大きくしみます。

n = 100
                 user     system      total        real
サンプルコード1    0.003470   0.000024   0.003494 (  0.003521)
サンプルコード2    0.000808   0.000001   0.000809 (  0.000811)
サンプルコード3    0.000104   0.000000   0.000104 (  0.000104)

期待通りの結果になりました。ついでにもっとnを大きくしてみます。
nの値を大きくしたときに、サンプルコード３は力を発揮してくれるみたいです。

n = 10000
                 user     system      total        real
サンプルコード1   61.783598   0.181313  61.964911 ( 62.323397)
サンプルコード2    0.061399   0.000159   0.061558 (  0.061719)
サンプルコード3    0.022213   0.000017   0.022230 (  0.022241)

サンプルコード1がめちゃくちゃ遅くなりました。
nを100倍にした時、サンプルコード2は100倍くらいの値になりましたが、サンプルコード1は100の2乗倍くらいの値になりました。

#計算量の見積もり
毎回、コードを書くたびに計算量を測ったりするのはすごい時間がかかってしまいます。
なので、コードを書く段階でおおよその計算量を出せるようにします。
大きさnの対象に対して、要する演算数をカウントすることで、アルゴリズムの計算量を見積もることができ、成長率の最も高いnに着目するO（オーダー）記法を利用し、大まかな計算量を示します。
サンプルコードを用いて計算量を見積もります。

・サンプルコード1：
ループ処理を3回回しているので、それをもとに計算します。 2n^3 + n^2 ≈ O(n^3)

計算方法（下記コードを参照）
if (i+1) * (j+1) <= n の行で、iとjがそれぞれn回ずつ代入され実行されるので、n^2回の演算数になる。
if (i+1) * (j+1) * (k+1) <= n　と　count += 1　の行で、iとjとkがそれぞれn回ずつ代入され実行されるので、n^3×2回の演算数になる。
それらを加算して演算数が2n^3 + n^2になる。

n = gets.chomp!.to_i
count = 0

n.times do |i|
  n.times do |j|
    if (i+1) * (j+1) <= n 
      n.times do |k|
        if (i+1) * (j+1) * (k+1) <= n
          count += 1
        end
      end
    end
  end
end

puts count

・サンプルコード2：
ループ処理を3回回していますが、breakしているので、 計算量はかなり減っています。ただ残念ですが、直接計算で求めることができなかったので、いくつかのnの値を用いて、演算数をおよそのオーダーで出しました。　106n - 500000 ≈ O(n)

・サンプルコード3：
ループ処理を3回回していますが、一つ一つのループ処理は階層が深くなるたびに回す数が小さくなるので、少しだけ演算数は軽減されます。　18n - 100000 ≈ O(n)

それぞれの演算数を計算対象nの大きさを変化した時に得られるグラフは下記になります。

サンプルコード2とサンプルコード3はほとんど同じように増加するので、オーダーが同じことがわかります。
実行結果と同じようにnが十分大きい時には、計算量がサンプルコード1 > サンプルコード2 > サンプルコード3
になることが確認できました。

これを用いて、常に計算量を意識しながらプログラムを書くことができるはずです。
#まとめ
・とりあえずプログラムが仕様通りに動けば良いと思ったけど、そんなことはないです。
・プログラムを書くときは、演算数見て、計算量意識しましょう。（他にも、発行されるクエリとかも意識する必要あるみたいだけど、まずは第一歩）