2 つのファイルを比較する問題は古くからあります。40 年前のパンチ カードの時代には、毎日販売される商品の請求書を印刷するために、すでに問題を解決しなければなりませんでした。1 つのファイルは顧客ファイル (プライマリ ファイル) で、2 つ目は納品書からパンチされたカードのデッキ (セカンダリ ファイル) でした。この二次ファイルの各レコード (カード) には、顧客番号とアイテム番号の両方が含まれていました。両方のファイルは顧客番号でソートされ、アルゴリズムはマッチングと呼ばれていました。各ファイルから 1 つのレコードを読み取り、共通キーを比較し、次の 3 つのケースのいずれかを選択します。
- 主キー < 副キー : この顧客をスキップします (通常、顧客ファイルには今日の売上よりも多くの顧客がいます)
次の主レコードを読み取ります
- 主キー = 第 2 キー : 請求書を印刷する
次の顧客レコード
を読み取る 顧客番号が変更されるまで、第 2 ファイルからアイテムを読み取って印刷する
- プライマリ キー > セカンダリ キー : セカンダリ ファイルのタイプミスまたは新しい顧客で、まだ顧客ファイルに追加されていない
エラー メッセージを出力する (有効な顧客ではない)
次のセカンダリ レコードを読み取る
読み取りループは、読み取るレコードがある限り、つまり両方のファイルが EOF (ファイルの終わり) にない限り続きます。私がRubyで書いたより大きなMatchingモジュールのコア部分は次のとおりです:
def matching(p_actionSmaller, p_actionEqual, p_actionGreater)
read_primary
read_secondary
while ! @eof_primary || ! @eof_secondary
case
when @primary_key < @secondary_key
p_actionSmaller.call(self)
read_primary
when @primary_key == @secondary_key
p_actionEqual.call(self)
read_primary
read_secondary
when @primary_key > @secondary_key
p_actionGreater.call(self)
read_secondary
end
end
end
これは、配列の問題に適応した簡略化されたバージョンです。
# input "files" :
x = [ [2,'a2','b20'], [3, 'a3', 'b3'], [4,'a4','b4'] ]
y = [[1,'a1','b1'], [2,'a2','b2' ], [3, 'a30', 'b3'], [5, 'a5', 'b5']]
puts '--- input --- :'
print 'x='; p x
print 'y='; p y
xh = Hash.new
yh = Hash.new
# converted to hash for easy extraction of data :
x.each do |a|
key, *value = a
xh[key] = value
end
y.each do |a|
key, *value = a
yh[key] = value
end
puts '--- as hash --- :'
print 'xh='; p xh
print 'yh='; p yh
# sort keys for matching both "files" on the same key :
@xkeys = xh.keys.sort
@ykeys = yh.keys.sort
print '@xkeys='; p @xkeys
print '@ykeys='; p @ykeys
# simplified algorithm, where EOF is replaced by HIGH_VALUE :
@x_index = -1
@y_index = -1
HIGH_VALUE = 255
def read_primary
@x_index += 1 # read next record
# The primary key is extracted from the record.
# At EOF it is replaced by HIGH_VALUE, usually x'FFFFFF'
@primary_key = @xkeys[@x_index] || HIGH_VALUE
# @xkeys[@x_index] returns nil if key does not exist, nil || H returns H
end
def read_secondary
@y_index += 1
@secondary_key = @ykeys[@y_index] || HIGH_VALUE
end
puts '--- matching --- :'
read_primary
read_secondary
while @x_index < @xkeys.length || @y_index < @ykeys.length
case
when @primary_key < @secondary_key
puts "case < : #{@primary_key} < #{@secondary_key}"
puts "x #{xh[@primary_key].inspect} has no equivalent in y"
read_primary
when @primary_key == @secondary_key
puts "case = : #{@primary_key} = #{@secondary_key}"
puts "compare #{xh[@primary_key].inspect} with #{yh[@primary_key].inspect}"
read_primary
read_secondary
when @primary_key > @secondary_key
puts "case > : #{@primary_key} > #{@secondary_key}"
puts "y #{yh[@secondary_key].inspect} has no equivalent in x"
read_secondary
end
end
実行:
$ ruby -w t.rb
--- input --- :
x=[[2, "a2", "b20"], [3, "a3", "b3"], [4, "a4", "b4"]]
y=[[1, "a1", "b1"], [2, "a2", "b2"], [3, "a30", "b3"], [5, "a5", "b5"]]
--- as hash --- :
xh={2=>["a2", "b20"], 3=>["a3", "b3"], 4=>["a4", "b4"]}
yh={5=>["a5", "b5"], 1=>["a1", "b1"], 2=>["a2", "b2"], 3=>["a30", "b3"]}
@xkeys=[2, 3, 4]
@ykeys=[1, 2, 3, 5]
--- matching --- :
case > : 2 > 1
y ["a1", "b1"] has no equivalent in x
case = : 2 = 2
compare ["a2", "b20"] with ["a2", "b2"]
case = : 3 = 3
compare ["a3", "b3"] with ["a30", "b3"]
case < : 4 < 5
x ["a4", "b4"] has no equivalent in y
case > : 255 > 5
y ["a5", "b5"] has no equivalent in x
違いのプレゼンテーションはあなたに任せます。
HTH