针对关于与未搜索数量相关的性能问题的提问,我已经重构了测试以参数化此问题。
示例结果:
searches |
set_size |
miss |
ordered |
unordered |
flat_map |
1000000 |
0 |
100% |
4384 |
12901 |
681 |
1000000 |
99 |
99.99% |
89127 |
42615 |
86091 |
1000000 |
172 |
99.98% |
101283 |
53468 |
96008 |
1000000 |
303 |
99.97% |
112747 |
53211 |
107343 |
1000000 |
396 |
99.96% |
124179 |
59655 |
112687 |
1000000 |
523 |
99.95% |
132180 |
51133 |
121669 |
1000000 |
599 |
99.94% |
135850 |
55078 |
121072 |
1000000 |
695 |
99.93% |
140204 |
60087 |
124961 |
1000000 |
795 |
99.92% |
146071 |
64790 |
127873 |
1000000 |
916 |
99.91% |
154461 |
50944 |
133194 |
1000000 |
988 |
99.9% |
156327 |
54094 |
134288 |
关键:
searches = number of searches performed against each map
set_size = how big each map is (and therefore how many of the searches will result in a hit)
miss = the probability of generating a missed search. Used for generating searches and set_size.
ordered = the time spent searching the ordered map
unordered = the time spent searching the unordered_map
flat_map = the time spent searching the flat map
note: time is measured in std::system_clock::duration ticks.
TL;DR
结果:当地图中有数据时,unordered_map显示出其优越性。唯一比有序地图表现更差的情况是地图为空的时候。
这是新代码:
#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <tuple>
#include <future>
#include <stdexcept>
#include <sstream>
using namespace std;
static const size_t key_length = 20;
const size_t nkeys = 1000000;
struct string_user
{
virtual void sink(const std::string&) = 0;
virtual ~string_user() = default;
};
struct real_string_user : string_user
{
virtual void sink(const std::string&) override
{
}
};
struct real_string_user_print : string_user
{
virtual void sink(const std::string& s) override
{
cout << s << endl;
}
};
std::unique_ptr<string_user> make_sink(const std::string& name)
{
if (name == "print")
{
return make_unique<real_string_user_print>();
}
if (name == "noprint")
{
return make_unique<real_string_user>();
}
throw logic_error(name);
}
auto gen_string = [](auto& engine, auto& dist)
{
std::string result(key_length, ' ');
generate(begin(result), end(result), [&] {
return dist(engine);
});
return result;
};
struct pair_less
{
bool operator()(const pair<string, string>& l, const string& r) const {
return l.first < r;
}
bool operator()(const string& l, const pair<string, string>& r) const {
return l < r.first;
}
};
template<class F>
auto time_test(F&& f, const vector<string> keys)
{
auto start_time = chrono::system_clock::now();
for (auto const& key : keys)
{
f(key);
}
auto stop_time = chrono::system_clock::now();
auto diff = stop_time - start_time;
return diff;
}
struct report_key
{
size_t nkeys;
int miss_chance;
};
std::ostream& operator<<(std::ostream& os, const report_key& key)
{
return os << "miss=" << setw(2) << key.miss_chance << "%";
}
void run_test(string_user& sink, size_t nkeys, double miss_prob)
{
unordered_map<string, string> unordered;
map<string, string> ordered;
vector<pair<string, string>> flat_map;
vector<string> keys;
unordered_set<string> keys_record;
auto eng = std::default_random_engine(std::random_device()());
auto alpha_dist = std::uniform_int_distribution<char>('A', 'Z');
auto prob_dist = std::uniform_real_distribution<double>(0, 1.0 - std::numeric_limits<double>::epsilon());
auto generate_new_key = [&] {
while(true) {
auto key = gen_string(eng, alpha_dist);
if(keys_record.insert(key).second) {
return key;
}
}
};
for (size_t i = 0 ; i < nkeys ; ++i)
{
bool inserted = false;
auto value = to_string(i);
auto key = generate_new_key();
if (prob_dist(eng) >= miss_prob) {
unordered.emplace(key, value);
flat_map.emplace_back(key, value);
ordered.emplace(key, std::move(value));
}
keys.emplace_back(std::move(key));
}
sort(begin(flat_map), end(flat_map),
[](const auto& l, const auto& r) { return l.first < r.first; });
shuffle(begin(keys), end(keys), eng);
auto unordered_lookup = [&](auto& key) {
auto i = unordered.find(key);
if (i != end(unordered)) {
sink.sink(i->second);
}
};
auto ordered_lookup = [&](auto& key) {
auto i = ordered.find(key);
if (i != end(ordered)) {
sink.sink(i->second);
}
};
auto flat_map_lookup = [&](auto& key) {
auto i = lower_bound(begin(flat_map),
end(flat_map),
key,
pair_less());
if (i != end(flat_map) && i->first == key) {
sink.sink(i->second);
}
};
auto unordered_future = async(launch::async,
[&]()
{
return time_test(unordered_lookup, keys);
});
auto ordered_future = async(launch::async, [&]
{
return time_test(ordered_lookup, keys);
});
auto flat_future = async(launch::async, [&]
{
return time_test(flat_map_lookup, keys);
});
auto ordered_time = ordered_future.get();
auto unordered_time = unordered_future.get();
auto flat_time = flat_future.get();
cout << "searches=" << setw(7) << nkeys;
cout << " set_size=" << setw(7) << unordered.size();
cout << " miss=" << setw(7) << setprecision(6) << miss_prob * 100.0 << "%";
cout << " ordered=" << setw(7) << ordered_time.count();
cout << " unordered=" << setw(7) << unordered_time.count();
cout << " flat_map=" << setw(7) << flat_time.count() << endl;
}
int main()
{
stringstream ss;
ss << "noprint";
string arg;
ss >> arg;
auto puser = make_sink(arg);
for (double chance = 1.0 ; chance >= 0.0 ; chance -= 0.0001)
{
run_test(*puser, 1000000, chance);
}
return 0;
}
map
的问题并不在于它本身的log N
,而是在于遍历树时每次内存访问都是基本随机的。当 map 很小时,这不重要,但当 map 很大时,它就占主导地位。(访问缓存和内存之间的差异是一个数量级或两个数量级;参见例如 https://dev59.com/VW855IYBdhLWcg3w6IvV/。而且这种差异往往会随着 CPU 代数的增加而增加,因为相关的物理是局部的。)相比指针追踪,等于/小于操作是微不足道的。 - Nemolower_bound
搜索,而不是对 map 的at
搜索。 - Richard Hodges