rubyでdiffを求める

ダミーデータ

diffを求めるのに先立ち、ダミーのデータを用意してみましょう。

rubyでのテストデータの生成にはfakerやforgeryが知られています。
今回はforgeryの日本語拡張であるforgery_jaを使用しています。

ダミーデータはCSVで用意する物とし、一行にはid, 名前, 住所を格納してみましょう。
最終的には差分を算出したいので、削除、変更、追加された異なる2つのデータを生成します。

# ダミー生成スクリプト

require 'csv'
require 'forgery_ja'

column_size = 100000 # データ件数
delete_size = 300 # 削除する件数
edit_size = 300 # 変更する件数
add_size = 30 # 追加する件数

dummy = []
column_size.times do |i|
  dummy << [
    i,
    ForgeryJa(:name).full_name,
    ForgeryJa(:address).full_address
  ]
end

CSV.open 'dummy1.csv', 'w' do |writer|
  dummy.each do |line|
    writer << line
  end
end

# 削除
delete_size.times do
  dummy.delete_at(rand dummy.size)
end

# 変更
edit_size.times do
  # 住所を変更する
  dummy[rand dummy.size][2] = ForgeryJa(:address).full_address
end

# 追加
add_size.times do |i|
  dummy << [i + column_size, ForgeryJa(:name).full_name, ForgeryJa(:address).full_address]
end

CSV.open 'dummy2.csv', 'w' do |writer|
  dummy.each do |line|
    writer << line
  end
end

出力結果

0,佐々木 健太,佐賀県沼田市西境町5547-4
1,相澤 翼,栃木県静岡市葵区矢場町9-5-9
2,山崎 楓花,秋田県矢板市高倉町4585-6
3,小林 美希,青森県島田市熊野町3-1-0
4,渡辺 仁,沖縄県多野郡上野村東境町3151-6
5,古閑 美帆,富山県下都賀郡岩舟町三田町1204-4

diffの取得

差分の取得にはdiff-lcsを使用してみます。
使い方は簡単で、2つの配列を渡すだけです。

require 'diff/lcs'

seq1 = %w(a b c e h j l m n p)
seq2 = %w(b c d e f j k l m r s t)

lcs = Diff::LCS.LCS(seq1, seq2)
diffs = Diff::LCS.diff(seq1, seq2)
sdiff = Diff::LCS.sdiff(seq1, seq2)

ちなみに、LCSはLongest Common Subsequenceなので、2つの要素列の最長共通部分列という意味です。

Diff::LCS.diffとDiff::LCS.sdiffの違いは、差分一つ一つがDiff::LCS::Changeで返るか、Diff::LCS::ContextChangeで返るかの違いです。

Diff::LCS.sdiffで比較できる一行の単位は文字列ですが、Diff::LCS.diffは一行の単位がArrayでも大丈夫です。
今回はCSV.readの読み出しをそのまま突っ込むのでDiff::LCS.diffを使用します。

diff算出サンプル & ベンチマーク

作成したダミーデータのdiffを求めるとともに、ベンチマークを取ってみます。
rubyで簡易なベンチマークの実行は標準で用意されているbenchmarkを利用するのが簡単です。

実行したマシンはMac Book Airでプロセッサは Intel Core i5 1.7GHz。
ダミーのCSVの中身は100000件、ファイルサイズは5.4MBです。

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

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

@diffs.each do |diff|
  puts '-----'
  diff.each do |line|
    p line
  end
end

実行結果

              user     system      total        real
read:     2.740000   0.060000   2.800000 (  2.806428)
diff:     1.140000   0.010000   1.150000 (  1.148815)
total:    3.880000   0.070000   3.950000 (  3.955243)
-----
["-", 84, ["84", "宮里 大輝", "山形県磐田市松栄町0094-9"]]
-----
["-", 355, ["355", "藍田 大地", "福井県富士市山池町7184-1"]]
-----
["-", 437, ["437", "加藤 友香", "三重県ひたちなか市丸田町3999-3"]]
-----
["-", 484, ["484", "木村 華子", "佐賀県下都賀郡岩舟町高倉町8-0-2"]]
["+", 481, ["484", "木村 華子", "高知県新潟市北区寿町2600-2"]]
-----
~~ 以下略 ~~

Dev.Wan.Co