やりたいこと
Enumerable#tally はレシーバの要素を == で比較して、同じものが何個ずつ含まれているのかを調べ、その結果を Hash オブジェクトで返してくれます。
やりたいのは、例えば、複数の配列を通じて、同じ要素が何個ずつあるか数えたいということです。今回は、次のような ary の例で考えてみます。
ary = Array.new(200) do
Array.new(20) { rand(1..5) }
end
素朴だが効率の良くない方法
その１ ー tally で計算した結果をマージする
ary.map(&:tally).then do |hashes|
{}.merge!(*hashes) { |_key, old, new| old + new }
end
=> {1=>759, 3=>801, 4=>833, 2=>851, 5=>756}
素朴で単純な方法ですが、Hash オブジェクトを200個も作った上で、それらをマージしなければならず、無駄です。
その２ ー ary を平坦化して tally する
単純に考えて、二重配列を平坦化すれば、一つのレシーバになるので、これに tally すれば上手くいくはずです。
ary.flatten.tally => {1=>759, 3=>801, 4=>833, 2=>851, 5=>756}
こんなふうにちゃんと計算できました。しかし、巨大な配列をわざわざ作るのは無駄で、美しくありません。
当然のことながら、Hash オブジェクトを使い回して、累積した計算結果が求められたら、巨大な配列を作る必要はありません。こんな感じです。
counter = Hash.new(0)
ary.each { |enum| enum.each { |e| counter[e] += 1 } }
counter
これを、Ｃで書かれた tally で実現できれば最強・最速なはずです。
結果を使い回せる tally を考えてみる。
Ruby で書くと、こんな感じです。
module Enumerable
def tally(counter = {})
each { |e| counter[e] = counter.fetch(e, 0) + 1 }
counter
end
end
Paul Graham の arc（ダウンロードはここ）を参考にしています。arc では、次のような counts 関数が定義されています。
(def counts (seq (o c (table)))
(if (no seq)
c
(do (++ (c (car seq) 0))
(counts (cdr seq) c))))
(let tbl (table)
(counts '(1 2) tbl)
(counts '(1 3) tbl)) => #hash((1 . 2) (2 . 1) (3 . 1))
計算結果が使い回せていますね。ちなみに、(o c (table)) の o は 仮引数 c が optional であり、(table) を評価して作られる hash がその初期値になることを意味します。
これを Ruby で再現すると、
def counts(ary, counter = {})
if ary.empty?
counter
else
e, *rest = ary
counter[e] = counter.fetch(e, 0) + 1
counts(rest, counter)
end
となります。より Ruby 的にすると、
def counts(ary, counter = {})
ary.each do |e|
counter[e] = counter.fetch(e, 0) + 1
end
counter
end
となって、ここから先ほど書いた、あったら良いなという tally につながっていきます。この tally があれば、
counter = {}
ary.each { |enum| enum.tally(counter) }
counter => {1=>759, 3=>801, 4=>833, 2=>851, 5=>756}
と書けます。Ｃで実装されていれば、速いはずです。さらに、
ary.each_with_object({}) { |enum, counter| enum.tally(counter) }
とか
ary.each_with_object({}, &:tally)
と書けます。（最後の例では、ブロック・パラメータの順序の関係で、reduce はできません。）
どうして Ruby は計算結果を使い回そうとしなかったのだろう。
現実に戻って、Enumerable#chain を使う
Array#flatten で巨大な配列を作るのはバカらしいけど、chain で Enumerator オブジェクトを一つ作るだけであれば、はるかにスマートです。ただ、chain を使うには、レシーバとなる Enumerable なオブジェクトが必要になります。そこで、やむなく、
ary[0].chain(*ary[1..]).tally
とすることになりますが、少し不格好です。更にやむなく、多重代入を使うことにします。
enum, *rest = ary
enum.chain(*rest).tally
スッキリ書けましたが、enum や rest で名前空間を汚したくありませんよね。そこで、
ary.then { |enum, *rest| enum.chain(*rest).tally }
のようにするとＯＫです。
ただ、ary をわざわざ分割するのはバカらしいことです。だって、ruby の内部では、rb_ary_cat を使って、enum と rest をもう一度一つの配列につなぎ合わせて処理をしているからです。
それなら、いっそのこと、
[].chain(*ary).tally
にすればどうか。何と、一番スッキリした感じになりました。
「これで決まり！」と言いたいところですが、無駄に空の配列を chain しているのが気になります。
Kernel#chain(*enums) があれば、スッキリするな〜。
chain(*ary).tally
結論
Enumerable#tally(counter = {}) や Kernel#chain(*enums) を実装してほしい。
どなたか、もっとスマートな方法があれば、お教えください。
追記１
コメント欄で @obelisk68 さんとやり取りをしていて分かったことですが、Kernel#chain(*enums) だと、配列の要素をわざわざスタックに展開するという無駄な処理をすることになるので、Kernel#.chain(enums) の方が使い勝手がいいかもしれません。
全体が一つの配列になっていないのであれば、単純に Enumerable#chain(*enums) を使えば良いわけですから。
ただ、いろいろ考えると、Enumerator オブジェクトを作るのだから、Enumerator.product にならって
class Enumerator
def self.chain(enums)
Enumerator.new do |y|
enums.each {|enum| enum.each(&y) }
end
end
end
が良いのかな？ これがあると、
Enumerator.chain(ary).tally
追記２
これも @obelisk68 さんに教えてもらった、ary.lazy.flat_map ... の件です。
整合性とか考えていませんが、lazy なオブジェクトを返す Enumerator::Lazy.flatten があれば、
ary.lazy.flatten.tally
とできて、良いのではないかと思いました。乱暴な書き方をすると、
class Enumerator::Lazy
def flatten
flat_map(&:itself)
end
end
的なものです。