その差歴然 の続き。
設定がちょっと前者に厳しくないですか。
この例だと、
for ( int i = 0; i < N; i+= 10) {
vec.push_back(i); // ケツに追加して
}
std::sort(vec.begin(),vec.end()); // 再ソート
でもいいわけで
なるほど。ではさらに。
まとめて複数ケツに追加の後ソートするのなら、
追加する分をソートし、元ネタとマージ(併合)すれば
もっと早いすね。
そこを検証してみた。
#include は省略
int main() {
const int N = 80000;
std::vector vec;
DWORD t;
(ここで0～N-1をpush_back)
t = GetTickCount();
// 0～Nまで10刻みで要素を挿入
for ( int i = 0; i < N; i+= 10) {
vec.push_back(i); // 全部ケツに(昇順で)追加して
}
std::sort(vec.begin(),vec.end()); // 再ソート
std::cout << "push_back's and sort "
<< std::setw(5) << GetTickCount() - t << "[ms]\n";
(ここでclearし、0～N-1をpush_back)
t = GetTickCount();
// 0～Nまで10刻みで要素を挿入
for ( int i = 0; i < N; i+= 10) {
vec.push_back(i); // 全部ケツに(昇順で)追加して
}
std::inplace_merge(vec.begin(), vec.begin()+N, vec.end()); // マージ
std::cout << "push_back's and inplace_merge "
<< std::setw(5) << GetTickCount() - t << "[ms]\n";
}
実行結果:
push_back's and sort 16[ms]
push_back's and inplace_merge 0[ms]
要素数８万でも inplace_merge では計測にかかりまへん。
※ このテのアルゴリズム検証には手駒の揃ったC++が楽ちんですわ。
C++、きみも や・ら・な・い・か
[追記]Nを百万にしてみたところ、249[ms] vs. 32[ms] 8倍速ぇー♪