Rubyのdiff-lcsの実行速度 #Ruby

`Diff::LCS.sdiff` と `Diff::LCS.diff` の実行速度の違い

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

ダミーデータ

dummy1.csv

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

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を使って作成

実行速度検証コード

# 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

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

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