Mapを使わないでSummary - エンジニアのソフトウェア的愛情

おさらい。

昨日（日付的には今日ですけど）、最後に「なんかよくわかんないんですけど、なんかしっくりこないところが。なんだろ？」って書いたんですが、「いろいろとやり方を変えてみても集計しているサマリデータの中からキーが一致するものを探して値を加算するということはMapを使ってるのと一緒にならないだろうか？」という点だった模様。

よくよく読み返してみたら「データをキーでソートしておいて」とあります。もとのコードも確かにソートされていることを前提としたコードになってた。ひとの話はよく聴きましょう（というか読みましょう）。

キーブレイク処理というのは、データをキーでソートしておいて順番に読み込み、キーが同じ値の間に処理（よくあるのが集計）を続ける。キーが違う値になったら（キーがブレイクしたら）集計値を出力し、集計用変数をクリアしてまた処理を続ける。というアルゴリズムです。

キー毎に値を集計する方法 - ひしだまの変更履歴

あぁ、たしかに。キーがソートしてあれば（完全なソートでなくても、コンテナの中でキーが同じ要素がかならず連続した状態になっていれば）、かつオンメモリで処理をするのでなければ、こういう処理使いますね。「キーブレイク処理」という名前がついていたのか…知らんかった。
オンメモリでなく、ソースからシンクへとデータを流し続けるような場合だったら、こんな感じで書いてます、私の場合。

#include <iostream>
#include <string>
#include <vector>

struct Data
{
    std::string code;
    std::string name;
    int         value;
};

// データの出力先
struct Sink
{
    std::ostream& out;

    Sink(std::ostream& out) : out(out) {}

    void output(const std::string& code, int sum)
    {
        out << code << ", " << sum << "\n";
    }
};

// source から入力を得て、そのサマリを sink へ出力する
void summary(const std::vector<Data>& source, Sink& sink)
{
    // 要素の数がゼロなら即終了
    if(source.empty())
    {
        return;
    }

    // 1番目の要素を初期値にする
    std::vector<Data>::const_iterator d    = source.begin();
    std::string                       code = d->code;
    int                               sum  = d->value;
    ++d;

    // 2番目以降の要素の処理
    for(; d != source.end(); ++d)
    {
        if(d->code == code)
        {
            // キーが同じなら集計を続ける
            sum += d->value;
        }
        else
        {
            // キーが変化したら、

            // それまでの集計結果を出力する
            sink.output(code, sum);

            // 新しいキーの要素を初期値にする
            code = d->code;
            sum  = d->value;
        }
    }

    // 最後に集計していた結果を出力する
    sink.output(code, sum);
}

int main(int, char* [])
{
    Data data[] = { { "A01", "hoge", 100},
                    { "A01", "piyo", 200},
                    { "A02", "hoge", 300},
                    { "A03", "hoge", 400},
                    { "A03", "piyo", 500} };


    std::vector<Data> source(data, data + sizeof(data) / sizeof(data[0]));
    Sink              sink(std::cout);

    summary(source, sink);

    return 0;
}

おまけ：Haskellで

マップを使うやり方ですけど、一応書けたので晒しておきます。

import List

summary src = [ (code subsrc, foldr (+) 0 [ v | (_, _, v) <- subsrc]) | subsrc <- groupBy (\(c1, _, _) (c2, _, _) -> c1 == c2) src]
  where
    code []            = ""
    code ((c, _, _):_) = c

source = [ ("A01", "hoge", 100),
           ("A01", "piyo", 200),
           ("A02", "hoge", 300),
           ("A03", "hoge", 400),
           ("A03", "piyo", 500) ]

main = mapM_ (putStrLn.(\(c,s) -> c ++ ", " ++ show s)) $ summary source