【計測】RubyのArray操作の速度を比較。なぜループ内の delete は危険なのか？

Ruby,競技プログラミング関連

以前以下の記事などで書いていますが、ここ数週間はAtCoderのABCコンテストに参加して頭の体操をしています。

そんな中で処理を書く中で、大抵はデータをArrayとして保持し、そのデータをごちゃごちゃ処理して答えを出す、という場面が多々出てきます。
一方で、競技プログラミングでは、処理時間やメモリ使用量に制限があるため、巨大なデータを扱うときや処理方法によっては解き方が合っていても正解とならない場面があります。

今回は、そんな中で出会したRubyのArray#deleteは処理時間が結構かかる、ということを知ったので調べたことやベンチマーク結果などをまとめていきます。

プロを目指す人のためのRuby入門［改訂2版］　言語仕様からテスト駆動開発・デバッグ技法まで [ 伊藤 淳一 ]
楽天ブックス
¥3,278 （2026/10/21 06:46時点 | 楽天市場調べ）
Amazon
楽天市場
Yahooショッピング

調べたきっかけ

前述の通り、競技プログラミングをやっている中で、サンプル問題は正解できるがコードを提出すると処理時間オーバーによって不正解となる場面が多々出てきます。
アルゴリズムに関する知識があまりないので、かなり愚直に処理を書いている認識はあるので、公式の解説や他の方の提出コードなどを参考に知見を得ている最中です。

大体ABCコンテストだとC問題あたりで計算量を気にしなければいけない場面が出てくるのですが、ここが毎回つまづきポイントとなっています。
Arrayにデータを格納し、そのデータに対して条件に合うものに対して処理したり、各データの内容によって他のデータを操作したり、というようなことがよく出題されています。

今回の問題は、ABC471のC問題です。

おおまかな処理の想定

問題を解いていた時は、想定として以下のような流れを考えていました。

  1. 座標を取得し、Arrayとして保持する
  2. 現在地から近い座標を見つけて合計移動距離を計算する
  3. Arrayから2で取得した座標を削除する
    流れとしては、そこまで複雑ではなさそうなので、コードを書いてみて提出。
    結果は・・・TLE、時間内に処理が終わらずに不正解となってしまいました。
    結局コンテスト時間内には解消できず、諸々調べていたところ知ったのがタイトルにある「Array#deleteは速度が遅い」ということでした

Array#deleteメソッド

Array#deleteは、その名の通りArrayから指定した要素を削除するメソッドです。
削除時は、指定した要素とArrayの各要素を==で比較し、一致したものを削除していきます。
ざっくりした解説はこの通りなのですが、内部的にはもう少し複雑なことをしています。
ドキュメントからソースを確認すると以下の通りでした。

VALUE
rb_ary_delete(VALUE ary, VALUE item)
{
    VALUE v = item;
    long i1, i2;

    for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) {
        VALUE e = RARRAY_AREF(ary, i1);

        if (rb_equal(e, item)) {
            v = e;
            continue;
        }
        if (i1 != i2) {
            rb_ary_store(ary, i2, e);
        }
        i2++;
    }
    if (RARRAY_LEN(ary) == i2) {
        if (rb_block_given_p()) {
            return rb_yield(item);
        }
        return Qnil;
    }

    ary_resize_smaller(ary, i2);

    ary_verify(ary);
    return v;
}

ポイントとなるのはary_resize_smallerの部分です。

static void
ary_resize_smaller(VALUE ary, long len)
{
    rb_ary_modify(ary);
    if (RARRAY_LEN(ary) > len) {
        ARY_SET_LEN(ary, len);
        if (len * 2 < ARY_CAPA(ary) &&
            ARY_CAPA(ary) > ARY_DEFAULT_SIZE) {
            ary_resize_capa(ary, len * 2);
        }
    }
}

ただ削除しただけでは要素が歯抜けになった配列ができてしまうので、削除された要素分縮める処理が走ります。
ary_resize_capaの処理自体はもっと複雑なのでメモしませんが、ざっくりArrayのサイズに応じてヒープメモリを使うかどうかが変わるようでした。

ということで、ざっくりまとめるとArray#deleteメソッドは以下の流れで処理をしています。

  • Arrayから指定した要素を見つけたら削除する
  • 指定した要素がなければnilを返す
  • 要素を削除した場合、Arrayのサイズを縮めつつ最後に見つけた値を返す

なので、Array#deleteをループの中で読み出すと、都度Array全体を検索する処理と削除・縮める処理が走るので時間がかかるというわけです。

似たメソッドのArray#delete_at

似たようなメソッドとしてArray#delete_atがあります。
これは、指定したインデックスの要素をArrayから削除するメソッドです。

このメソッドは、削除する要素をインデックスで指定するのでArray全体から一致する要素を検索する必要がないのでArray#deleteより速度が速いです。
・・・処理内容が異なるので当然といえばそうですね。

処理速度を比較してみる

どの程度処理速度が変わるのかわからなかったので、ベンチマークをとってみました。
上記のABC471のC問題のように、配列から要素を取り出して処理し、その要素を除外する、というようなコードを以下の3パターンで比べてみます。

  • Array#deleteを使った場合
  • Array#delete_atを使う場合
  • Arrayからデータを削除せず、別の方法で管理する

そもそもArrayからデータを削除しない方針をとる

Arrayから対象を削除する処理に時間がかかるのであれば、そもそも削除しなければ良いのでは、と思って似たようなことをSetを使って実現してみました。
コードとしてはこんなイメージです。

deleted = Set.new
array.each do |val| # このArrayに処理すべきデータが入っている
  next if deleted.include?(val)

  deleted << val
  # valを使った操作
end

では、ベンチマークです。
コードはこんな感じのものを比べています。
fetch_sorted_samplesでユニークなデータを持つ配列を用意し、これに対してArray#delete・Array#delete_atと上記のSetを使ったものを比べてみました。

# frozen_string_literal: true

require "benchmark/ips"
require "set"

def fetch_sorted_samples(range, count, exclude: nil)
  result = []

  while result.size < count
    needed = count - result.size
    chunk = Array.new(needed) { rand(range) }

    chunk.delete(exclude) if exclude

    result.concat(chunk)
    result.uniq!
  end

  result.sort!
end

MAX_SIZE = 8 * (10**5)
range = (-10**9)..(10**9)
sample = fetch_sorted_samples(range, MAX_SIZE, exclude: 0)

Benchmark.ips do |r|
  r.report "delete" do
    array = sample.dup
    until array.empty?
      val = array.sample
      # valを使った処理
      array.delete val
    end
  end

  r.report "delete_at" do
    array = sample.dup
    until array.empty?
      index = rand(array.length)
      val = array[index]
      # valを使った処理
      array.delete_at index
    end
  end

  r.report "not delete" do
    deleted = Set.new
    array = sample.dup
    array.each do |val|
      next if deleted.include?(val)

      deleted << val
      # valを使った操作
    end
  end

  r.compare!
end

結果はこんな感じ。
Array#deleteは処理に時間がかかる、というのはわかっていましたがArray#delete_atもそこまで

Arrayのサイズごとのベンチマーク

Arrayサイズが10の時

ruby 4.0.7 (2026-09-15 revision 229531a6cf) +PRISM [arm64-darwin27]
Warming up --------------------------------------
              delete   124.978k i/100ms
           delete_at   127.120k i/100ms
          not delete   145.072k i/100ms
Calculating -------------------------------------
              delete      1.451M (± 4.0%) i/s  (689.10 ns/i) -      7.374M in   5.081253s
           delete_at      1.285M (± 1.1%) i/s  (777.96 ns/i) -      6.483M in   5.043601s
          not delete      1.468M (± 1.3%) i/s  (680.98 ns/i) -      7.399M in   5.038350s

Comparison:
not delete:  1468471.2 i/s
    delete:  1451158.2 i/s - same-ish: difference falls within error
 delete_at:  1285414.9 i/s - 1.14x  slower

Arrayサイズが100の時

ruby 4.0.7 (2026-09-15 revision 229531a6cf) +PRISM [arm64-darwin27]
Warming up --------------------------------------
              delete     4.191k i/100ms
           delete_at    14.269k i/100ms
          not delete    18.775k i/100ms
Calculating -------------------------------------
              delete     43.710k (± 9.8%) i/s   (22.88 μs/i) -    222.123k in   5.081773s
           delete_at    142.065k (± 0.9%) i/s    (7.04 μs/i) -    713.450k in   5.022005s
          not delete    188.884k (± 0.9%) i/s    (5.29 μs/i) -    957.525k in   5.069390s

Comparison:
not delete:   188883.7 i/s
 delete_at:   142064.8 i/s - 1.33x  slower
    delete:    43709.7 i/s - 4.32x  slower

Arrayサイズが1,000の時

ruby 4.0.7 (2026-09-15 revision 229531a6cf) +PRISM [arm64-darwin27]
Warming up --------------------------------------
              delete    42.000 i/100ms
           delete_at     1.210k i/100ms
          not delete     1.993k i/100ms
Calculating -------------------------------------
              delete    560.336 (± 7.7%) i/s    (1.78 ms/i) -      2.814k in   5.021987s
           delete_at     12.207k (± 0.6%) i/s   (81.92 μs/i) -     61.710k in   5.055335s
          not delete     20.012k (± 1.3%) i/s   (49.97 μs/i) -    101.643k in   5.079076s

Comparison:
not delete:    20012.1 i/s
 delete_at:    12206.9 i/s - 1.64x  slower
    delete:      560.3 i/s - 35.71x  slower

Arrayサイズが10,000の時

ruby 4.0.7 (2026-09-15 revision 229531a6cf) +PRISM [arm64-darwin27]
Warming up --------------------------------------
              delete     1.000 i/100ms
           delete_at    40.000 i/100ms
          not delete   195.000 i/100ms
Calculating -------------------------------------
              delete      5.695 (± 0.0%) i/s  (175.59 ms/i) -     29.000 in   5.091983s
           delete_at    409.542 (± 0.5%) i/s    (2.44 ms/i) -      2.080k in   5.078840s
          not delete      1.984k (± 1.2%) i/s  (504.08 μs/i) -      9.945k in   5.013100s

Comparison:
not delete:     1983.8 i/s
 delete_at:      409.5 i/s - 4.84x  slower
    delete:        5.7 i/s - 348.33x  slower

Arrayサイズが100,000の時

ruby 4.0.7 (2026-09-15 revision 229531a6cf) +PRISM [arm64-darwin27]
Warming up --------------------------------------
              delete     1.000 i/100ms
           delete_at     1.000 i/100ms
          not delete    18.000 i/100ms
Calculating -------------------------------------
              delete      0.054 (± 0.0%) i/s    (18.67 s/i) -      1.000 in  18.666110s
           delete_at      3.450 (± 0.0%) i/s  (289.89 ms/i) -     18.000 in   5.217995s
          not delete    188.169 (± 1.1%) i/s    (5.31 ms/i) -    954.000 in   5.069924s

Comparison:
not delete:      188.2 i/s
 delete_at:        3.4 i/s - 54.55x  slower
    delete:        0.1 i/s - 3512.37x  slower

Arrayサイズが800,000の時

ruby 4.0.7 (2026-09-15 revision 229531a6cf) +PRISM [arm64-darwin27]
Warming up --------------------------------------
              delete     1.000 i/100ms
           delete_at     1.000 i/100ms
          not delete     2.000 i/100ms
Calculating -------------------------------------
              delete      0.001 (± 0.0%) i/s  (1163.90 s/i) -      1.000 in 1163.899957s
           delete_at      0.052 (± 0.0%) i/s    (19.14 s/i) -      1.000 in  19.143359s
          not delete     19.832 (± 5.0%) i/s   (50.42 ms/i) -    100.000 in   5.042303s

Comparison:
not delete:       19.8 i/s
 delete_at:        0.1 i/s - 379.66x  slower
    delete:        0.0 i/s - 23082.71x  slower

ベンチマークの結果

それぞれの結果を表にまとめてみます。
なお、AtCoder上ではRuby 3系ですがここではRuby 4.0.7で計測します。

処理内容が異なるので単純な比較はできませんが、Arrayから削除するより明らかにSetを使った方法が速いことがわかりました。
また、Array#delete_atはArray#deleteより速いですが、Arrayサイズが大きくなるにつれて速度低下が大きくなっていることがわかりました。
合わせて、AtCoderでは大抵の場合処理時間が2秒と制限されているので、Array#deleteやArray#delete_atでは時間内に処理が終わらないことが確認できました。

ということで、Array#deleteやArray#delete_atは処理に時間がかかるので
Arrayのサイズが大きくなることが想定される場合は、直接削除せずに削除したことを別の配列等で管理する方法を検討した方が良さそうです。

まとめ

今回は、AtCoderのコンテストの中で処理時間オーバーで不正解となってしまう場面に遭遇したので、実際の処理内容を追ったりベンチマークをとって比較したりしてみました。
結果としては、コンテストの中で使ったArray#deleteは遅いことがわかっていました。そして、それより速いと思っていたArray#delete_atについてもArrayのサイズが大きくなるほどどんどん速度が低下していくことがわかりました。

合わせて、削除せず別の方法で削除したことを管理するなど、異なる方針で同じことを実現することで劇的に処理速度を改善できることもわかりました。
改めて、アルゴリズムについて学ぶことの意義というか、意味を実感した出来事でした。

今回は、ここまで。

プロを目指す人のためのRuby入門［改訂2版］　言語仕様からテスト駆動開発・デバッグ技法まで [ 伊藤 淳一 ]
楽天ブックス
¥3,278 （2026/10/21 06:46時点 | 楽天市場調べ）
Amazon
楽天市場
Yahooショッピング

おわり

Posted by しきゆら