如果我想加载一个相对较大的〈string-key,int-value〉对文件,并使用std::map来存储数据。当我一个接一个地加载每个条目并将其插入到map中时,插入操作将花费O(log N)。我想通过对文件中的条目进行排序来改进这一点,以确保当我一个接一个地加载每个条目时,插入将只需要一次迭代。这可能通过在文件中提供正确的条目排序来实现。问题是,顺序是什么?假设与map排序的顺序相同是正确的吗?我使用标准的字符串比较方法,默认情况下是std::map。
esyap4oy1#
是的,如果您有一个按value_comp()顺序排列的对序列,则可以使用the 4th overload
value_comp()
template< class InputIt > map(InputIt first, InputIt last);
如果序列按value_comp()顺序排序,则需要使用线性时间。
ryevplcw2#
正如我在评论中所写:注意insert的重载有一个pos参数来提示元素应该去给予。如果文件中的数据是用end()迭代器排序的,那么就可以正常工作。在std::vector中预先排序很可能是没有意义的。不要做任何假设,编写基准测试并度量每一个可能的实现。要知道编写好的perforce测试是很棘手的,因为优化器可能会比你聪明。在处理性能时,第一条规则是首先测量,第二条规则是首先测量,第三条规则是......首先要做的是分析你的代码,目标是找出代码中的主要瓶颈,优化只运行10%的代码是浪费时间。在第二步中,你应该度量代码的修改是如何影响性能的。可能会有很多意外情况导致更坏的结果。因此,在您的情况下,基准测试可能看起来像这样,**调整这些测试,使它们更精确地匹配您的用例。**这非常重要,请参见下文。
pos
end()
std::vector
#include <sstream> #include <map> #include <iomanip> #include <algorithm> #include <random> constexpr size_t DataSizeStart = 8 << 10; constexpr size_t DataSizeStop = 8 << 10; using TestData = std::vector<std::pair<std::string, int>>; using TestDataConst = std::vector<std::pair<const std::string, int>>; std::string makeStringFor(size_t x) { std::ostringstream out; out << std::setfill('0') << std::setw(6) << x; return out.str(); } TestData sortedData(size_t n) { TestData r; r.reserve(n); size_t i = 0; std::generate_n(std::back_inserter(r), n, [&i]() { return std::pair{makeStringFor(++i), i}; }); return r; } TestData shuffledData(size_t n) { auto data = sortedData(n); std::random_device rd; std::mt19937 g(rd()); std::shuffle(data.begin(), data.end(), g); return data; } TestDataConst sortedConstData(size_t n) { auto r = sortedData(n); return {r.begin(), r.end()}; } TestDataConst shuffledConstData(size_t n) { auto r = shuffledData(n); return {r.begin(), r.end()}; } template<auto Data> static void CreateMapInsert(benchmark::State& state) { auto n = state.range(0); auto data = Data(n); for (auto _ : state) { benchmark::DoNotOptimize(data); std::map<std::string, int> m; for (auto& p : data) { m.insert(m.end(), p); } benchmark::DoNotOptimize(m); } } BENCHMARK(CreateMapInsert<sortedData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); BENCHMARK(CreateMapInsert<shuffledData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); BENCHMARK(CreateMapInsert<sortedConstData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); BENCHMARK(CreateMapInsert<shuffledConstData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); template<auto Data> static void CreateMapDirectly(benchmark::State& state) { auto n = state.range(0); auto data = Data(n); for (auto _ : state) { benchmark::DoNotOptimize(data); std::map<std::string, int> m{data.begin(), data.end()}; benchmark::DoNotOptimize(m); } } BENCHMARK(CreateMapDirectly<sortedData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); BENCHMARK(CreateMapDirectly<shuffledData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); BENCHMARK(CreateMapDirectly<sortedConstData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); BENCHMARK(CreateMapDirectly<shuffledConstData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); template<auto Data> static void FirstSortVectorThenCreateMapDirctly(benchmark::State& state) { auto n = state.range(0); auto data = Data(n); for (auto _ : state) { benchmark::DoNotOptimize(data); auto sorted = data; std::sort(sorted.begin(), sorted.end()); std::map<std::string, int> m{sorted.begin(), sorted.end()}; benchmark::DoNotOptimize(m); } } BENCHMARK(FirstSortVectorThenCreateMapDirctly<shuffledData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop); template<auto Data> static void FirstSortVectorThenMapIsert(benchmark::State& state) { auto n = state.range(0); auto data = Data(n); for (auto _ : state) { benchmark::DoNotOptimize(data); auto sorted = data; std::sort(sorted.begin(), sorted.end()); std::map<std::string, int> m; for (auto& p : sorted) { m.insert(m.end(), p); } benchmark::DoNotOptimize(m); } } BENCHMARK(FirstSortVectorThenMapIsert<shuffledData>)->RangeMultiplier(2)->Range(DataSizeStart, DataSizeStop);
结果表| 编译程序|比较不同的数据大小|样品8192|| - ------|- ------|- ------|| 海合会12.2|quick-bench|quick-bench|| 叮当声15 libstdc++|quick-bench|quick-bench|| 叮当声14 libc++|quick-bench|quick-bench|一般情况下,数据应按insert与pos相加,因为在所有情况下都会得到最佳结果(或接近最佳结果)。这也证明了先在std::vector中排序数据与其他慢方法相比给予明显的好处,在clang和libc++的情况下,这是最慢的解决方案。我也很惊讶直接从迭代器构造map到std::<std::string, in>的表现如此之差。正如Caleth在下面的评论中所捕捉到的那样,将const添加到std::pair<const std::string, int>可以节省时间。在这种情况下,构造函数成为最快的选择。这并不是说stdlibc++显然有一些性能缺陷,libc++在这种情况下速度更快,并且在一个对中缺少const时没有这种奇怪的行为。libc++在两个版本的对中都是最快的。
insert
std::<std::string, in>
Caleth
const
std::pair<const std::string, int>
stdlibc++
libc++
2条答案
按热度按时间esyap4oy1#
是的,如果您有一个按
value_comp()
顺序排列的对序列,则可以使用the 4th overload如果序列按
value_comp()
顺序排序,则需要使用线性时间。ryevplcw2#
正如我在评论中所写:
注意insert的重载有一个
pos
参数来提示元素应该去给予。如果文件中的数据是用end()
迭代器排序的,那么就可以正常工作。在std::vector
中预先排序很可能是没有意义的。不要做任何假设,编写基准测试并度量每一个可能的实现。要知道编写好的perforce测试是很棘手的,因为优化器可能会比你聪明。
在处理性能时,第一条规则是首先测量,第二条规则是首先测量,第三条规则是......
首先要做的是分析你的代码,目标是找出代码中的主要瓶颈,优化只运行10%的代码是浪费时间。
在第二步中,你应该度量代码的修改是如何影响性能的。可能会有很多意外情况导致更坏的结果。
因此,在您的情况下,基准测试可能看起来像这样,**调整这些测试,使它们更精确地匹配您的用例。**这非常重要,请参见下文。
结果表
| 编译程序|比较不同的数据大小|样品8192|
| - ------|- ------|- ------|
| 海合会12.2|quick-bench|quick-bench|
| 叮当声15 libstdc++|quick-bench|quick-bench|
| 叮当声14 libc++|quick-bench|quick-bench|
一般情况下,数据应按
insert
与pos
相加,因为在所有情况下都会得到最佳结果(或接近最佳结果)。这也证明了先在
std::vector
中排序数据与其他慢方法相比给予明显的好处,在clang和libc++的情况下,这是最慢的解决方案。我也很惊讶直接从迭代器构造map到
std::<std::string, in>
的表现如此之差。正如Caleth
在下面的评论中所捕捉到的那样,将const
添加到std::pair<const std::string, int>
可以节省时间。在这种情况下,构造函数成为最快的选择。这并不是说
stdlibc++
显然有一些性能缺陷,libc++
在这种情况下速度更快,并且在一个对中缺少const
时没有这种奇怪的行为。libc++
在两个版本的对中都是最快的。