そういう仕様だった

The array is changed instantly every time the block is called, not after the iteration is over.

http://www.ruby-doc.org/core-2.1.2/Array.html#method-i-delete_if

ようするに条件ブロックが true を返したら次に条件ブロックが実行されるときには、配列は完全な状態で要素数は１つ減っているということだ。使いやすさ優先ということなのだろう。

この制約を緩めると O(n) の delete_if を書くことが出来る。

class Array
  # 走査が完了するまで配列を不完全な状態に置くが、
  # 空間効率 O(1)、時間効率 O(n) で走る delete_if。
  def lite_delete_if
    fail ArgumentError, 'no block given' unless block_given?

    read_ptr = 0
    writ_ptr = 0
    while read_ptr < size
      item = self[read_ptr]
      if yield(item)
        read_ptr += 1
        next
      elsif read_ptr != writ_ptr
        self[writ_ptr] = item
      end
      read_ptr += 1
      writ_ptr += 1
    end
    self
  ensure
    while read_ptr < size
      self[writ_ptr] = self[read_ptr]
      read_ptr += 1
      writ_ptr += 1
    end
    self[writ_ptr..-1] = [] # truncate
  end
end

標準の delete_if との比較はこんな感じ。

                  user     system      total        real
delete all   10.070000   0.690000  10.760000 ( 10.802066)
delete half   5.050000   0.360000   5.410000 (  5.418306)
delete none   0.010000   0.000000   0.010000 (  0.011556)
lite all      0.020000   0.000000   0.020000 (  0.026159)
lite half     0.040000   0.000000   0.040000 (  0.038867)
lite none     0.030000   0.010000   0.040000 (  0.033636)

配列への書き込み回数が一番多くなる、全要素の半分を削除するケースが一番遅くなっているのが面白い。

空間効率を気にしなければ*1もう少し速くできる。こちらのバージョンはブロックから break した場合、何も削除されない点でまたセマンティクスが異なる。

class Array
  # 走査が完了するまで配列を全く変更しないが、
  # 空間効率 O(n)、時間効率 O(n) で走る delete_if。
  def quick_delete_if(&test)
    fail ArgumentError, 'no block given' unless test

    replace(reject(&test))
  end
end

                  user     system      total        real
quick all     0.010000   0.000000   0.010000 (  0.012533)
quick half    0.020000   0.000000   0.020000 (  0.014838)
quick none    0.010000   0.000000   0.010000 (  0.022953)

ベンチマークに利用したスクリプトはこちら。

# -*- coding: utf-8 -*-
require 'benchmark'

# class Array ... をここに。

n = 250_000
ints = [*1..n]

Benchmark.bm(11) do |bm|
  ar = ints.dup
  bm.report('delete all') do
    ar.delete_if { true }
  end
  fail unless ar.empty?

  ar = ints.dup
  bm.report('delete half') do
    ar.delete_if(&:odd?)
  end
  half = ar
  fail unless ar.size == 125_000

  ar = ints.dup
  bm.report('delete none') do
    ar.delete_if { false }
  end
  fail unless ar == ints

  ar = ints.dup
  bm.report('lite all') do
    ar.lite_delete_if { true }
  end
  fail unless ar.empty?

  ar = ints.dup
  bm.report('lite half') do
    ar.lite_delete_if(&:odd?)
  end
  fail unless ar == half

  ar = ints.dup
  bm.report('lite none') do
    ar.lite_delete_if { false }
  end
  fail unless ar == ints

  ar = ints.dup
  bm.report('quick all') do
    ar.quick_delete_if { true }
  end
  fail unless ar.empty?

  ar = ints.dup
  bm.report('quick half') do
    ar.quick_delete_if(&:odd?)
  end
  fail unless ar == half

  ar = ints.dup
  bm.report('quick none') do
    ar.quick_delete_if { false }
  end
  fail unless ar == ints
end

*1:殆どの場合問題にならないだろう。GC があぶなっかしい Ruby 2.1.1 では繰り返し呼び出すとメモリフットプリントが漸増したが。