当键值是标准向量时，为什么在 C++ 中使用 at 访问映射值这么慢？

Question

我使用 std::map 定义为 std::map<std::vector<int>, double>，您会看到键值是整数向量。我的地图中的成员数量是 24600。这是最小工作示例：

InOutLetFileVelocityWeights.h:

#include <iostream>
#include <string>
#include <vector>
#include <map>

class InOutLetFileVelocityWeights
{
        public:
          InOutLetFileVelocityWeights();

          const std::string& GetWeightsFilePath()
          {
            return velocityWeightsFilePath;
          }
          void SetWeightsFilePath(const std::string& path)
          {
            velocityWeightsFilePath = path;
          }

          double GetValue(std::vector<int>& xyz);

          void Initialise();

        private:
          std::string velocityWeightsFilePath;

          std::map<std::vector<int>, double> weights_table;
};

InOutLetFileVelocityWeights.cc:

#include "InOutLetFileVelocityWeights.h"
#include <algorithm>
#include <fstream>
#include <cmath>

InOutLetFileVelocityWeights::InOutLetFileVelocityWeights()
{
}

double InOutLetFileVelocityWeights::GetValue(std::vector<int>& xyz)
{

      double value;

      value = weights_table.at(xyz);

      return value;

}

void InOutLetFileVelocityWeights::Initialise()
{
/* Load and read file. */
const std::string in_name = velocityWeightsFilePath;

std::fstream myfile;
myfile.open(in_name.c_str(), std::ios_base::in);

std::string input_line;
/* input files are in ASCII, in format:
 *  *
 *   * coord_x coord_y coord_z weights_value
 *    *
 *     * */
while (myfile.good())
{
            double x, y, z;
            double v;
            myfile >> x >> y >> z >> v;

            std::vector<int> xyz;
            xyz.push_back(x);
            xyz.push_back(y);
            xyz.push_back(z);

            weights_table[xyz] = v;

        //std::cout << x << y << z << v << std::endl;
}
myfile.close();
}

main.cc:

#include "InOutLetFileVelocityWeights.h"

int main(int argc, char *argv[])
{

const std::string in_name = "Flow-Weights.txt";

std::vector<int> xyz;

xyz.push_back(760);
xyz.push_back(189);
xyz.push_back(368);

InOutLetFileVelocityWeights* Iolet = new InOutLetFileVelocityWeights();

Iolet->SetWeightsFilePath(in_name);

Iolet->Initialise();

double value = Iolet->GetValue(xyz);

std::cout << value << std::endl;

return 0;

}

知道为什么从 GetValue 函数中获取值需要这么长时间吗？输入文件在这里：https://drive.google.com/file/d/1Bvv4JfdjJjCo-GKnduBdqabDJHo3UxbV/view?usp=sharing .

Answer 1

为什么这么慢？

因为你在这里做的比你需要的多得多:

weights_table[xyz] = v;

map::operator[] 搜索给定键的条目，当不存在给定键的条目时插入一个键值对，然后 returns 您对该值的引用。

如果您只想在地图中插入一个元素，您应该使用 map::insert。

然后在您的 GetValue 中您按值传递向量。当向量很大时，这可能需要一段时间。

还要确保启用编译器优化！

Answer 2

您还有一些其他问题，例如尝试访问不存在的键并扩大地图的大小，或者它没有挂在您认为的位置，或者存在编译器错误或类似问题。这个从包含 25000 个 4 元组整数的文件 "x" 读取的独立示例在我的笔记本电脑上使用 g++ 并且没有优化基本上是即时的。

#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <fstream>

std::map<std::vector<int>, double> weights_table;
std::vector<std::vector<int> > allkeys;

void
loadit(char const *name)
{
  /* Load and read file. */
  std::fstream myfile;
  myfile.open(name, std::ios_base::in);

  std::string input_line;
  /* input files are in ASCII, in format:
   *
   * coord_x coord_y coord_z weights_value
   *
   * */
  while (myfile.good())
    {
      int x, y, z;
      double v;
      myfile >> x >> y >> z >> v;

      std::vector<int> xyz;
      xyz.push_back(x);
      xyz.push_back(y);
      xyz.push_back(z);
      allkeys.push_back(xyz);

      weights_table[xyz] = v;
    }
  myfile.close();
}

double GetValue(std::vector<int> xyz)
{
      double value;

      value = weights_table.at(xyz);

      return value;
}

int
main()
{
  loadit("x");
  double res=0;
  for (size_t i=0; i < allkeys.size(); ++i)
    res+=GetValue(allkeys[i]);
  std::cout << res << std::endl;
  return (0);
}

Answer 3

您可能希望使用 std::tuple<int, int, int> 而不是 std::vector<int> 作为密钥，因为前者的创建和复制成本要低得多。

和 std::unordered_map 而不是 std::map。前者可以为您提供接近 O(1) 的查找复杂度（取决于您的哈希函数），并且比 std::map.

更 CPU 缓存友好

Answer 4

A std::map 按键排序。当您插入一个元素时，它必须将新元素的键与许多其他键（大小的对数）进行比较。由于您的键是 std::vector 类型，想象一下插入一个元素所需的工作，或 24600!

访问也变得非常昂贵。 std::map::at() 的复杂度在大小上是对数的，但是同样，您需要比较 std::vector 类型的键（我不确定 std::vector 类型的键是如何排序的，但是它猜测这是线性大小）。

此外，每次创建 std::vector 时，您都在动态分配，这非常昂贵（您可以只使用 std::array 来完成这项工作）。您甚至可以在调用 GetValue(std::vector<int> xyz) 时创建一个副本（参数 xyz 应该作为 const 引用传递。

作为替代方案，您可以将变量 x、y 和 z 存储在 std::array<int, 3> 中并使用 std::map<std::array<int,3>, double>。这将解决您的时间问题。

无论如何，具有 std::array 类型键的 std::map 与具有 std::vector 类型键的映射一样丑陋。你不应该使用那种地图。

我不知道您的程序的确切目标是什么，但请考虑以下事项。当你试图让你的 double 给出一个 triplet 时，你是如何决定你需要哪个三元组的？我想你需要为每个三胞胎或一些随机三胞胎做这个。在这两种情况下，您实际上都不需要 std::map。您可以将三元组和值都存储在 std::vector:

中

// size
const size_t N = 24600;

// reserve space for vector of triplets (x, y, z) and vector of doubles (v)
std::vector<std::array<int, 3>> vec_triplets;
std::vector<double vec_values;
vec_triplets.reserve(N);
vec_values.reserve(N);

// for each triplet and double, store it in the vector
for ( ... )
{
    vec_triplets.emplace_back(std::array<int, 3>{x, y, z});
    vec_values.emplace_back(v);
}

// now I need to compute something using a triplet and the associated double
for (size_t idx = 0; idx < N; ++idx)
{
    const auto& triplet = vec_triplets[idx];
    const associated_double = vec_values[idx];
    /* do whatever you need */
}

当键值是标准向量时，为什么在 C++ 中使用 at 访问映射值这么慢？

Why accessing map values by using at in C++ is so slow when key values are std vectors?

c++

containers

stl

std

c++11