A Micro Toolbox

ソフトウェアのニッチな問題の対処記録です

キーブレイク処理を簡潔に書きたい

Ruby

ということで、簡単なモジュール(https://github.com/hashimoton/keybreak)を作ってgem化した。

キーブレイク処理

キーブレイク処理(またはコントロールブレイク処理)とは、ソート済みのレコードを順に読み込んで、レコード内のある項目(キー)が同一のレコードごとにグループ分けして処理を行うこと。
例えば、キーごとの件数を数えたり、集計をしたりといった処理が挙げられる。

参考:


RubyにはEnumerable#mapに代表されるスマートな方法があるけれど、
使用メモリを抑えたい時など、手続き的なプログラムが必要になるときもある。

煩雑なキーブレイク処理のプログラム

典型的なキーブレイク処理のひとつ、キーごとの件数カウントを愚直に書くと次のようになる
レコードは改行区切り、レコード内の項目はタブ区切り、第一項目がキー)。

RECORDS =<<EOD
a	1
b	2
b	3
c	4
c	5
c	6
d	7
e	8
e	9
EOD

count = 0
prev_key = nil

RECORDS.each_line do |line|
  key = line.split("\t")[0]

  if !prev_key.nil? && key != prev_key
    puts "#{prev_key}:#{count}"
    count = 0
  end

  count += 1
  prev_key = key
end

if !prev_key.nil?
    puts "#{prev_key}:#{count}"
end

期待する結果は次のとおり。

a:1
b:2
c:3
d:1
e:2

ここで何が問題かというと、キーごとの件数出力処理("puts")をレコードの読み出しループ内だけでなく、
ループ終了後にもう一度書かなければならない点にある。


これは冗長だし、忘れたらバグになるし、面倒極まりない。
レコードの先読みができる状況(Enumerable#peekなど)であれば、ループ内でキーの終了を検知できるので多少楽になるものの、
キーが入れ子になるケースを考えだすとやはり煩雑になってしまう。

Keybreakモジュールの使い方

Keybreakモジュールを使って件数カウント処理を書き直すと次のようになる。

require "keybreak"

RECORDS =<<EOD
a	1
b	2
b	3
c	4
c	5
c	6
d	7
e	8
e	9
EOD

Keybreak.execute_with_controller do |c, count|
  c.on(:keystart) {count = 0}
  c.on(:keyend) {|key| puts "#{key}:#{count}"}

  RECORDS.each_line do |line|
    key = line.split("\t")[0]
    c.feed(key)
    count += 1
  end
end

Keybreak.execute_with_controllerの一つ目のブロック引数cは、キーブレイク処理の制御補助クラス(Keybreak::Controller, 以下コントローラ)のインスタンス。


キーが変わるとき、現行キーの終了イベント(:keyend)がまず起こり、続いて新しいキーの開始(:keystart)イベントが起こる。
これらのイベントハンドラをコントローラに登録しておく(Controller#on())。
レコードの読み込みループの中でコントローラに新しいキーを渡す(Controller#feed())と、
キーが変わったときに現行キーの終了イベントハンドラと新しいキーの開始イベントハンドラが実行される。


上の例では、キーの開始時にカウント用変数を初期化し、終了時に件数を出力している。


Keybreak.execute_with_controllerは与えたブロックの実行後に、キーの終了イベントをもう一度実行する。
これによって、最終キーも含めてすべてのキーについて件数が出力される。

キーが入れ子の場合


第一項目が親キー(key)、第二項目が子キー(sub_key)。

require "keybreak"

RECORDS =<<EOD
a	a1	1
b	b1	2
b	b2	3
c	c1	4
c	c1	5
c	c2	6
d	d1	7
e	e1	8
e	e1	9
EOD

Keybreak.execute_with_controller do |c|
  Keybreak.execute_with_controller do |sub_c|
    c.on(:keystart) {|key| puts "#{key} START"}
    c.on(:keyend) do |key|
      sub_c.flush
      puts "#{key} END"
    end
  
    sub_c.on(:keystart) {|key| puts "  #{key} START"}
    sub_c.on(:keyend) do |key|
      puts "  #{key} END"
    end

    RECORDS.each_line do |line|
      key, sub_key, value = line.split("\t")
      c.feed(key)
      sub_c.feed(sub_key)
    end
  end
end

親キーと子キーそれぞれにコントローラを用意する。


親キーの終了イベントハンドラで最初に、子キーの強制終了(Keybreak::Controller#flush())を実行する。
親キーのKeybreak.execute_with_controllerブロック内にレコード読み出しループを置き、
親キー、子キーの順でコントローラにキーを渡す。


期待される出力は次のとおり。

a START
  a1 START
  a1 END
a END
b START
  b1 START
  b1 END
  b2 START
  b2 END
b END
c START
  c1 START
  c1 END
  c2 START
  c2 END
c END
d START
  d1 START
  d1 END
d END
e START
  e1 START
  e1 END
e END


Keybreak.execute_with_controllerのブロックが入れ子になるのが嫌なら、
Keybreak::Controller#executeを使って次のようにも書ける。

c = Keybreak::Controller.new
sub_c = Keybreak::Controller.new

c.on(:keystart) {|key| puts "#{key} START"}
c.on(:keyend) do |key|
  sub_c.flush
  puts "#{key} END"
end

sub_c.on(:keystart) {|key| puts "  #{key} START"}
sub_c.on(:keyend) do |key|
  puts "  #{key} END"
end

c.execute do
  RECORDS.each_line do |line|
    key, sub_key, value = line.split("\t")
    feed(key)
    sub_c.feed(sub_key)
  end
end