[アルゴリズム(Ruby)]尺取り法の解説

こんにちは！じゃいごテックのあつしです。

今回は尺取り法というアルゴリズムをご紹介します。

尺取り法とは

数列から取り出す範囲の先頭と末尾のインデックス情報を記憶して、先頭・末尾の位置をスライドさせた分の変化量を加減算して範囲内の総数を計算する方法です。

区間の最大値や条件を満たす区間を求める時によく使うアルゴリズムです。

サンプルコード

n 個の要素を持つ配列 ary の連続する k 個の要素の最大合計値を求めるコードです。

# しゃくとり法
# 左端と右端をずらして加減算を行っていく
def func1(n, k, ary)
  # 最大区間 max_total と total を最初の区間合計で初期化
  max_total = total = ary[0..k - 1].sum

  # 次の区間以降をループ処理
  1.upto(n - k) do |index|
    # ary[index - 1] は計算区間から外れるので total から引く
    total = total - ary[index - 1]

    # ary[index + k - 1] は計算区間に追加されるので total に足す
    total = total + ary[index + k - 1]

    # total が max_total を超えていたら更新する
    if total > max_total
      max_total = total
    end
  end
  max_total
end

# sumメソッドで計算を行う(2重ループ)
def func2(n, k, ary)
  # max_total を最初の区間合計で初期化
  max_total = ary[0..k - 1].sum

  # 次の区間以降をループ処理
  1.upto(n - k).each do |index|
    # ary[index] から k 個分の要素の合計を計算し total へ代入
    total = ary[index..index + k - 1].sum

    # total が max_total を超えていたら更新する
    if total > max_total
      max_total = total
    end
  end
  max_total
end

# ******************************
# n 個の要素を持つ配列 ary があり
# 連続する k 個の合計最大値を求める
# ******************************

# 計算条件
n = 10000
k = 5000
a = 100

# ランダムを固定
srand(0)
# ランダム配列生成
ary = Array.new(n) { rand(a) }

# 問題確認用
#p ary
puts "n = #{n}, k = #{k}"
puts "--------"

# func1: 尺取り法で処理
# 計算量 = k + (n - k) * 3
start = Time.now
puts func1(n, k, ary)
puts <<~"EOS"
       尺取り法
       処理時間: #{Time.now - start}
       計算量: #{k + (n - k) * 3}
     EOS
puts "--------"

# func2: sumメソッドで処理
# 計算量 = k + (n - k) * (k + 1)
start = Time.now
puts func2(n, k, ary)
puts <<~"EOS"
       sumメソッド
       処理時間: #{Time.now - start}
       計算量: #{k + (n - k) * (k + 1)}
     EOS

サンプルコードの計算量と実行時間

尺取り法では n の桁と計算量の桁が同じペースで増えますが、sumメソッド（2重ループ）では n の桁が1個増えると計算量の桁が2個増えます。

処理時間で見ると、 10の8乗後半から2秒程度の処理時間がかかるようになり、 paiza.IO でタイムオーバーが出始めました。

尺取り法の計算量

sumメソッド（2重ループ）の計算量

サンプルコードの動作確認

paiza.IO で要素数 n 、 計算範囲 k を変えて実行してみることが出来ます。

サンプルコードの処理解説

サンプルコードを以下の条件で実行した時の処理を解説します。

今回のまとめ

尺取り法は始点・終点の位置を記憶しておき、始点・終点をスライドさせて値を加減算していく方法で、条件を満たす区間の長さや数を求めるのに適したアルゴリズムです。

尺取り法は理解しやすいアルゴリズムだと思うので是非使ってみて下さい。