LoginSignup
41
28

More than 5 years have passed since last update.

@sileader

C++コンテナの速度比較

Last updated at Posted at 2017-06-26

概要

C++は様々なコンテナを持っていますがそれぞれ内部的なアルゴリズムが異なるので、特性や得意分野を知ることは効率の良いプログラムを作る上で有用だと考え、比較してみようと思いました。

unordered_mapとmapの速度比較

unordered_mapとmapですが、全く異なるデータ構造で作られているので面白い結果を出してくれると思います。

使ったプログラム

#include <chrono>
#include <iostream>

#ifdef TEST_USE_MAP
#   include <map>
namespace {
    template<class K, class V>using map=std::map<K, V>;
}
#else
#   include <unordered_map>
namespace {
    template<class K, class V>using map=std::unordered_map<K, V>;
}
#endif


namespace {
    template<class TimePoint>void elapsed_time(const std::string& msg, const TimePoint& start, const TimePoint& end) {
        std::cout<<msg<<" : "<<std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count()<<" ミリ秒"<<std::endl;
    }
}

int main() {
    constexpr std::size_t ELEMENT_COUNT=10000000;

    map<std::string, std::string> str_str_umap;

    std::string s;
    // 要素の追加
    auto start=std::chrono::high_resolution_clock::now();
    for(std::size_t i=0; i<ELEMENT_COUNT; ++i) {
        s=std::to_string(i);
        str_str_umap[s]=s;
    }
    auto end=std::chrono::high_resolution_clock::now();
    elapsed_time("要素の追加", start, end);

    // 要素の走査(キーからの走査)
    start=std::chrono::high_resolution_clock::now();
    for(std::size_t i=0; i<ELEMENT_COUNT; ++i) {
        s=std::to_string(i);
        str_str_umap.at(s);
    }
    end=std::chrono::high_resolution_clock::now();
    elapsed_time("要素の走査(キー)", start, end);

    // 要素の走査(範囲for)
    start=std::chrono::high_resolution_clock::now();
    for(const auto& sp : str_str_umap) {
    }
    end=std::chrono::high_resolution_clock::now();
    elapsed_time("要素の走査(範囲for)", start, end);

    // 要素の削除
    start=std::chrono::high_resolution_clock::now();
    for(std::size_t i=0; i<ELEMENT_COUNT; ++i) {
        s=std::to_string(i);
        str_str_umap.erase(s);
    }
    end=std::chrono::high_resolution_clock::now();
    elapsed_time("要素の削除", start, end);
}

# std::mapバージョン
$ clang++ -std=c++14 -O0 -DTEST_USE_MAP -o map map.cpp

# std::unordered_mapバージョン
$ clang++ -std=c++14 -O0 -DTEST_USE_UMAP -o umap map.cpp

結果

要素の追加

回数 map unordered_map
1 17823 9643
2 17644 9601
3 17641 9674
4 17617 9888
5 17836 9672
平均 17712.2 9695.6

unordered_mapのほうが1.8倍速いようです。

要素の走査(キー)

回数 map unordered_map
1 10952 5168
2 10727 5315
3 10715 5343
4 10702 5463
5 10689 5193
平均 10757 5296.4

unordered_mapのほうが2倍速いです。

要素の走査(範囲for)

回数 map unordered_map
1 375 874
2 374 854
3 376 849
4 373 892
5 373 858
平均 374.2 865.4

これは意外だったのですがmapのほうが2.3倍速いようです。

要素の削除

回数 map unordered_map
1 13363 6643
2 13565 6815
3 13214 6558
4 13178 6839
5 13301 6481
平均 13324.2 6667.2

unordered_mapのほうが2倍程度速いです。

結論

範囲for以外はunordered_mapのほうが2倍近く速いです。

vectorとdeque

コンテナとしてはvectorが割と有名ですが、dequeもqueueやstackに使われます。

使ったプログラム

#include <iostream>
#include <string>
#include <chrono>

#ifdef TEST_USE_DEQUE
#   include <deque>
namespace {
    template<class T>using list=std::deque<T>;
}
#else
#   include <vector>
namespace {
    template<class T>using list=std::vector<T>;
}
#endif

namespace {
    template<class Duration> void print_time(const std::string& msg, const Duration& time, const std::string& t="ミリ秒") {
        std::cout<<msg<<" : "<<time.count()<<" "<<t<<std::endl;
    }

    template<class Duration, class TimePoint>
    void elapsed_time(const std::string& msg, const TimePoint& start, const TimePoint& end, const std::string& t="ミリ秒") {
        print_time(msg, std::chrono::duration_cast<Duration>(end-start), t);
    }
}

int main() {
    constexpr std::chrono::milliseconds _0ms(0);
    constexpr std::size_t ELEMENT_COUNT=10000000;

    list<std::string> str_list;

    std::string s="1";

    // 要素の追加(push_back)
    auto start=std::chrono::high_resolution_clock::now();
    for(std::size_t i=0; i<ELEMENT_COUNT; ++i) {
        str_list.push_back(s);
    }
    auto end=std::chrono::high_resolution_clock::now();
    elapsed_time<std::chrono::milliseconds>("要素の追加(push_back)", start, end);

    // 要素の追加(insert)
    std::chrono::milliseconds time(_0ms);
    for(std::size_t i=0; i<ELEMENT_COUNT; i+=100000) {
        auto itr=std::begin(str_list);
        start=std::chrono::high_resolution_clock::now();
        str_list.insert(itr, s);
        end=std::chrono::high_resolution_clock::now();
        time+=std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    }
    print_time("要素の先頭への追加(insert)", time);

    str_list.clear();

    // 要素の追加(emplace_back)
    start=std::chrono::high_resolution_clock::now();
    for(std::size_t i=0; i<ELEMENT_COUNT; ++i) {
        str_list.emplace_back(s);
    }
    end=std::chrono::high_resolution_clock::now();
    elapsed_time<std::chrono::milliseconds>("要素の追加(emplace_back)", start, end);

    // 要素の追加(emplace)
    time=_0ms;
    for(std::size_t i=0; i<ELEMENT_COUNT; i+=100000) {
        auto itr=std::begin(str_list);
        start=std::chrono::high_resolution_clock::now();
        str_list.emplace(itr, s);
        end=std::chrono::high_resolution_clock::now();
        time+=std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    }
    print_time("要素の先頭への追加(emplace)", time);

    // 要素の走査(すべての要素)
    start=std::chrono::high_resolution_clock::now();
    for(std::size_t i=0; i<ELEMENT_COUNT; ++i) {
        str_list.at(i);
    }
    end=std::chrono::high_resolution_clock::now();
    elapsed_time<std::chrono::milliseconds>("要素の走査(すべての要素)", start, end);

    // 要素の走査(範囲for)
    start=std::chrono::high_resolution_clock::now();
    for(const auto& sp : str_list) {
    }
    end=std::chrono::high_resolution_clock::now();
    elapsed_time<std::chrono::milliseconds>("要素の走査(範囲for)", start, end);

    // 要素の走査(最初と最後)
    start=std::chrono::high_resolution_clock::now();
    str_list.front();
    str_list.back();
    end=std::chrono::high_resolution_clock::now();
    elapsed_time<std::chrono::nanoseconds>("要素の走査(最初と最後)", start, end, "ナノ秒");

    // 要素の削除
    start=std::chrono::high_resolution_clock::now();
    for(std::size_t i=0; i<ELEMENT_COUNT; i+=10000) {
        str_list.erase(std::begin(str_list));
    }
    end=std::chrono::high_resolution_clock::now();
    elapsed_time<std::chrono::nanoseconds>("要素の削除", start, end, "ナノ秒");
}

# std::dequeバージョン
$ clang++ -std=c++14 -O0 -DTEST_USE_DEQUE -o deque list.cpp

# std::vectorバージョン
$ clang++ -std=c++14 -O0 -DTEST_USE_VECTOR -o vector list.cpp

forの再初期化式が+=になっているものはどちらかの処理が遅すぎるものです。

結果

要素の追加(push_back)

回数 vector deque
1 973 338
2 989 336
3 860 342
4 896 343
5 984 381
平均 940.4 348

領域を大きくするときのコピー量の違いかdequeのほうが速い結果になりました。

要素の先頭への追加(insert)

回数 vector deque
1 9051 0
2 8994 0
3 8872 0
4 9124 0
5 9037 0
平均 9015.6 0

先頭への追加は圧倒的にdequeのほうが速いという結果になりました。

要素の追加(emplace_back)

回数 vector deque
1 233 284
2 236 284
3 235 285
4 236 287
5 235 281
平均 235 284.2

やっぱりpush_backよりは速いです。
vectorとdequeは僅差でvectorの勝利です。

要素の先頭への追加(emplace)

回数 vector deque
1 9022 0
2 8835 0
3 8923 0
4 8997 0
5 9030 0
平均 8961.4 0

dequeのほうが圧倒的に速いです。
insertよりも速いという結果になりました。

要素の走査(すべての要素)

回数 vector deque
1 106 1099
2 106 1094
3 105 1093
4 105 1098
5 105 1087
平均 105.4 1094.2

これはすごい差がでました。
vectorは安定して速いという感じですね。

要素の走査(範囲for)

回数 vector deque
1 95 114
2 95 111
3 95 112
4 95 111
5 96 111
平均 95.2 111.8

範囲forはvectorのほうが速いという結果になりました。
これもvectorは安定して速いです。

要素の走査(最初と最後)

回数 vector deque
1 350 371
2 382 409
3 358 395
4 315 356
5 320 384
平均 345 383

そんなに差がでませんでした。
一応全部vectorのほうが速いです。

要素の削除(先頭)

回数 vector deque
1 103401672961 151526
2 103364671055 151700
3 103953655253 150569
4 104234321618 149700
5 102828393379 151875
平均 103556542853.2 151074

これは見てもらえば解ると思いますが、vectorで先頭の要素を何度も削除してはいけません。
この数値はナの秒単位なので、桁が大きすぎますがdequeのほうが圧倒的に速いです。

結論

先頭やその近くの要素の削除を頻繁に行うときはdequeを使ったほうが良さそうです。

環境

CPU : Intel Core i5 2500 3.30GHz
メモリ : 16GiB DDR3 1333MHz
OS : Linux Mint 18 x64

41
28
5

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
41
28