ネタ元 → ソートぉ、な話。
ソートされた配列にあらたな要素を追加するとき、
末尾に追加して再度ソート するよりは
挿入点を探して押し込む 方が速かろ?
検証してみた:
#include <windows.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>
int main() {
const int N = 20000;
std::vector<int> vec;
for ( int i = 0; i < N; ++i ) {
vec.push_back(i);
}
DWORD t;
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 and sort "
<< std::setw(5) << GetTickCount() - t << "[ms]\n";
vec.clear();
for ( int i = 0; i < N; ++i ) {
vec.push_back(i);
}
t = GetTickCount();
// 0～Nまで10刻みで要素を挿入
for ( int i = 0; i < N; i+= 10) {
std::vector<int>::iterator iter // 挿入点を見つけて
= std::lower_bound(vec.begin(), vec.end(), i);
vec.insert(iter, i); // そこにねぢ込む
}
std::cout << "binary_search and insert "
<< std::setw(5) << GetTickCount() - t << "[ms]\n";
}
実行結果:
push_back and sort 2063[ms]
binary_search and insert 15[ms]
後者の方が100倍以上速いっす。