何をしたいか

配列の添字を複数同時に指定して、下記のようにまとめて削除したい。

array = [3, 6, 1, 9, 7, 8]
array.delete_ats([1, 3, 4])
array #=> [3, 1, 8]

さらにこの計算量を改善して、高速に動かしたい！（計算量やオーダー記法 O(⋅) については、参考ページを最後に掲載しました）

実装

オープンクラスを使って、見かけ上同じ動きをするメソッドを Array クラスに4つ追加してみました。

class Array
  # being_deleted must be sorted

  # 後ろから順番に削除（頭から削除すると、削除の度に添字がずれるため）
  # O(N^2)？
  def delete_ats_1(being_deleted)
    being_deleted.reverse.each do |deleted|
      self.delete_at(deleted)
    end
  end

  # being_deleted に self の index が含まれる場合は削除（線形探索）
  # O(N^2)
  def delete_ats_2(being_deleted)
    self.delete_if.with_index do |_, i|
      being_deleted.include?(i)
    end
  end

  # delete_ats_2 を改善
  # being_deleted に self の index が含まれる場合は削除（二分探索）
  # O(NlogN)
  def delete_ats_3(being_deleted)
    self.delete_if.with_index do |_, i|
      being_deleted.bsearch { |deleted| deleted >= i } == i
    end
  end

  # self と being_deleted を順番に回しつつ、削除しない物を tmp に詰める
  # O(N)
  def delete_ats_4(being_deleted)
    tmp = []
    current = 0
    self.each_with_index do |a, i|
      if being_deleted[current] == i
        current += 1
      else
        tmp << a
      end
    end
    self.replace(tmp)
  end
end

ベンチマーク

実装

require 'benchmark'
require_relative '../lib/delete_ats.rb'

ARRAY_SIZE = gets.to_i
array_1 = (0...ARRAY_SIZE).to_a
array_2 = array_1.dup
array_3 = array_1.dup
array_4 = array_1.dup
being_deleted = 0.step(ARRAY_SIZE - 1, 2).to_a
Benchmark.bm do |x|
  puts ("ARRAY_SIZE: #{sprintf("%.0e", ARRAY_SIZE)}")
  x.report("1:") { array_1.delete_ats_1(being_deleted) }
  x.report("2:") { array_2.delete_ats_2(being_deleted) }
  x.report("3:") { array_3.delete_ats_3(being_deleted) }
  x.report("4:") { array_4.delete_ats_4(being_deleted) }
end

配列の要素を 1 つずつ飛ばしながら順番に削除し、その実行時間を計測します。

結果比較

配列サイズ 10 ^ 4

       user     system      total        real
ARRAY_SIZE: 1e+04
1:  0.002244   0.000012   0.002256 (  0.002352)
2:  0.259646   0.001245   0.260891 (  0.264851)
3:  0.007171   0.000162   0.007333 (  0.007628)
4:  0.000715   0.000032   0.000747 (  0.000747)

配列サイズ 10 ^ 5

       user     system      total        real
ARRAY_SIZE: 1e+05
1:  0.213257   0.001253   0.214510 (  0.216350)
2: 25.813206   0.159038  25.972244 ( 26.720222)
3:  0.087369   0.000814   0.088183 (  0.090878)
4:  0.007199   0.000207   0.007406 (  0.007442)

delete_ats_2 は O(N²) のため、ここでオーダー数が 10¹⁰ に達してしまい、許容時間を超えてしまいました。

配列サイズ 10 ^ 6

       user     system      total        real
ARRAY_SIZE: 1e+06
1: 28.544373   0.241101  28.785474 ( 31.156171)
3:  0.941576   0.006753   0.948329 (  0.960607)
4:  0.074461   0.002314   0.076775 (  0.077585)

delete_ats_1 も O(N²) 相当の計算量かと思いましたが、delete_at メソッドが思ったよりも早く動きました。しかし配列サイズ 10⁵ までが限界のようです。

配列サイズ 10 ^ 7

       user     system      total        real
ARRAY_SIZE: 1e+07
3: 11.047709   0.104127  11.151836 ( 11.707355)
4:  0.749899   0.028396   0.778295 (  0.805788)

O(NlogN)の delete_ats_3 は配列サイズ 10⁶ が限界です。

配列サイズ 10 ^ 8

       user     system      total        real
ARRAY_SIZE: 1e+08
4:  7.132723   0.149687   7.282410 (  7.398004)

O(N)の delete_ats_4 も配列サイズ 10⁸ はさすがに厳しかったです。

まとめ

計算量を O(N) まで落とした delete_ats_4 のメソッドであれば、配列サイズ 10⁷ 程度まで、添字を複数同時に指定して素早く要素を削除できるようになりました！

※添字は事前に昇順でソートされている必要があります。

※マイナスの添字には対応していません。

テストコード

こんな感じで簡単にテストを動かして、全てのメソッドの動作を確認しました。👀

require 'test/unit'
require_relative '../lib/delete_ats.rb'

class TestDeleteAts < Test::Unit::TestCase
  def setup
    @array = [3, 6, 1, 9, 7, 8]
  end

  def test_delete_ats_4
    @array.delete_ats_4([0, 3, 5])
    assert_equal @array, [6, 1, 7]
  end

  def test_delete_ats_4_when_including_exceeding_index
    @array.delete_ats_4([0, 3, 5, 6])
    assert_equal @array, [6, 1, 7]
  end

  def test_delete_ats_4_when_index_is_empty
    @array.delete_ats_4([])
    assert_equal @array, [3, 6, 1, 9, 7, 8]
  end
end

参考ページ：計算量（オーダー記法）について

W - 2.06.計算量 - AtCoder

要素数やループ回数などをオーダー記法 O(⋅) で表現することで、プログラムの中でどこが実行時間のボトルネックとなるかがわかり、実行時間を当てずっぽうではなく高精度で予測することができます。ざっくりとした一例を挙げると、Ruby では 10⁷ の一重ループが実行時間的に限界です。

ごぐたんのブログ

ごぐたんのブログです。

Ruby の delete_ats メソッドを書いた（配列の複数要素を O(N) で高速に削除）