C++ Advent Calendar 2011 18日目

とりあえずPDFにしたところで力尽きたので公開。
ブログ形式には後で変えます。たぶん。
https://docs.google.com/open?id=0Bz3ia7nrCMfHY2EzZjdmNjItNGVhNy00NTM4LWEyY2MtMTYwMTczNjJhZTNm

はてダよりLatexの方が慣れてるとかほんとブログ書く気ないなあ・・

つぎのC++11 Advent Calendar 2011は@hotwartermorning (id:heisseswasser)さんです！

追記：書くつもりで書き忘れてましたけどstd::thread関連は
http://www.justsoftwaresolutions.co.uk/threading/multithreading-in-c++0x-part-1-starting-threads.htmlのシリーズを読むといいと思います

FortranでFizzBuzz

C++でfor文とか、FortranでDO文とか、使ったら負けです。

program fizzbuzz
    integer,parameter :: N = 20
    integer :: i
    character(8),dimension(N) :: list
    write(list,'(I4)') (/(i,i=1,N)/)
    where(mod((/(i,i=1,N)/),3)==0)  list="fizz"
    where(mod((/(i,i=1,N)/),5)==0)  list="buzz"
    where(mod((/(i,i=1,N)/),15)==0) list="fizzbuzz"
    print '(a)',list
end program fizzbuzz

http://ideone.com/jotnRに置いてみる

数字混じり文字列のソートをBoost.Xpressiveで

元ネタはここ(http://ja.doukaku.org/295/)なんですが、
札幌C++勉強会で扱ったのでちょっとやってみる。

方針は比較関数で文字列と数値に分けて、それぞれの場合で処理を分けてるだけ。

#include<iostream>
#include<string>
#include<vector>
#include<fstream>
#include<boost/lexical_cast.hpp>
#include<boost/xpressive/xpressive.hpp>
#include<boost/xpressive/regex_actions.hpp>

struct Compare {
	typedef std::pair<std::string,int> Pair;

	bool operator()(const std::string& str1,const std::string& str2) const
	{
		using namespace boost::xpressive;
		std::vector<Pair> vec1,vec2;
		sregex re1 = make_regex(vec1), re2 = make_regex(vec2);

		// 数字と数字以外の文字列に分けてvecに入れる
		// 詳しくはCompare::make_regexメンバ関数を参照
		sregex_token_iterator(str1.begin(),str1.end(),re1);
		sregex_token_iterator(str2.begin(),str2.end(),re2);

		std::vector<Pair>::iterator
			begin1=vec1.begin(),end1=vec1.end(),
			begin2=vec2.begin(),end2=vec2.end();
		
		for(;begin1!=end1 && begin2!=end2;++begin1,++begin2) {
			if(begin1->second==0&&begin2->second==0){ // 数字
				const int d1 = boost::lexical_cast<int>(begin1->first);
				const int d2 = boost::lexical_cast<int>(begin2->first);
				if(d1<d2) return true;
				else if(d1>d2) return false;
			}
			else { // 数字以外
				const std::string& s1 = begin1->first;
				const std::string& s2 = begin2->first;
				if(s1<s2) return true;
				else if(s1>s2) return false;
			}
		}
		return false;
	}

	boost::xpressive::sregex make_regex(std::vector<Pair>& v) const {
		using namespace boost::xpressive;
		// 数字の場合は文字列と0のペア
		// 数字以外の場合は文字列と1のペアとして
		// vectorに入れる、という正規表現
		sregex re = +( 
				(s1=+_d)[
					push_back(ref(v), make_pair(s1,0))] | 
				(s2=+~_d)[
					push_back(ref(v), make_pair(s2,1))]
				);
		return re;
	}
};

int main(int argc,char** argv) {
	using namespace boost::xpressive;
	typedef std::pair<std::string,int> Pair;
	if(argc!=2) return -1;
	std::ifstream ifs(argv[1]);
	std::vector<std::string> lines;
	for(std::string str;std::getline(ifs,str);){
		lines.push_back(str);
		std::cout << str << std::endl;
	}
	std::cout << "sorted: " <<  std::endl;
	std::sort(lines.begin(),lines.end(),Compare());
	std::copy(lines.begin(),lines.end(),std::ostream_iterator<std::string>(std::cout,"\n"));
	return 0;
}

細かい仕様についてはよく知らないので、何かミスがあるかも。
あとパフォーマンスとかは考えてないので、このままでは実際には使えないですね。
文字列比較の度に正規表現でサーチしてますし。
効率を考えるならすべてトークン分割した状態でコンテナに保持させてからソートした方がよさそう。

最初boost::tupleでやってmake_tupleではコンパイル通らなかったけども(これを通すために悩んだ)
どうやらmake_pairしか用意されてないようだ。

iostream vs stdio

結論としてiostream vs stdioではなく、ofstream vs fprintfの比較になってますもう過去に幾度と無くされてきた戦争な気がするのでドキュメントとして残す。

iostreamはデフォルトでstdioより遅い。
ただし、http://homepage1.nifty.com/herumi/diary/0812.html#25 のように
tie(0) + sync_with_stdio(false)を読んでおけば改善される（はず）

といってもベンチマークをとらないと何ともいえないので検証。

ってことでまずは検証ソース(ツッコミ歓迎、ちなみに560Mほどのファイルが出るので注意)

#include<cstdio>
#include<vector>
#include<iostream>
#include<fstream>
#include<boost/timer.hpp>

const int loop_max = 5;
const int NX=256,NY=256,NZ=256;
const int DX=1./NX,DY=1./NY,DZ=1./NZ;

void iotest_stdio(const std::vector<double>& data) {
	FILE* fp=fopen("data.dat","w");
	for(int c=0;c<loop_max;++c) {
		for(int i=0;i<NX;++i) {
			for(int j=0;j<NY;++j) {
				for(int k=0;k<NZ;++k) {
					const double x=i*DX,y=j*DY,z=k*DZ;
					fprintf(fp,"%f %f %f\n",x,y,z,data[i*NX*NY+j*NY+k]);
				}
			}
		}
	}
	fclose(fp);
}
void iotest_stream(const std::vector<double>& data) {
	std::ofstream ofs("data.dat");
	for(int c=0;c<loop_max;++c) {
		for(int i=0;i<NX;++i) {
			for(int j=0;j<NY;++j) {
				for(int k=0;k<NZ;++k) {
					const double x=i*DX,y=j*DY,z=k*DZ;
					ofs << x << " " << y << " " << z << " "
						<< data[i*NX*NY+j*NY+k];
				}
			}
		}
	}
}

int main() {
	std::vector<double> data(NX*NY*NZ);
	{
		std::cout << "iotest stdio : ";
		boost::timer timer;
		iotest_stdio(data);
		const double elapsed = timer.elapsed();
		std::cout << elapsed << std::endl;
	}
	{
		std::cout << "iotest stream without tie(0)+sync_with_stdio(false) : ";
		boost::timer timer;
		iotest_stream(data);
		const double elapsed = timer.elapsed();
		std::cout << elapsed << std::endl;
	}
	{
		std::cout << "iotest stream with tie(0)+sync_with_stdio(false) : ";
		std::cin.tie(0);
		std::ios::sync_with_stdio(false);
		boost::timer timer;
		iotest_stream(data);
		const double elapsed = timer.elapsed();
		std::cout << elapsed << std::endl;
	}
	return 0;
}

結果(環境はLinux,g++ (GCC) 4.4.5 20101112 (Red Hat 4.4.5-2), -O3最適化)
iotest stdio : 51.38
iotest stream without tie(0)+sync_with_stdio(false) : 114.49
iotest stream with tie(0)+sync_with_stdio(false) : 114.55

tie(0) + sync_with_stdio(false)で改善されなかった！あれ？

追記：

らしいので再度検証

あと

というコメントのように今回はofstreamしか使ってないのでcin.tie(0)は関係ないはずです。あってもなくても変わらないはずなので消さずに入れてます。無駄・・

再検証結果
sync_with_stdio(false)をつけた場合のmain関数を次のように変えてます。
他は上記ソースと同じ

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::vector<double> data(NX*NY*NZ);
    {
        std::cout << "iotest stream with tie(0)+sync_with_stdio(false) : ";
        boost::timer timer;
        iotest_stream(data);
        const double elapsed = timer.elapsed();
        std::cout << elapsed << std::endl;
    }
    return 0;
}

iotest stdio : 51.15
iotest stream without tie(0)+sync_with_stdio(false) : 114.12
iotest stream with tie(0)+sync_with_stdio(false) : 113.29

誤差の範囲でしか変わらないですね。ツッコミまだまだ歓迎です
ちなみにtieとsync_with_stdioの呼び出し順を逆にしても同じ。

さらに追記：

真偽や詳細なところはまだ不明ですが、たしかにcinはもちろんsync_with_stdioだって"stdio"って言ってるし、fstreamでは関係ないかも。
ということで今回の検証は単純にfprintfとofstreamの比較ということで終わり？
stdioでの比較してませんけど、私の場合、数ＧＢ単位のデータ出力となるのでファイルへのIO以外は意味が無い。ってことで他の人にパス。

PLplotのexampleひどすww

PLplotのexample03があまりにもひどかった
→ https://plplot.svn.sourceforge.net/svnroot/plplot/trunk/examples/c++/x03.cc

ちなみにPLplotの使い方は https://sites.google.com/site/makeplplot/ がよくまとまっている。

PLplot自体はいいライブラリだと思うんだけど、C++bindingは"例が"ひどすぎる。
でもライブラリのインターフェイスを書きなおす気は起きないので
簡単に使える方法を模索。
例えば、使い方としてはplstreamを継承してしまうのはどうだろう？
(std::shared_ptrを使ってるのでC++11で)

#include<iostream>
#include<string>
#include<vector>
#include<memory>
#include<plstream.h>

class Plots : plstream {
public:
    Plots(int argc,const char** argv) {
        parseopts(&argc, argv, PL_PARSE_FULL);
        scolbg(255,255,255);
        scol0(15, 0, 0, 0);
        // sdev("aqt");  // AquaTerm
        init();
    }
    void plot(int num,
            std::vector<double>& ax,
            std::vector<double>& ay)
    {
        col0(15);
        env(-1.3,1.3,-0.3,1.3,1,1);
        lab("X", "Y", "y=x#u2#d");
        col0(1);
        wid(3);
        line(num,&ax[0],&ay[0]);
    }
};

int main(int argc,const char** argv) {
    std::shared_ptr<Plots> pls(new Plots(argc,argv));

    const int num = 30;
    std::vector<double> ax(num),ay(num);

    const double x_min=-1.0, x_max=1.0;
    for(int i=0;i<num;++i) {
        ax[i] = x_min+(x_max-x_min)/(num-1.0)*i;
        ay[i] = ax[i]*ax[i];
    }

    pls->plot(num,ax,ay);
    return 0;
}

少しはましかな？

ぷよぷよの消去アルゴリズム

元ネタ > http://okajima.air-nifty.com/b/2011/01/2011-ffac.html

#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<valarray>
typedef std::vector<std::vector<int> > Field;
const int width=6;
const std::string data =
"  GYRR"
"RYYGYG"
"GYGYRR"
"RYGYRG"
"YGYRYG"
"GYRYRG"
"YGYRYR"
"YGYRYR"
"YRRGRG"
"RYGYGG"
"GRYGYR"
"GRYGYR"
"GRYGYR" 
;
// 表示
void disp(const Field& field) {
	const int height = field[0].size();
	for(int i=0;i<height;++i) {
		for(int j=0;j<width;++j) {
			std::cout<<static_cast<char>(field[j][i]);
		}
		std::cout<<std::endl;
	}
}
// 転置
template<class T> std::valarray<T>
transpose( const std::valarray<T>& A, const int column) {
	const int row=A.size()/column;
	std::valarray<size_t> n(2),s(2);
	n[0]=column;n[1]=row;s[0]=1;s[1]=column;
	return A[std::gslice(0,n,s)];
}
// 配置データ(width*height)からField型(height*width)に変換
Field convert(std::string str) {
	const int height = str.size()/width;
	std::valarray<std::string::value_type> tmp(str.c_str(),str.size());
	std::valarray<std::string::value_type> trans = transpose(tmp,width);
	Field field;
	for(int i=0;i<width;++i) {
		field.push_back(std::vector<int>(&trans[i*height],&trans[(i+1)*height]));
	}
	return field;
}
// paint(flagで同じ色を塗りつぶす。塗った箇所もついでに数える)
int paint(Field& field,const int x,const int y,int flag) {
	const int height = field[0].size();
	const int now = field[x][y];
	if(now==flag||now==' ')return 0;
	field[x][y]=flag;

	const int nx[] = {x  ,x  ,x-1,x+1};
	const int ny[] = {y-1,y+1,y,  y  };
	int count=1;
	for(int i=0;i<4;++i) {
		if(nx[i]>=0&&nx[i]<width&&ny[i]>=0&&ny[i]<height
				&&field[nx[i]][ny[i]]==now&&field[nx[i]][ny[i]]==now){
			count+=paint(field,nx[i],ny[i],flag);
		}
	}
	return count;
}
// ぷよを消す
// 消す場所がなくなったらfalseを返す
bool Clear(Field& field) {
	const int height = field[0].size();
	const int mflag= 'x', rflag = 'N';
	Field mask(field);
	for(int i=0;i<width;++i) {
		for(int j=0;j<height;++j) {
			// 一回目のpaintで数えて、二回目で消すフラグを立てる
			if(paint(mask,i,j,mflag)>=4) paint(field,i,j,rflag);
		}
	}
	bool check=false;
	for(int i=0;i<width;++i) {
		std::vector<int>::reverse_iterator itr
			=std::remove_if(field[i].rbegin(),field[i].rend(),
					std::bind1st(std::equal_to<int>(),rflag));
		std::fill(itr,field[i].rend(),' ');
		check |= itr!=field[i].rend();
	}
	return check;
}

int main() {
	Field field=convert(data);
	for(int i=0;Clear(field);++i) {
		std::cout<<"["<<i<<"]"<<std::endl;
		disp(field);
	}
	return 0;
}

optionalとbindとphoenix

boost::optional::getをbindにかけたいと思っていろいろ試したメモ
結論はphoenix使え。

以下いろいろ試したソース

#include<iostream>
#include<boost/optional.hpp>
#include<boost/phoenix/phoenix.hpp>
#include<boost/lambda/lambda.hpp>

int main(const int argc,const char** argv) {
    using boost::phoenix::bind;
    using boost::phoenix::arg_names::arg1;
    boost::optional<int> opt(4);
    // (1)
    std::cout << opt.get() << std::endl; // OK
    std::cout << *opt << std::endl; // OK

    // (2-1)
    (std::cout << *arg1 << std::endl)(opt); // OK
    std::cout << (*arg1)(opt) << std::endl; // OK

    // (2-2)
//  (std::cout << *boost::lambda::_1 << "\n")(opt); // lambdaだとNG
//  std::cout << (*boost::lambda::_1)(opt) << std::endl; // もちろんこれもNG


    // (3-1)
//  std::cout << 
//      bind(&boost::optional<int>::get, arg1)(opt) // NG
//      << std::endl;
    // (3-2)
    std::cout << 
        bind(
            static_cast<int const&(boost::optional<int>::*)()const>
                (&boost::optional<int>::get),
            arg1)(opt) // OK
        << std::endl;
    // (3-3)
    (std::cout <<
        bind(
            static_cast<int const&(boost::optional<int>::*)()const>
                (&boost::optional<int>::get),
            arg1)
        << std::endl)(opt);  // OK
    return 0;
}

(1)は普通にoptionalを使う場合。やりたいのはこれの関数化
(2-1)はphoenixを使って関数化して、引数にoptを渡している。っていうかこれで十分bindいらない。
(2-2)は(2-1)と似てるけど、Boost.Lambdaバージョン。これはコンパイル通らない。さっさとBoost.Phoenixに乗り換えよう。
(3-1,2,3)は問題のbindで呼び出すパターン。(3-1)は通らない。(3-2,3)はコンパイル通る。けど普通の人はこんなのすぐに書けない、よね？

(3-3)を使えば(std::cout..)を関数化できるけど、どう考えても(2-1)の方がいい。