[c++] stringのコピーが遅かった件

stringオブジェクトのコピーは遅い

先日行われた AtCoder Beginner Contest 199 のC問題において、
「ある大きな二つの文字列変数の中身を入れ替える」という操作を何回も繰り返す状況を考慮する必要があった。¹

以下のコードでは、長さ10万ちょっとの二つの文字列を入れ替える操作を10万回繰り返すのに要する時間を計測している。10回計測を行い、最後にその平均値を出力する。

exchange.cpp

# include <iostream>
using namespace std;
using namespace std::chrono;

int main(void){
    string s1 = "abcdefg...."; // s1.size() == 100464
    string s2 = "zyxwvut...."; // s2.size() == 100464

    int cnt = 0;
    long long total = 0;

    while(cnt < 10) {
	    auto start = high_resolution_clock::now();

	    for(int i = 0; i < 100000; i++) {
	      string tmp = s1;
	      s1 = s2;
	      s2 = tmp;      
	    }

	    auto stop = high_resolution_clock::now();
	    auto duration = duration_cast<milliseconds>(stop - start);
	    total += duration.count();

	    cout << "cnt=" << cnt << ":" << duration.count() << " ms." << endl;

	    cnt++;
	  }

	  cout << "avg:" << total / (double)10 << " ms." << endl;
}

結果は次の通り：

	時間
0	1713 ms
1	1706 ms
2	1699 ms
3	1726 ms
4	1677 ms
5	1681 ms
6	1714 ms
7	1704 ms
8	1706 ms
9	1696 ms
avg.	1702.2 ms

このように、入れ替える文字列が巨大で操作回数も大きい場合、実行に時間がかかってしまう。

なぜ遅いか？

何気なく書いたコードに、文字列長が大きい時にそれに合わせて時間計算量も大きくなる箇所があった。

原因1: コピーコンストラクタ

copy_constructor

string tmp = s1;

この行では string::basic_string のコピーコンストラクタが呼ばれる。時間計算量はO(N)となり、代入しようとする右辺の文字列長(s1)に比例する。(https://ja.cppreference.com/w/cpp/string/basic_string/basic_string)
上記の例では、長さ100464の文字列をコピーするという処理を10万回繰り返すため、相応の時間がかかると思われる。

原因2: コピー演算子

'='operator

s1 = s2;
s2 = tmp;

この2行では、string::basic_string のコピー演算子が呼ばれる。時間計算量はやはりO(N)となり、代入しようとする右辺の文字列長に比例する。(https://ja.cppreference.com/w/cpp/string/basic_string/operator%3D)

stringオブジェクトを高速に入れ替える方法はあるか？

swap を使用する。(https://ja.cppreference.com/w/cpp/string/basic_string/swap)

swap.cpp

# include <iostream>
using namespace std;
using namespace std::chrono;

int main(void){
    string s1 = "abcdefg...."; // s1.size() == 100464
    string s2 = "zyxwvut...."; // s2.size() == 100464

    int cnt = 0;
    long long total = 0;

    while(cnt < 10) {
	    auto start = high_resolution_clock::now();

	    for(int i = 0; i < 100000; i++) {
	      s1.swap(s2);
	    }

	    auto stop = high_resolution_clock::now();
	    auto duration = duration_cast<milliseconds>(stop - start);
	    total += duration.count();

	    cout << "cnt=" << cnt << ":" << duration.count() << " ms." << endl;

	    cnt++;
	  }

	  cout << "avg:" << total / (double)10 << " ms." << endl;
}

結果は次の通り：

	時間
0	3 ms
1	2 ms
2	2 ms
3	2 ms
4	2 ms
5	3 ms
6	2 ms
7	3 ms
8	2 ms
9	2 ms
avg.	2.3 ms

違いは歴然としている。時間計算量はO(1)となり、入れ替える文字列長に依らず、一定時間となる。

なお、swap は std::basic_string::swap のメンバー関数以外にも、std::swap があり、それを用いても記述可能。すなわち、以下のようにも記述できる。

swap(s1, s2);

1. この操作しなくても解けます。むしろそちらの方が想定解です。 ↩