C++11のunordered_setと、setとの所要時間を比較する

C++11の標準ライブラリで新たに加わったunordered_setの練習として、従来のsetとの速度比較を行ってみる。

unrodered_setは、setと異なり、挿入した数字をソートせずに保存する。この性質はPythonのDictionaryやPerlのHashと同じ（はず）。単に出現した値を記録するデータ構造がほしいだけの場合、setでは無駄な処理が入ってしまうので、setを使うよりもunordered_setの方が高速であることが期待できる。

実験の方法は以下の通り。

• あらかじめ100万個の数字を用意。各数字は1から1000万までのどれかの値をランダムにとる
• setとunorder_setのそれぞれについて以下のことをする
  • 100万個の数字をすべて挿入
  • 挿入した数字を走査

書いたコードは以下。

#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <chrono>
#include <random>

using namespace std;

template<class T>
void print_elapsed_time( T start, T end )
{
    std::cout << "elapsed time = "
              << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count()
              << " msec."
              << std::endl;
}

int main()
{
    vector<int> numbers;
    const int NUM = 1000000;

    // 1からNUM*10までの範囲の一様乱数を返す準備
    std::mt19937 engine;
    std::uniform_int_distribution<int> distribution( 1, NUM*10 );

    // NUM個分のランダムな数字列をあらかじめ用意
    for(int i = 0; i < NUM; ++i) {
        numbers.push_back( distribution(engine) );
    }

    // setに値を挿入
    set<int> my_set;
    auto start = std::chrono::system_clock::now();
    for(auto num : numbers) {
        my_set.insert( num );
    }
    auto end = std::chrono::system_clock::now();
    cout << "set insert: ";
    print_elapsed_time(start, end);
    
    // setのすべての要素を走査
    start = std::chrono::system_clock::now();
    long long sum = 0;
    for(auto num : my_set) {
        sum += num;
    }
    cout << sum << endl;
    end = std::chrono::system_clock::now();
    cout << "set print: ";
    print_elapsed_time(start, end);

    // unordered_setに値を挿入
    unordered_set<int> my_uoset;
    start = std::chrono::system_clock::now();
    for(auto num : numbers) {
        my_uoset.insert( num );
    }
    end = std::chrono::system_clock::now();
    cout << "unordered_set insert: ";
    print_elapsed_time(start, end);

    // unordered_setのすべての要素を走査
    start = std::chrono::system_clock::now();
    sum = 0;
    for(auto num : my_uoset) {
        sum += num;
    }
    cout << sum << endl;
    end = std::chrono::system_clock::now();
    cout << "unordered_set print: ";
    print_elapsed_time(start, end);

    return 0;
}

Clangでコンパイルする。

$ clang++ -std=c++11 -stdlib=libc++ unordered_set.cpp 

実行結果は以下。

set insert: elapsed time = 1003 msec.
4755106825099
set print: elapsed time = 101 msec.
unordered_set insert: elapsed time = 705 msec.
4755106825099
unordered_set print: elapsed time = 59 msec.

setの所要時間に比べて、unordered_setの所要時間は、挿入では70.3%、走査では58.4%であった。やはりunordered_setの方がsetより高速という結果だった。