2013_07-12

2013年7月～12月

2013-09-28(SAT)

ちょい改良

前回のaccumulatedですが、範囲のコピーを保持していたため、範囲が大きなデータの場合、メモリを無駄に使うことになっていました。(前回のaccumulated.hppの47行目を参照。)

int main()
{
    std::vector<int> values;

    // valuesに値をたくさん追加

    auto sum = values | accumulated(0); // sumがvaluesのコピーを保持。メモリがMOTTAINAI。

    std::cout << sum << std::endl;
}

修正するには、範囲の参照を保持するように変更するのが手っ取り早いのですが、transformedのような他のRangeアダプタと仕組みをそろえるため(あと、お勉強のため)、boost::iterator_rangeを使うことにしました。他にも若干手直ししたので、再度、コード全体を貼り付けておきます。

#ifndef ___MY_UTILITY_RANGE_ADAPTOR_ACCUMULATED_HPP
#define ___MY_UTILITY_RANGE_ADAPTOR_ACCUMULATED_HPP


#include <numeric>
#include <iterator>
#include <boost/range/iterator_range.hpp>


namespace my_utility {

namespace detail {

template<typename ValueT, typename FuncT>
struct accumulate_holder_t
{
    typedef ValueT result_t;

    accumulate_holder_t(ValueT init, FuncT func)
        : Init(init), Func(func) {}

    ValueT Init;
    FuncT  Func;
};

template<typename ValueT>
struct accumulate_holder_t<ValueT, void>
{
    typedef ValueT result_t;

    accumulate_holder_t(ValueT init)
        : Init(init) {}

    ValueT Init;
};

template<typename InputRngT, typename HolderT>
struct accumulated_result_base_t
{
    typedef boost::iterator_range<typename boost::range_const_iterator<InputRngT>::type> range_t;

    accumulated_result_base_t(const InputRngT& rng, const HolderT& holder)
        : m_rng(rng), m_holder(holder) {}

    accumulated_result_base_t operator=(const accumulated_result_base_t& rhs)
    {
        m_rng    = rhs.m_rng;
        m_holder = rhs.m_holder;
 
        return *this;
    }

    range_t m_rng;
    HolderT m_holder;
};


template<typename InputRngT, typename ValueT, typename FuncT>
struct accumulated_result_t
    : private accumulated_result_base_t<InputRngT, accumulate_holder_t<ValueT, FuncT>>
{
    accumulated_result_t(const InputRngT& rng, const accumulate_holder_t<ValueT, FuncT>& acc)
        :  accumulated_result_base_t<InputRngT, accumulate_holder_t<ValueT, FuncT>>(rng, acc) {}

    operator typename accumulate_holder_t<ValueT, FuncT>::result_t() const
    {
        return std::accumulate(std::begin(m_rng), std::end(m_rng), m_holder.Init, m_holder.Func);
    }
};

template<typename InputRngT, typename ValueT>
struct accumulated_result_t<InputRngT, ValueT, void>
    : private accumulated_result_base_t<InputRngT, accumulate_holder_t<ValueT, void>>
{
    accumulated_result_t(const InputRngT& rng, const accumulate_holder_t<ValueT, void>& acc)
        :  accumulated_result_base_t<InputRngT, accumulate_holder_t<ValueT, void>>(rng, acc) {}

    operator typename accumulate_holder_t<ValueT, void>::result_t() const
    {
        return std::accumulate(std::begin(m_rng), std::end(m_rng), m_holder.Init);
    }
};

template<typename InputRngT, typename ValueT, typename FuncT>
inline accumulated_result_t<InputRngT, ValueT, FuncT>
operator|(const InputRngT& rng, const accumulate_holder_t<ValueT, FuncT>& acc)
{
    return accumulated_result_t<InputRngT, ValueT, FuncT>(rng, acc);
}

template<typename InputRngT, typename ValueT>
inline accumulated_result_t<InputRngT, ValueT, void>
operator|(const InputRngT& rng, const accumulate_holder_t<ValueT, void>& acc)
{
    return accumulated_result_t<InputRngT, ValueT, void>(rng, acc);
}

} // namespace detail

using detail::accumulated_result_t;

namespace adaptors {

template<typename ValueT, typename FuncT>
detail::accumulate_holder_t<ValueT, FuncT> accumulated(ValueT init, FuncT func)
{
    return detail::accumulate_holder_t<ValueT, FuncT>(init, func);
}

template<typename ValueT>
detail::accumulate_holder_t<ValueT, void> accumulated(ValueT init)
{
    return detail::accumulate_holder_t<ValueT, void>(init);
}

template<typename InputRngT, typename ValueT, typename FuncT>
accumulated_result_t<InputRngT, ValueT, FuncT> accumulate(const InputRngT& rng, ValueT init, FuncT func)
{
    return accumulated_result_t<InputRngT, ValueT, FuncT>(rng, accumulated(init, func));
}

template<typename InputRngT, typename ValueT>
accumulated_result_t<InputRngT, ValueT, void> accumulate(const InputRngT& rng, ValueT init)
{
    return accumulated_result_t<InputRngT, ValueT, void>(rng, accumulated(init));
}

} // namespace adaptors

template<typename InputRngT, typename ValueT, typename FuncT, typename IteratorT, typename ElemT, typename TraitsT>
inline std::basic_ostream<ElemT, TraitsT>&
    operator<<(std::basic_ostream<ElemT, TraitsT>& os,
               const accumulated_result_t<InputRngT, ValueT, FuncT>& acc_result)
{
    return os << static_cast<accumulate_holder_t::result_t>(acc_result);
}

} // namespace my_utility


#endif // ___MY_UTILITY_RANGE_ADAPTOR_ACCUMULATED_HPP

http://hrdr.nobody.jp/log/2013/2013_07-12.html#date20130928

2013-09-13(FRI)

Dの練習

問題：文字列 "0 1 2 3 4 5 6 7 8 9 10"に含まれる数値の合計を表示するプログラムを作成せよ。

……なんも考えずに書くと以下のようになります。(SyntaxHighlighterがDには流石に対応していなかったので、C#のブラシで代用します。。。)

import std.stdio;
import std.algorithm;
import std.conv;
import std.string;

void main()
{
    string text = "0 1 2 3 4 5 6 7 8 9 10";

    int sum = reduce!("a + b")(map!(to!int)(split(text)));

    writeln(sum);
}

意図した動作になりますが、1行にまとめて書く場合、上記のように関数呼び出しを入れ子にするよりも、メソッドチェイン形式で書いたほうが読みやすいです。例えば、C#でLINQを使って書くと以下のようになります。

using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        string text = "0 1 2 3 4 5 6 7 8 9 10";
        
        int sum = text.Split().Select(int.Parse).Sum();

        Console.WriteLine(sum);
    }
}

同様に、Rubyだと……。

text = "0 1 2 3 4 5 6 7 8 9 10"

sum = text.split.map(&:to_i).reduce(:+)

puts sum

Dには、UFCSという、関数の第一引数をオブジェクトに見立ててメソッドのように呼び出すことができる、かわった機能があります。それを使うと以下のようになります。

module main;

import std.stdio;
import std.algorithm;
import std.conv;
import std.string;

void main()
{
    string text = "0 1 2 3 4 5 6 7 8 9 10";

    int sum = text.split.map!(to!int).reduce!("a + b");

    writeln(sum);
}

RubyやC#に劣らぬ表現力、すばらしいです。ちなみに、これはシンタックスシュガーなので、Dの中の人(==コンパイラ)からは最初に示したコードと同じに見えます。

さて、ついで(?)なのでC++でもやってみましょう。まずは、C++標準だけを使って。

#include <string>
#include <sstream>
#include <iostream>
#include <vector>
#include <numeric>

int main()
{
    std::string text = "0 1 2 3 4 5 6 7 8 9 10";
    std::istringstream ss(text);

    std::vector<int> values((std::istream_iterator<int>(ss)), std::istream_iterator<int>());
    int sum = std::accumulate(std::begin(values), std::end(values), 0);

    std::cout << sum << std::endl;
}

STLのおかげで、Cで書くよりかはだいぶんマシだとは思いますが、DやC#のようにはいきませんね。次は、Boostも併用してみましょう。

#include <string>
#include <iostream>
#include <boost/tokenizer.hpp>
#include <boost/range/adaptor/transformed.hpp>
#include <boost/range/numeric.hpp>
#include <boost/lexical_cast.hpp>

using boost::tokenizer;
using boost::adaptors::transformed;
using boost::lexical_cast;
using boost::accumulate;

int main()
{
    std::string text = "0 1 2 3 4 5 6 7 8 9 10";

    int sum = accumulate(tokenizer<>(text) | transformed(lexical_cast<int, std::string>)), 0);

    std::cout << sum << std::endl;
}

1行に収まりましたが、accumulateで括られているのがちょっと残念です。上の例でも使っているRangeアダプタの「transformed」は、関数型言語でいうところの「map」や「collect」操作に対応します。なので、「reduce」や「inject」に対応する「accumulated」ってのがあるのかと思ってたんですが、どうやら存在しないようです。仕方ないので、自作することにしました。実装は後で示すとして、自作した「accumulated」を使うとこんな感じになります。

#include <string>
#include <iostream>
#include <boost/tokenizer.hpp>
#include <boost/range/adaptor/transformed.hpp>
#include <boost/lexical_cast.hpp>
#include "accumulated.hpp" // ← コレを自作

using boost::tokenizer;
using boost::adaptors::transformed;
using boost::lexical_cast;
using my_utility::adaptors::accumulated;

int main()
{
    std::string text = "0 1 2 3 4 5 6 7 8 9 10";

    int sum = tokenizer<>(text) | transformed(lexical_cast<int, std::string>) | accumulated(0);

    std::cout << sum << std::endl;
}

tokenizerのRangeアダプタ化、という改善の余地はありますが、十分スッキリしました。(tokenizedっていうRangeアダプタはあるんですけど、今回の問題には適用できませんでした。)そして、accumulated.hppの実装は以下のようになります。

#include <type_traits>
#include <boost/range/numeric.hpp>


namespace my_utility {

namespace detail {

template<typename ValueT, typename FuncT>
struct accumulated_t
{
    typedef ValueT value_t;
    typedef FuncT  func_t;

    accumulated_t(value_t init, func_t func)
        : Init(init), Func(func) {}

    value_t Init;
    func_t  Func;
};

template<typename ValueT>
struct accumulated_t<ValueT, void>
{
    typedef ValueT value_t;

    accumulated_t(value_t init)
        : Init(init) {}

    value_t Init;
};

template<typename ForwardRangeT, typename AccumulatedT>
struct accumulated_result_base_t
{
    accumulated_result_base_t(const ForwardRangeT& rng, const AccumulatedT& acc)
        : m_rng(rng), m_acc(acc) {}

    accumulated_result_base_t operator=(const accumulated_result_base_t& rhs)
    {
        m_rng = rhs.m_rng;
        m_acc = rhs.m_acc;

        return *this;
    }

    ForwardRangeT m_rng;
    AccumulatedT  m_acc;
};


template<typename ForwardRangeT, typename ValueT, typename FuncT>
struct accumulated_result_t
    : private accumulated_result_base_t<ForwardRangeT, accumulated_t<ValueT, FuncT>>
{
    accumulated_result_t(const ForwardRangeT& rng, const accumulated_t<ValueT, FuncT>& acc)
        :  accumulated_result_base_t<ForwardRangeT, accumulated_t<ValueT, FuncT>>(rng, acc) {}

    operator typename accumulated_t<ValueT, FuncT>::value_t() const
    {
        return boost::accumulate(m_rng, m_acc.Init, m_acc.Func);
    }
};

template<typename ForwardRangeT, typename ValueT>
struct accumulated_result_t<ForwardRangeT, ValueT, void>
    : private accumulated_result_base_t<ForwardRangeT, accumulated_t<ValueT, void>>
{
    accumulated_result_t(const ForwardRangeT& rng, const accumulated_t<ValueT, void>& acc)
        :  accumulated_result_base_t<ForwardRangeT, accumulated_t<ValueT, void>>(rng, acc) {}

    operator typename accumulated_t<ValueT, void>::value_t() const
    {
        return boost::accumulate(m_rng, m_acc.Init);
    }
};

template<typename ForwardRangeT, typename ValueT, typename FuncT>
inline accumulated_result_t<ForwardRangeT, ValueT, FuncT>
operator|(const ForwardRangeT& rng, const accumulated_t<ValueT, FuncT>& acc)
{
    return accumulated_result_t<ForwardRangeT, ValueT, FuncT>(rng, acc);
}

template<typename ForwardRangeT, typename ValueT>
inline accumulated_result_t<ForwardRangeT, ValueT, void>
operator|(const ForwardRangeT& rng, const accumulated_t<ValueT, void>& acc)
{
    return accumulated_result_t<ForwardRangeT, ValueT, void>(rng, acc);
}

} // namespace detail

using detail::accumulated_result_t;

namespace adaptors {

template<typename ValueT, typename FuncT>
detail::accumulated_t<ValueT, FuncT> accumulated(ValueT init, FuncT func)
{
    return detail::accumulated_t<ValueT, FuncT>(init, func);
}

template<typename ValueT>
detail::accumulated_t<ValueT, void> accumulated(ValueT init)
{
    return detail::accumulated_t<ValueT, void>(init);
}

template<typename ForwardRangeT, typename ValueT, typename FuncT>
accumulated_result_t<ForwardRangeT, ValueT, FuncT> accumulate(const ForwardRangeT& rng, ValueT init, FuncT func)
{
    return accumulated_result_t<ForwardRangeT, ValueT, FuncT>(rng, accumulated(init, func));
}

template<typename ForwardRangeT, typename ValueT>
accumulated_result_t<ForwardRangeT, ValueT, void> accumulate(const ForwardRangeT& rng, ValueT init)
{
    return accumulated_result_t<ForwardRangeT, ValueT, void>(rng, accumulated(init));
}

} // namespace adaptors

template<typename ForwardRange, typename ValueT, typename FuncT, typename IteratorT, typename ElemT, typename TraitsT>
inline std::basic_ostream<ElemT, TraitsT>&
    operator<<(std::basic_ostream<ElemT, TraitsT>& os,
               const accumulated_result_t<ForwardRange, ValueT, FuncT>& acc_result)
{
    return os << static_cast<AccumulatedT::value_t>(acc_result);
}

template<typename ForwardRange, typename ValueT, typename IteratorT, typename ElemT, typename TraitsT>
inline std::basic_ostream<ElemT, TraitsT>&
    operator<<(std::basic_ostream<ElemT, TraitsT>& os,
               const accumulated_result_t<ForwardRange, ValueT, void>& acc_result)
{
    return os << static_cast<AccumulatedT::value_t>(acc_result);
}

} // namespace my_utility

長げぇ。書いたはいいけど読めませんな。今回の問題を解くだけなら、operator|の中でboost::accumulateを呼び出すだけなのですが、無駄にがんばってしまって、std::accumulateと同様に関数(ラムダ式含む)を引数にとるオーバーロードを呼べるようにしたり、他のRangeアダプタと同様に処理を遅延させる機能を持たせてあります。なので、以下のような使い方もできます。

#include <iostream>
#include <boost/range/irange.hpp>
#include "accumulated.hpp"

using boost::irange;
using my_utility::adaptors::accumulated;

int _tmain()
{
    auto product = irange(1, 5) | accumulated(1, [](int a, int b){ return a * b; });

    std::cout << product << std::endl;
}

ここで、10行目の変数productの型はintではなく、特殊化されたaccumulated_result_tという型になります。この型はキャスト演算子を定義しており(accumulated.hppの59行目参照)、accumulatedの第1引数に渡された初期値の型にキャストされるときまで、処理を遅延させます。なので、上の例の10行目では、まだ「総乗」の計算は行われていません。また、operator<<も用意しており(accumulated.hppの124行目参照)、この中でキャストを行うようにしています。よって上の例では、12行目ではじめて計算が行われ、表示されることになります。

なお、処理を遅延させる必要がなければ、autoを使わずにintで受け取るようにすると、暗黙的なキャストにより、その行で処理が実行されます。

やっぱり、C++は楽しいなぁ。って、何の練習だったんだっけ？

http://hrdr.nobody.jp/log/2013/2013_07-12.html#date20130913

2013-07-21(SUN)

さいきょうのぷろぐらみんぐげんご

今年覚えるプログラミング言語は、D言語にしよう。まだ、プログラミング言語Dを読んだだけですが、以下のようなポイントが気に入りました。

関数プログラミングのサポート: 今どきのプログラミング言語なら常識だよね、という感じですが。
メッセージパッシング方式の並行処理: 並行処理で有名なプログラミング言語Erlangもこれですよね。こっちのほうがスレッドよりも自分好み。
std.algorithm: C++の<algorithm>や<boost/range/algorithm.hpp>になじみがあれば、すぐに使えるライブラリ。
言語がサポートするunittest: 外部ライブラリなしでユニットテストが書けるのは楽ちんです。関数のすぐそばに書けるのもよいところ。
in引数: C++でいうところの引数のconst参照渡しです。C#だとこれができないんですよねぇ。
開発者の1人がAndrei Alexandrescuさん。: Modern C++ Designで有名な人ですね。この人にだったらC++をdisられても嫌な気にならないから不思議。

これはOperaですか？いいえ、Opera15です。

Opera15を入れてみたけど、操作性とカスタマイズ性が退化してて、Opera12に戻ってきました。Operaのように扱えない時点で、Opera15はOperaに非ず。僕がOperaを使い始めてから、今年でちょうど10年になりますが、そんなキリのいい年にどうして……。

Opera12のサポートが切られるのが先か、Opera15がOperaになれるのが先か。「拡張機能で実現」ってやり方は嫌いです。探して取ってくるのがめんどくさいのですよ。

http://hrdr.nobody.jp/log/2013/2013_07-12.html#date20130721

春鳥 -ハルドリ-