複数の Enumerable なオブジェクトで tally したい【追記あり】

やりたいこと

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

的なものです。