配列操作の速度を改善してみた話（Ruby）

こんにちは、エンジニアのnaruです。

花粉が鼻と眼球を突きまくる地獄のような時期がそろそろ終わりを迎えそうですね。スーパーハッピーです。リモートで引きこもっていてほぼ関係ないのは内緒です。

さて、最近取り組んだプロジェクトでほんのちょっと改修しただけで大幅な速度改善を実現したという小話をしたいと思います。

問題設定

設定としては以下の通りです。

• huge_array：要素数が多い文字列の配列

• ignore_array：（huge_arrayの要素数から見れば無視できるほどの要素数の）文字列の配列

• huge_array の要素のうち先頭が ignore_array の要素のいずれとも一致しない要素の配列 filtered_huge_array を得たい

上記設定の簡単な例
・huge_array：["apple", "banana", "cherry", "diamond", "elephant"]
・ignore_array：["app", "dia"]
・上記のとき、filtered_huge_array として ["banana", "cherry", "elephant"] を得たい

実際のプロジェクトでの実装状況
以下のようにメソッドのパラメータとして配列を渡し、その配列に破壊的な変更を加えないようにフィルタ済配列を返す必要がありました。
今回の記事でもこの制約に基づいて実装しています。

def filter_array(huge_array, ignore_array)
  # ・huge_array から条件に合わない要素を除外する
  # ・破壊的変更を避けるためhuge_arrayには変更を加えないようにして、
  # 　新規配列 filterd_huge_array を作成し返り値として返す
  
  # huge_array から filtered_huge_array を作る処理

  return filtered_huge_array
end

今回のテスト・ベンチマーク方法
先頭に0〜49,999までの数値がついている文字列の配列から、先頭が奇数である文字列を除いた配列を作ることを考えます。

速度計測については以下のようにbenchmarkライブラリを使用して計測していきます。

desc "配列操作速度テスト"
task :speed_check => :environment do
  require 'benchmark'
  
  Benchmark.bm 25 do |r|
    huge_array = []
    50000.times{|n| huge_array << "#{n}times!"}
    ignore_array = ["1","3","5","7","9"]

    r.report "example title" do
      # ここに実行時間を計測したい処理を記載する
    end
  end
end

複数のパターンで計測してみる

dupでコピーして条件に適さない要素を削除していく方式

元々の実装方式です。
愚直に実装されていて理解しやすい反面、速度的に課題がある実装となっていました。

# dupでコピーして条件に適さない要素を削除していく方式
r.report "dup and delete" do
  filtered_huge_array = huge_array.dup
  huge_array.each do |elem|
    if ignore_array.any? { |ignore_elem| elem.start_with?(ignore_elem) }
      filtered_huge_array.delete(elem)
    end
  end
end

結果：遅い

                           user     system      total        real
dup and delete        21.214093   0.020917  21.235010 ( 21.258392)

後述の実装パターンでの説明でこちらのパターンの速度と比べますが、結果としてはとても遅いものとなっています。

理由をざっくりというと、配列の要素を削除していく操作（Array#delete）がとても遅いことが主な原因であると考えられます。

より細かくいうと、以下の要素が速度劣化の原因として大きそうです。
・deleteの際に配列内の要素を再配置するため時間がかかっている
・deleteの際に対象要素をインデックスで指定するのではなく、要素の内容で検索してから削除するためさらに余計に時間がかかっている

参考：dupのみの処理

ちなみに、上記の中で「dupでコピーする処理自体が遅いんじゃないの？」と感じる方もいるかもしれません。

# 参考：dupのみの処理
r.report "dup only" do
  filtered_huge_array = huge_array.dup
end

測ってみました。

                                user     system      total        real
dup only                    0.000006   0.000002   0.000008 (  0.000006)

爆速です。どうもありがとうございました。
※ ・・・というのも、こちらの記事によるとdupは呼び出されるだけだとO(1)であり、値の更新が行われる際に初めてO(N)かけて複製処理がされる、ということのようです。

空配列で条件に適した要素を末尾追加していく方式

「条件に当てはまらない配列要素の削除」が遅いならば「条件に当てはまる配列要素の空配列への追加」は速いのではということで実装してみたのが以下です。

# 空配列で条件に適した要素を末尾追加していく方式
r.report "create from empty" do
  filtered_huge_array = []
  huge_array.each do |elem|
    if ignore_array.none? { |ignore_elem| elem.start_with?(ignore_elem) }
      filtered_huge_array << elem
    end
  end
end

結果：速くなったぞ

                           user     system      total        real
dup and delete        21.214093   0.020917  21.235010 ( 21.258392)
create from empty      0.019172   0.000317   0.019489 (  0.019611)

配列末尾への追加については計算量が抑えられるため爆速になりました。（もちろん処理した結果は変わりません）

※ ちなみに、配列末尾への追加方法については他にpushがあると思いますが、<<の方が速いようです。

組み込み関数の利用

Ruby組み込みの関数であるselectやrejectを使えば、フィルタ処理を実現することができるのでこちらでも2パターン検証してみます。

select + none?

# selectとnone?使ってフィルタする方式
r.report "nodup and select/none?" do
  filtered_huge_array = huge_array.select do |elem| 
      ignore_array.none? { |ignore_elem| elem.start_with?(ignore_elem) }
    end
end

reject + any?

# rejectとany?使ってフィルタする方式
r.report "nodup and reject/any?" do
  filtered_huge_array = huge_array.reject do |elem|
      ignore_array.any? { |ignore_elem| elem.start_with?(ignore_elem) }
    end
end

結果：さらに若干速くなったぞ

                           user     system      total        real
dup and delete        21.214093   0.020917  21.235010 ( 21.258392)
create from empty      0.019172   0.000317   0.019489 (  0.019611)
select/none?           0.016715   0.000171   0.016886 (  0.016963)
reject/any?            0.016904   0.000137   0.017041 (  0.017088)

さすがは組み込み関数、より最適化がされているのか（内部実装までは確認できておりません）自分で実装したフィルタ処理よりも僅かですがさらに速くなりました。

ちなみにselectパターンとrejectパターンはそこまで違いが出ませんでした。

結論

思いつく複数のパターンで計測して比較してみてわかったこととしては以下の通りです。

• 速度が求められる場面では、極端な特別な理由がない限り配列の要素削除（Array#delete）は使わない方がベターかも。

• 「条件を満たさない要素を削除する」方針よりも「条件を満たす要素を空配列に追加していく」方針の方が速かった。

• さらに組み込み関数で置き換えて既存のレールに乗ったら速くなった。

そして、今回あげたパターン以外にもまだまだ高速化の手法はあると思うので、今後も継続して実装中に効率的な処理実装の意識・調査をしながら改善していきたいです。

そして最後に

スペースマーケットでは現在エンジニア募集中です。
興味のある方、是非お話だけでもさせていただければ幸いです！