Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2012-04-18

競技プログラミングのためのD言語(4/2)

21:47 | はてなブックマーク - 競技プログラミングのためのD言語(4/2) - cafelier@SRM

言語というかライブラリによって意外と違うのが標準入出力の速度で、入力サイズ N の線形オーダ O(N) で解かないといけない類の問題では、注意しないとデータを読み込むだけでタイムアウトするのも日常茶飯事です。その辺の心配はないのか調べてみました(今までDでそういう問題解いたことがなかったのでした…)。以下、

  • 100万未満の自然数が一行に3個、100万行、のランダムデータの総和を計算
  • gcc 4.7.0 と dmd 2.059
  • Core i7 2.7GHz の Windows7PowerShell の Measure-Command コマンドで5回測定して中間値

をとった結果です(単位は秒)。最適化ありというのは g++ -O3 と dmd -O -release -inline で、なしというのは引数なし。

プログラム最適化あり最適化なし
(1) C++ iostream (手抜き)5.2245.428
(2) C++ iostream (真面目)1.1191.155
(3) C++ scanf0.4990.507
(4) D readln+split+to!int1.0781.529
(5) D readln+split+map!(to!int)1.0721.545
(6) D readf1.9582.335
(7) D scanf1.3931.410

なにかの優劣比較をしたいわけではないので、まったくひとかけらも厳密なベンチマークではありませんが、結論としては、まあ readln + split で問題ないのではないでしょうか、と思いました。というか、だいたいこんなオーダなのでOnline JudgeにD言語を入れる人は参考にしていただければという感じです。あと iostream が遅くてコンテストで困るという人はまずは tie(0) と sync_with_stdio(false) を (定期発言)。

// (1) C++ iostream (手抜き)
#include <iostream>
using namespace std;

int main() {
	long long total = 0;
	for(int a,b,c; cin>>a>>b>>c; )
		total += a+b+c;
	cout << total << endl;
}
// (2) C++ iostream (真面目)
#include <iostream>
using namespace std;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	long long total = 0;
	for(int a,b,c; cin>>a>>b>>c; )
		total += a+b+c;
	cout << total << endl;
}
// (3) C++ scanf
#include <cstdio>
using namespace std;

int main() {
	long long total = 0;
	for(int a,b,c; scanf("%d%d%d",&a,&b,&c)==3; )
		total += a+b+c;
	printf("%lld\n", total);
}
// (4) D readln + split + to!int
import std.array;
import std.conv;
import std.stdio;

void main() {
	long total = 0;
	for(string s; (s=readln()).length; ) {
		auto ss = s.split();
		int a = ss[0].to!int();
		int b = ss[1].to!int();
		int c = ss[2].to!int();
		total += a+b+c;
	}
	writeln(total);
}
// (5) D readln + split + map!(to!int)
import std.algorithm;
import std.array;
import std.conv;
import std.stdio;

void main() {
	long total = 0;
	for(string s; (s=readln()).length; ) {
		auto ss = s.split().map!(to!int);
		total += ss[0]+ss[1]+ss[2];
	}
	writeln(total);
}
// (6) D readf
import std.array;
import std.conv;
import std.stdio;

void main() {
	long total = 0;
	for(int a,b,c; readf("%d %d %d\n",&a,&b,&c); )
		total += a+b+c;
	writeln(total);
}
// (7) D scanf
import std.c.stdio;

void main() {
	long total = 0;
	for(int a,b,c; scanf("%d%d%d\n",&a,&b,&c)==3; )
		total += a+b+c;
	printf("%lld\n", total);
}
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/cafelier/20120418
 | 

presented by cafelier/k.inaba under CC0