Rubyのdiff-lcsの実行速度



##`Diff::LCS.sdiff` と `Diff::LCS.diff` の実行速度の違い
diff-lcsで使う`Diff::LCS.sdiff` と `Diff::LCS.diff` の実行速度について、１００万行のCSVファイル（ファイル容量: 57.5MB）で検証した結果は以下のとおり。

###ダミーデータ

```csv:dummy1.csv
0,高嶺 咲,秋田県利根郡片品村熊野町0-0-9
1,田中 海斗,岡山県伊東市八幡町2-6-3
2,相田 結愛,富山県ひたちなか市野田新町7-6-3
・・・
999997,宮里 健,宮崎県館林市広小路8464-8
999998,中島 柚希,広島県浜松市浜北区矢場町6244-8
999999,井上 秀樹,福島県焼津市新富町7684-6
```

```csv:dummy2.csv
0,高嶺 咲,秋田県利根郡片品村熊野町0-0-9
1,田中 海斗,岡山県伊東市八幡町2-6-3
2,相田 結愛,富山県ひたちなか市野田新町7-6-3
・・・
1000027,鈴木 陽輝,神奈川県ひたちなか市南沖野町2574-2
1000028,清水 大地,愛媛県ひたちなか市寿町9-6-3
1000029,古賀 恵美子,徳島県三条市天王町4707-9
```

※ ダミーデータは`forgecy_ja`を使って作成

###実行速度検証コード

```ruby
# diff算出サンプル
require 'csv'
require 'diff/lcs'
require 'benchmark'

puts "Diff::LCS.diff"

Benchmark.bm(7, "total:") do |x|
  r = x.report("read:") {
    @data1 = CSV.read 'dummy1.csv'
    @data2 = CSV.read 'dummy2.csv'
  }
  d = x.report("diff:") { @diffs = Diff::LCS.diff(@data1, @data2) }

  total = r + d

  [total]
end

puts "Diff::LCS.sdiff"

Benchmark.bm(7, "total:") do |x|
  r = x.report("read:") {
    @data1 = CSV.read 'dummy1.csv'
    @data2 = CSV.read 'dummy2.csv'
  }
  d = x.report("diff:") { @diffs = Diff::LCS.sdiff(@data1, @data2) }

  total = r + d

  [total]
end
```

###実行結果
```
Diff::LCS.diff
              user     system      total        real
read:    14.460000   0.560000  15.020000 ( 15.103050)
diff:    10.220000   0.170000  10.390000 ( 10.471545)
total:   24.680000   0.730000  25.410000 ( 25.574596)
Diff::LCS.sdiff
              user     system      total        real
read:    15.380000   0.430000  15.810000 ( 15.896651)
diff:    15.990000   0.200000  16.190000 ( 16.286861)
total:   31.370000   0.630000  32.000000 ( 32.183512)
```

多少ではあるが、`Diff::LCS.sdiff`メソッドの方が遅くなっている。ただし、約１００万行のCSVファイルでこの程度の差なので、よほど巨大なファイルを扱うのでなければ違いは無視できると思われる。


##参考情報
`Diff::LCS.sdiff` と `Diff::LCS.diff` メソッドの定義は以下のとおりである。
[diff-lcs/lcs.rb at master · halostatue/diff-lcs](https://github.com/halostatue/diff-lcs/blob/master/lib/diff/lcs.rb)

```ruby:lcs.rb
# line: 165
def diff(seq1, seq2, callbacks = nil, &block) # :yields diff changes:
  diff_traversal(:diff, seq1, seq2, callbacks || Diff::LCS::DiffCallbacks,
                 &block)
end

# line: 184
def sdiff(seq1, seq2, callbacks = nil, &block) #:yields diff changes:
  diff_traversal(:sdiff, seq1, seq2, callbacks || Diff::LCS::SDiffCallbacks,
                 &block)
end
```

ここで呼び出されている`diff_traversal`メソッドはの定義は以下のとおり。
[diff-lcs/internals.rb at master · halostatue/diff-lcs](https://github.com/halostatue/diff-lcs/blob/master/lib/diff/lcs/internals.rb)

```ruby:internals.rb
# line: 4
def diff_traversal(method, seq1, seq2, callbacks, &block)
  callbacks = callbacks_for(callbacks)
  case method
  when :diff
    traverse_sequences(seq1, seq2, callbacks)
  when :sdiff
    traverse_balanced(seq1, seq2, callbacks)
  end
  callbacks.finish if callbacks.respond_to? :finish

  if block
    callbacks.diffs.map do |hunk|
      if hunk.kind_of? Array
        hunk.map { |hunk_block| block[hunk_block] }
      else
        block[hunk]
      end
    end
  else
    callbacks.diffs
  end
end
```

さらに、`Diff::LCS.sdiff`メソッドから呼び出される`diff_traversal`メソッドの注意書きに、`diff_traversal`メソッドは`Diff::LCS.diff`メソッドから呼び出される`traverse_sequences`メソッドより少し遅いと書かれている。
[diff-lcs/lcs.rb at master · halostatue/diff-lcs](https://github.com/halostatue/diff-lcs/blob/master/lib/diff/lcs.rb)

```ruby:lcs.rb
# line: 408-409
# #traverse_balanced might be a bit slower than #traverse_sequences,
# noticable only while processing huge amounts of data.
```