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_;

我在初始化包含它的class时填充它：

//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;

我使用大量随机密钥测量了地图的访问运行时间，这非常疯狂。它完全控制了使用它的函数的运行时间。

有什么办法可以加快速度吗？

谢谢！

吉尔。

Answer 1

您可以改用 3 维数组：f[x_start][y_start][angle]。它会占用相同（或更少）的 space 因为无论如何你都有所有可能的钥匙。当然，您也可以使用适当的索引模拟具有平面向量的 3-D 数组。这种方法可以保证您不断地进行查找。

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) 查找，而不是您当前在代码中使用 std::map 看到的 O(lg N)。但是如果你真的想花很多时间探索这个容器，我建议只是包装它以便你可以控制实现：

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 ... ?
};

C++加速地图访问

C++ speed up map access

c++

performance