Rubyで競技プログラミングする人向けのTipsです。
マージテクってありますよね。
set とか Hash をマージするときに要素数の少ない方を列挙することで計算量を削減するやつ
RubyのHashにmergeメソッドあるのですけど、このとき引数に要素数が少ない方を選ぶとマージテクになります
large, small = small, large if large.size < small.size
large.merge!(small)
もちろん eachで回すより、mergeでやるほうが早いです。
small.each{|k, v| large[k] = v }
large.merge!(small) # こっちのが早い
コメントで以下の質問を頂いたので追記
key が重複しないとき専用でしょうか？
key が重複すると、large の値が上書きされてしまうので、それでいいのか考えた上で使う必要のあるテクだと思います。
上記のコードだと上書きになります。
たしかにマージテクを語る上ではキーが重複した場合のほうが重要かもしれませんね。
キーが重複したときに値をうまくマージしたいときにはブロック付きのほうを使います。
large.merge!(small) do |key, ours, theirs|
ours + theirs
end
これでキーが重複したときはその値の和になります。
# ブロックなし (上書き)
{ a: 1, b: 2 }.merge!({ a: 1, c: 2})
=> {:a=>1, :b=>2, :c=>2}
# ブロック付き (ブロック引数でマージ処理)
{ a: 1, b: 2 }.merge!({ a: 1, c: 2}){|k, a, b| a + b }
=> {:a=>2, :b=>2, :c=>2}
たまにマージ処理後にもうこのキーは不要なので削除したいというときがあるんですが、それはできないんですよね。
defaultと同じ値のときに削除にならないかなーと思うときがあります。