読者です 読者をやめる 読者になる 読者になる

C++入力の速度測定

double型でも調べてみました

動機

Welcome To PKU JudgeOnline で想定解法が  O(n \log n) の問題(3873 -- Trick or Treat)をC++で解いた時に、標準入力に cin を使ってTLE(Time Limit Exceeded) となりました.
この時の対策として scanf を使うか、

[cin 高速化]
cin.tie(0);
ios::sync_with_stdio(false);

を使用するかのどちらかですが後者を使っても TLE が取れなくて、scanf にしたら問題が AC(Accept) されたので入力の測定をしてみることにしました.
上のソースコードを使用することを便宜上cin高速化と呼ぶことにします.

測定対象のプログラム

測定する対象は入力を次の3つの方法で行うプログラムです.

  1. cinを使うプログラム
  2. cin高速化を使うプログラム
  3. scanfを使うプログラム

それぞれのプログラムに対して、最適化なしと最適化あり(-O2オプション)の2通りを試しました.
また、各々の計測時間は下の各々の入力に対して 10 回測定した時間の平均としています.

入力

入力は次の形式のテキストで、サイズ  N 10^3, 10^4, 10^5, 10^6, 10^7, 10^8 としました.
それぞれの  a_{i}, b_{i} (1 \le i \le N) はランダムに生成しています.
また、int型とdouble型で実験を行いました.
double型は時間の都合上 N = 10^8 の場合は行いませんでした.

[入力形式]
a_{1} b_{1}
a_{2} b_{2}
・
・
・
a_{N} b_{N}

実験環境

  • [コンパイラ] gcc version 4.8.2
  • [OS] Ubuntu 14.04.1 LTS 64bit
  • [メモリ] 3.8GiB
  • [プロセッサ] Intel® Core™ i3-2120 CPU @ 3.30GHz × 4
  • [ディスク] 488.0GB

実験結果(int型)

f:id:tatanaideyo:20141024211223p:plain

[入力の違いによる時間計測](int型)
データサイズ cin cin -O2 cin高速化 cin高速化 -O2 scanf scanf -O2
 10^3 0.5 0.8 0.0 0.0 0.0 0.0
 10^4 9.5 11.5 3.2 2.7 2.1 3.0
 10^5 84.0 84.5 22.9 23.6 23.1 23.5
 10^6 884.0 836.6 215.0 213.2 207.0 212.4
 10^7 8395.2 8380.3 2112.5 2091.7 2051.8 2113.1
 10^8 87023.5 86472.2 24647.7 24250.0 25305.3 28142.5

実験結果(double型)

f:id:tatanaideyo:20141024223732p:plain

[入力の違いによる時間計測](double型)
データサイズ cin cin -O2 cin高速化 cin高速化 -O2 scanf scanf -O2
 10^3 1.2 2.4 0.4 1.0 0.3 0.2
 10^4 19.5 20.2 9.4 11.5 7.7 6.4
 10^5 194.2 192.0 88.7 94.6 55.5 59.4
 10^6 1874.9 1882.7 902.0 895.1 557.5 564.0
 10^7 18974.3 18645.1 9162.2 8851.1 5507.6 5564.8

まとめ

計測結果としては、

[int型]
cin高速化-O2 < cin高速化 < scanf << scanf -O2 <<<< cin -O2 << cin

[double型]
scanf < scanf -O2 <<< cin高速化 -O2 << cin高速化 <<<< cin -O2 << cin

でした.
double型の方が時間がかかることは知りませんでした.
(zeosuttさんありがとうございます.)
何故、POJでcin高速化が通らないかは謎ですがPOJだからということで諦めてscanfを使うようにします.
(だぶん世の中にはもっと不可思議なことがあるのでそれの訓練)

ソースコード

[cin]
#include <iostream>
#include <cstdio>
#include <chrono>

using namespace std;

int main()
{
    auto start = std::chrono::high_resolution_clock::now();

    int a, b;

    while (cin >> a >> b) {

    }

    auto end = std::chrono::high_resolution_clock::now();
    auto take_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << take_time.count() << "\n";

    return 0;
}
[cin高速化]
#include <iostream>
#include <cstdio>
#include <chrono>

using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    auto start = std::chrono::high_resolution_clock::now();

    int a, b;

    while (cin >> a >> b) {

    }

    auto end = std::chrono::high_resolution_clock::now();
    auto take_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout  << take_time.count() << "\n";

    return 0;
}
[scanf]
#include <iostream>
#include <cstdio>
#include <chrono>

using namespace std;

int main()
{
    auto start = std::chrono::high_resolution_clock::now();

    int a, b;

    while (~scanf("%d %d", &a, &b)) {

    }

    auto end = std::chrono::high_resolution_clock::now();
    auto take_time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << take_time.count() << "\n";

    return 0;
}