c++ std::map插入顺序和性能

mwecs4sa  于 2023-02-26  发布在  其他
关注(0)|答案(2)|浏览(215)

如果我想加载一个相对较大的〈string-key,int-value〉对文件,并使用std::map来存储数据。当我一个接一个地加载每个条目并将其插入到map中时,插入操作将花费O(log N)。我想通过对文件中的条目进行排序来改进这一点,以确保当我一个接一个地加载每个条目时,插入将只需要一次迭代。这可能通过在文件中提供正确的条目排序来实现。问题是,顺序是什么?假设与map排序的顺序相同是正确的吗?我使用标准的字符串比较方法,默认情况下是std::map。

esyap4oy

esyap4oy1#

是的,如果您有一个按value_comp()顺序排列的对序列,则可以使用the 4th overload

template< class InputIt >
map(InputIt first, InputIt last);

如果序列按value_comp()顺序排序,则需要使用线性时间。

ryevplcw

ryevplcw2#

正如我在评论中所写:
注意insert的重载有一个pos参数来提示元素应该去给予。如果文件中的数据是用end()迭代器排序的,那么就可以正常工作。在std::vector中预先排序很可能是没有意义的。
不要做任何假设,编写基准测试并度量每一个可能的实现。要知道编写好的perforce测试是很棘手的,因为优化器可能会比你聪明。
在处理性能时,第一条规则是首先测量,第二条规则是首先测量,第三条规则是......
首先要做的是分析你的代码,目标是找出代码中的主要瓶颈,优化只运行10%的代码是浪费时间。
在第二步中,你应该度量代码的修改是如何影响性能的。可能会有很多意外情况导致更坏的结果。
因此,在您的情况下,基准测试可能看起来像这样,**调整这些测试,使它们更精确地匹配您的用例。**这非常重要,请参见下文。

#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|
一般情况下,数据应按insertpos相加,因为在所有情况下都会得到最佳结果(或接近最佳结果)。
这也证明了先在std::vector中排序数据与其他慢方法相比给予明显的好处,在clang和libc++的情况下,这是最慢的解决方案。
我也很惊讶直接从迭代器构造map到std::<std::string, in>的表现如此之差。正如Caleth在下面的评论中所捕捉到的那样,将const添加到std::pair<const std::string, int>可以节省时间。在这种情况下,构造函数成为最快的选择。
这并不是说stdlibc++显然有一些性能缺陷,libc++在这种情况下速度更快,并且在一个对中缺少const时没有这种奇怪的行为。libc++在两个版本的对中都是最快的。

相关问题