Ruby
Gem
diff-lcs

Rubyのdiff-lcsの実行速度

More than 1 year has passed since last update.


Diff::LCS.sdiffDiff::LCS.diff の実行速度の違い

diff-lcsで使うDiff::LCS.sdiffDiff::LCS.diff の実行速度について、100万行の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メソッドの方が遅くなっている。ただし、約100万行のCSVファイルでこの程度の差なので、よほど巨大なファイルを扱うのでなければ違いは無視できると思われる。


参考情報

Diff::LCS.sdiffDiff::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


lcs.rb

# line: 408-409

# #traverse_balanced might be a bit slower than #traverse_sequences,
# noticable only while processing huge amounts of data.