C++ скорость доступа карту

Question

Я определил следующую карту:

class xy_angle { 
public: 
    int x; 
    int y; 
    int angle; 

    xy_angle(int x, int y, int angle) :x(x), y(y), angle(angle){}; 

}; 

class xy_angleComparator { 
public: 
    bool operator() (const xy_angle &a, const xy_angle &b) const { 
     if (a.x != b.x) 
      return a.x < b.x; 
     else if (a.y != b.y) 
      return a.y < b.y; 
     else if (a.angle != b.angle) 
      return a.angle < b.angle; 
     else 
      return false; 
    } 
}; 

std::map<xy_angle, std::pair<int, int>, xy_angleComparator> transformed_coordinates_lut_; 

Я заполнить его, когда я инициализировать класс, который содержит его:

//creating LUTs 
int half_patch_size=48; 
for (int x_start = -half_patch_size; x_start <= half_patch_size; x_start++){ 
    for (int y_start = -half_patch_size; y_start <= half_patch_size; y_start++){ 
     for (int angle = -314; angle < 314; angle++){ 
      float angle_f = (float)angle/100.f; 
      double cos_theta = cos(angle_f); 
      double sin_theta = sin(angle_f); 

      int x_tranformed = (int)(((float)x_start)*cos_theta - ((float)y_start)*sin_theta); 
      int y_tranformed = (int)(((float)x_start)*sin_theta + ((float)y_start)*cos_theta); 

      if (x_tranformed > half_patch_size) 
       x_tranformed = half_patch_size; 

      if (x_tranformed < -half_patch_size) 
       x_tranformed = -half_patch_size; 

      if (y_tranformed > half_patch_size) 
       y_tranformed = half_patch_size; 

      if (y_tranformed < -half_patch_size) 
       y_tranformed = -half_patch_size; 

      transformed_coordinates_lut_[xy_angle(x_start, y_start, angle)] = std::pair<int, int>(x_tranformed, y_tranformed); 
     } 
    } 
} 

И я к нему доступ, используя следующий код:

int ax2 = transformed_coordinates_lut_[xy_angle(ax, ay, theta)].first; 
int ay2 = transformed_coordinates_lut_[xy_angle(ax, ay, theta)].second; 

Я измерил время доступа к карте, используя большой набор случайных ключей, и это совершенно безумно. Он полностью доминирует над временем работы функций, которые его используют.

Есть ли способ ускорить его?

Спасибо!

Gil.

Answer 1

Вместо этого вы можете использовать 3-мерный массив: f[x_start][y_start][angle]. Он будет занимать одно и то же (или меньше) пространство, потому что в любом случае у вас есть все возможные ключи. Конечно, вы также можете эмулировать трехмерный массив с плоским вектором, используя соответствующие индексы. Такой подход гарантирует постоянный поиск времени.

Answer 2

Независимо от того, какой контейнер использовать этот код плохо:

int ax2 = transformed_coordinates_lut_[xy_angle(ax, ay, theta)].first; 
int ay2 = transformed_coordinates_lut_[xy_angle(ax, ay, theta)].second; 

Вы делаете то же поиск в два раза! Определенно кешируйте результат:

auto& a2 = transformed_coordinates_lut_[xy_angle(ax, ay, theta)]; 
int ax2 = a2.first; 
int ay2 = a2.second; 

Теперь, насколько ускоряется работа. Наименьшее работа фронт будет просто качнуть из другого ассоциативного типа контейнера:

using MapType = std::unordered_map<xy_angle, 
            std::pair<int, int>, 
            xy_angle_hash>; // implement this hash 

Это даст вам O(1) поиск вместо того, O(lg N) вы сейчас видите в коде с std::map. Но если вы действительно хотите, чтобы тратить много времени, исследуя этот контейнер, я предлагаю просто окружив его, так что вы можете контролировать реализацию:

class TransformMap 
{ 
public: 
    std::pair<int, int>& operator()(const xy_angle&); 

private: 
    // is it std::map? 
    // or std::unordered_map? 
    // or 3D-array or vector or ... ? 
};