【計測】RubyのArray操作の速度を比較。なぜループ内の delete は危険なのか？
以前以下の記事などで書いていますが、ここ数週間はAtCoderのABCコンテストに参加して頭の体操をしています。
そんな中で処理を書く中で、大抵はデータをArrayとして保持し、そのデータをごちゃごちゃ処理して答えを出す、という場面が多々出てきます。
一方で、競技プログラミングでは、処理時間やメモリ使用量に制限があるため、巨大なデータを扱うときや処理方法によっては解き方が合っていても正解とならない場面があります。
今回は、そんな中で出会したRubyのArray#deleteは処理時間が結構かかる、ということを知ったので調べたことやベンチマーク結果などをまとめていきます。
調べたきっかけ
前述の通り、競技プログラミングをやっている中で、サンプル問題は正解できるがコードを提出すると処理時間オーバーによって不正解となる場面が多々出てきます。
アルゴリズムに関する知識があまりないので、かなり愚直に処理を書いている認識はあるので、公式の解説や他の方の提出コードなどを参考に知見を得ている最中です。
大体ABCコンテストだとC問題あたりで計算量を気にしなければいけない場面が出てくるのですが、ここが毎回つまづきポイントとなっています。
Arrayにデータを格納し、そのデータに対して条件に合うものに対して処理したり、各データの内容によって他のデータを操作したり、というようなことがよく出題されています。
今回の問題は、ABC471のC問題です。
おおまかな処理の想定
問題を解いていた時は、想定として以下のような流れを考えていました。
- 座標を取得し、Arrayとして保持する
- 現在地から近い座標を見つけて合計移動距離を計算する
- 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のサイズが大きくなるほどどんどん速度が低下していくことがわかりました。
合わせて、削除せず別の方法で削除したことを管理するなど、異なる方針で同じことを実現することで劇的に処理速度を改善できることもわかりました。
改めて、アルゴリズムについて学ぶことの意義というか、意味を実感した出来事でした。
今回は、ここまで。
おわり