5
私はあるコードでmapを使って注文データを保存していました。巨大な地図では、破壊には時間がかかることが分かった。私が持っていたこのコードでは、10000でmapvector<pair>によって減少し、処理時間を交換...私はどのような状況std :: map <A,B>は、並べ替えられたstd :: vector <std :: pair <A,B>>より速くなりますか？
最後に、私は私がソートさvectorまたはpairでmap性能を比較することを決めたので驚きました。
そして、私は状況を見つけることができなかったので、私は驚いてはどこmap他.... mapが高速であるいくつかの状況が存在しなければならない... pairのvectorソート（ランダムに充填され、後にソートされた）よりも速かったですこのクラスを提供する際のポイントは何ですか？ここで
は、私がテストしたものです：
テスト1、ソート（私は、ソートのコンテナをしたいので）と破壊、map充填を比較し、vector充填対破壊：
g++ main.cpp -O3 -o mainとGOTでコンパイル
#include <iostream>
#include <time.h>
#include <cstdlib>
#include <map>
#include <vector>
#include <algorithm>
int main(void)
{
clock_t tStart = clock();
{
std::map<float,int> myMap;
for (int i = 0; i != 10000000; ++i)
{
myMap[ ((float)std::rand())/RAND_MAX ] = i;
}
}
std::cout << "Time taken by map: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;
tStart = clock();
{
std::vector< std::pair<float,int> > myVect;
for (int i = 0; i != 10000000; ++i)
{
myVect.push_back(std::make_pair(((float)std::rand())/RAND_MAX, i));
}
// sort the vector, as we want a sorted container:
std::sort(myVect.begin(), myVect.end());
}
std::cout << "Time taken by vect: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;
return 0;
}
：
Time taken by map: 21.7142
Time taken by vect: 7.94725
mapの3倍遅く...
、私は私がテストした....「OK、ベクトルは埋めるために、より速く、ソートですが、検索がマップに速くなります」、言った：
#include <iostream>
#include <time.h>
#include <cstdlib>
#include <map>
#include <vector>
#include <algorithm>
int main(void)
{
clock_t tStart = clock();
{
std::map<float,int> myMap;
float middle = 0;
float last;
for (int i = 0; i != 10000000; ++i)
{
last = ((float)std::rand())/RAND_MAX;
myMap[ last ] = i;
if (i == 5000000)
middle = last; // element we will later search
}
std::cout << "Map created after " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;
float sum = 0;
for (int i = 0; i != 10; ++i)
sum += myMap[ last ]; // search it
std::cout << "Sum is " << sum << std::endl;
}
std::cout << "Time taken by map: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;
tStart = clock();
{
std::vector< std::pair<float,int> > myVect;
std::pair<float,int> middle;
std::pair<float,int> last;
for (int i = 0; i != 10000000; ++i)
{
last = std::make_pair(((float)std::rand())/RAND_MAX, i);
myVect.push_back(last);
if (i == 5000000)
middle = last; // element we will later search
}
std::sort(myVect.begin(), myVect.end());
std::cout << "Vector created after " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;
float sum = 0;
for (int i = 0; i != 10; ++i)
sum += (std::find(myVect.begin(), myVect.end(), last))->second; // search it
std::cout << "Sum is " << sum << std::endl;
}
std::cout << "Time taken by vect: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;
return 0;
}
はg++ main.cpp -O3 -o mainでコンパイルして得た：
vectorと明らかに速くなり
Map created after 19.5357
Sum is 1e+08
Time taken by map: 21.41
Vector created after 7.96388
Sum is 1e+08
Time taken by vect: 8.31741
（mapで10件の検索設定は、ほぼ2秒を取り、それがvectorと半分だけ秒かかりました）
So：
- 私は何かを見逃しましたか？
- 私のテストは正解/正確ではありませんか？
mapは単純にクラスを回避するか、実際にはmapのパフォーマンスが良い状況がありますか？
オペレーション間の順序を維持する必要がある場合（たとえば、挿入の間にルックアップがある場合など）、既存のコンテナに大量の挿入があります。マップにソートされたベクトルに10kのランダムな値を挿入してみてください。 –
何もテストしたことがありません（例：要素の削除についてはどうすればよいですか？）。しかし、一般的には、ノードベースのデータ構造は非常にキャッシュに不相応です。 –
@Revolver_Ocelot：ありがとう、それがポイントだったし、私はそれを逃した。テストをしました（下記の答えを参照してください）、そして、そうです、 'map'はついに速くなりました。 – jpo38