エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

キーブレイク処理とフィルタの関係について

前回のエントリで「ソースからシンクへとデータを流し続けるような場合」の例として、コンテナからシンクオブジェクトへとデータを流すコードを書きました。

よくよく考えてみると、「コンテナそのものを渡すよりもイテレータで範囲を渡す方がよい(STLもこの考え方にそって作られています)」「シンクオブジェクトもイテレータとして実装できる」ということに気がつきました。
入出力をイテレータに抽象化することで入出力の形式にとらわれることなく処理を書けるはずです。


せっかくなのでもう一段。キーブレイクの判定、初期値の設定、集計計算も外から指定できるようにすれば、入力するデータの型、出力するデータの型からも独立することができるはず。


以上を踏まえて、書き直してみたのがこれ。

#ifndef SUMMARY_H
#define SUMMARY_H

// begin から end までの入力を得て、その集計結果を sink へ出力する関数テンプレート
template< typename SourceType,
          typename SinkType,
          typename InputIterator,
          typename OutputIterator,
          typename Translator,
          typename Comparator,
          typename Accumulator >
void summary( const InputIterator& begin,       // 入力元の先頭
              const InputIterator& end,         // 入力元の末尾
              OutputIterator       out,         // 出力先
              Translator           translate,   // 入力したデータを出力するデータの型に変換する関数
              Comparator           isKeyBroken, // キーブレイクを検出する関数
              Accumulator          accumulate ) // 集計の計算をする関数
{
    // 入力がなければすぐに終了
    if(begin == end)
    {
        return;
    }

    InputIterator i = begin;

    // 1番目の要素を積算の初期値にする
    SinkType sink = translate(*i);
    ++i;

    // 2番目以降の要素の処理
    while(i != end)
    {
        if(isKeyBroken(sink, *i))
        {
            // キーブレイクしたら、

            // それまでの集計結果を出力する
            out++ = sink;

            // 新しいキーの要素を初期値にする
            sink = translate(*i);
        }
        else
        {
            // キーブレイクしていないなら、集計を続ける
            accumulate(sink, *i);
        }

        ++i;
    }

    // 最後に集計していた結果を出力する
    out++ = sink;
}

#endif//KEYBREAK_H


こうやって書き下してみると。これは入力するデータ列を出力するデータ列へと変換するフィルタそのもの。grepuniqと同列で考えることができそうです。事前にソートしておく必要があるところなんかuniqとそっくりかも。

実例、その1

vectorに格納してある入力データを集計してvectorに書き出す例。
集計した結果を最後に標準出力に出力しています。

#include "summary.h"

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>

// 入力を得るデータの型
struct Source
{
    std::string code;
    std::string name;
    int         value;

    Source(const std::string& code, const std::string& name, int value) : code(code), name(name), value(value) {}
};

// 出力するデータの型
struct Sink
{
    std::string code;
    int         sum;

    Sink(const std::string& code, int sum) : code(code), sum(sum) {}
};

// Sink を出力するための挿入演算子(ostream_iterator で使用する)
std::ostream& operator << (std::ostream& out, const Sink& sink)
{
    return out << sink.code << ", " << sink.sum;
}

// キーブレイクを判定する(キーブレイクしたら true 、していなければ false を返す)
bool isKeyBroken(const Sink& sink, const Source& source)
{
    return source.code != sink.code;
}

// 入力したデータを出力するデータの型に変換する
Sink translate(const Source& source)
{
    return Sink(source.code, source.value);
}

// 入力したデータを集計する(第1引数に集計結果を保存するデータ、第2引数に集計する入力データ)
void accumulate(Sink& sink, const Source& source)
{
    sink.sum += source.value;
}

int main(int, char* [])
{
    std::vector<Source> source;
    std::vector<Sink>   sink;

    // 入力するデータを作る
    source.push_back(Source("A01", "hoge", 100));
    source.push_back(Source("A01", "piyo", 200));
    source.push_back(Source("A02", "hoge", 300));
    source.push_back(Source("A03", "hoge", 400));
    source.push_back(Source("A03", "piyo", 500));

    // 集計する
    summary<Source, Sink>( source.begin(),
                           source.end(),
                           std::back_inserter(sink),
                           translate,
                           isKeyBroken,
                           accumulate );

    // 集計結果を出力する
    std::copy(sink.begin(), sink.end(), std::ostream_iterator<Sink>(std::cout, "\n"));

    return 0;
}


実行結果。前回と同じなので省略。

実例、その2

標準入力から直接入力を得て、集計結果を標準出力へ直接出力します。

#include "summary.h"

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>

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

struct Sink
{
    std::string code;
    int         sum;

    Sink(const std::string& code, int sum) : code(code), sum(sum) {}
};

std::istream& operator >> (std::istream& in, Source& source)
{
    return in >> source.code >> source.name >> source.value;
}

std::ostream& operator << (std::ostream& out, const Sink& sink)
{
    return out << sink.code << ", " << sink.sum;
}

bool isKeyBroken(const Sink& sink, const Source& source)
{
    return source.code != sink.code;
}

Sink translate(const Source& source)
{
    return Sink(source.code, source.value);
}

void accumulate(Sink& sink, const Source& source)
{
    sink.sum += source.value;
}

int main(int, char* [])
{
    std::istream_iterator<Source> begin(std::cin);      // 標準入力から入力イテレータを作る
    std::istream_iterator<Source> end;                  // 入力イテレータの終端を作る
    std::ostream_iterator<Sink>   out(std::cout, "\n"); // 標準出力から出力イテレータを作る

    summary<Source, Sink>( begin,
                           end,
                           out,
                           translate,
                           isKeyBroken,
                           accumulate );

    return 0;
}


実行結果。

$ cat source.txt 
A01 hoge 100
A01 piyo 200
A02 hoge 300
A03 hoge 400
A03 piyo 500
$ ./summary2 < source.txt > sink.txt
$ cat sink.txt
A01, 300
A02, 300
A03, 900

実例、Haskellでは?

抽象化ならばHaskellが得意とするところなんじゃないだろうか、と、考え始めたまではいいんですが、スキル不足で途中から先に進めなくなってしまいました。

summary関数をghciに読み込ませて関数の型を見ているとこんな感じになります。

Prelude Summary> :t summary
summary
  :: (Monad m) =>
     (t -> t1)
     -> (t1 -> t -> Bool)
     -> (t1 -> t -> t1)
     -> (t1 -> m a)
     -> m a
     -> [t]
     -> m a


出力の型は任意のモナドにすることができたようなのですが、入力にはリストを要求しています。これも任意のモナドにできないかとしばらく考えたんですが挫折。モナドの理解が不充分。入力がないときのための値を用意しないといけないのも、なんか不格好ですし。


ともかく。できたところまで晒しておきます。

module Summary
  where

summary _ _ _ _ nosource [] = nosource
summary translate isKeyBroken accumulate output _ (s:ss) = summary_ (translate s) ss
  where
    summary_ sink [] = output sink
    summary_ sink (s:ss)
      | isKeyBroken sink s = output sink >> summary_ (translate s) ss
      | otherwise          = summary_ (accumulate sink s) ss


標準入力から入力を得て、集計結果を直接標準出力へ出力します。

module Main
  where

import Summary

data Source = Source String String Integer
data Sink   = Sink String Integer

translate (Source c n v)                = Sink c v
isKeyBroken (Sink c1 _) (Source c2 _ _) = c1 /= c2
accumulate (Sink c1 s) (Source _ _ v)   = Sink c1 (s + v)
output (Sink c s)                       = putStrLn $ c ++ " " ++ show s

toSource []         = []
toSource [""]       = []
toSource (c:n:v:ss) = (Source c n (read v::Integer)):(toSource ss)

main = getContents >>= return.toSource.words
                   >>= summary translate isKeyBroken accumulate output (return ())