Почему доступ к значениям карты с помощью at в C ++ такой медленный, когда значения ключей являются векторами std? - PullRequest
Новая
       59

Почему доступ к значениям карты с помощью at в C ++ такой медленный, когда значения ключей являются векторами std?

0 голосов
/ 23 января 2020

Я использую 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.

Ответы [ 4 ]

6 голосов
/ 23 января 2020

У вас есть другая проблема, например, попытка получить доступ к ключам, которых там нет, и увеличение размера карты, или она не зависла там, где вы думаете, или есть ошибка компилятора или что-то в этом роде. Этот автономный пример чтения из файла "x", содержащего 25000 4-х кортежей целых чисел, практически мгновенен на моем ноутбуке с 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);
}
1 голос
/ 23 января 2020

A std::map сортирует по ключам. Когда вы вставляете элемент, он должен сравнивать ключ нового элемента со многими другими ключами (логарифмический размер c). Поскольку ваши ключи имеют тип std::vector, представьте себе работу, необходимую для вставки элемента, или 24600!

Также доступ становится довольно дорогим. Сложность std::map::at() имеет логарифмический размер c, но опять же, вам нужно сравнить ключи, которые имеют тип 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::map с ключами типа std::array так же безобразен, как карта с ключами типа 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 */
}
1 голос
/ 23 января 2020

Вы можете использовать std::tuple<int, int, int> вместо std::vector<int> для своих ключей, поскольку первые намного дешевле создавать и копировать.

И std::unordered_map вместо std::map. Первый может дать вам O(1) сложность поиска (в зависимости от вашей функции ha sh), и он более дружественен к кэш-памяти процессора, чем std::map.

0 голосов
/ 23 января 2020

Почему это так медленно?

Поскольку здесь вы делаете гораздо больше, чем нужно: 

weights_table[xyz] = v;

map::operator[] ищет запись для данного ключа, вставляет ключ- пара значений, когда записи для данного ключа не существует, а затем возвращает ссылку на значение.

Если вы просто хотите вставить элемент в карту, вы должны использовать map::insert.

Тогда в вашем GetValue вы передаете векторы по значению. Это может занять некоторое время, когда векторы велики.

Также обязательно включите оптимизацию компилятора!

...