c++ - 使用 C++-AMP 减少未排序 vector 搜索的运行时间

Question

我编写了一个程序，它通过未排序的结构 vector 进行大量搜索以查找唯一元素的索引。这种搜索在 for 循环中的每次迭代中进行多次，并且在 for 循环迭代期间 vector 内的数据也会更改多次(仅添加数据，不删除任何内容)。现在这个程序做了我想要它做的，但是它相当慢，所以在我让 VS2012 分析我的程序的性能之后我发现程序 80% 以上的时间都在搜索未排序的 vector ，所以我自然而然地想要优化搜索。我知道我能得到的最好的是 O(n)，因为它是一个未排序的 vector (每个元素都是唯一的，元素的顺序一旦插入就不能改变)，但我希望以某种方式减少运行时间。

我一直在考虑使用并行处理来减少程序运行时间，Microsoft 的 AMP 库看起来很有前途。从它的外观来看，您可以使用并行处理来遍历数组以查找数组中的元素。但是未排序的 vector 中的数据变化很大，所以这不会将瓶颈从迭代 vector 转移到从 CPU 到 GPU 的数据传输，或者有 AMP 内置优化来解决这个问题吗？请记住: vector 中的数据仅添加到 vector 的末尾，不会删除任何内容。

以防万一:这是我使用的 vector 和搜索函数:

struct VertexData
{
    VertexData( unsigned int pos, unsigned int norm, unsigned int tex )
        : posIdx(pos), normIdx(norm), texIdx(tex) {}

    unsigned int posIdx;
    unsigned int normIdx;
    unsigned int texIdx;

    inline bool operator<( const VertexData &rhs ) const
    {
        return std::tie(posIdx, normIdx, texIdx) < std::tie(rhs.posIdx, rhs.normIdx, rhs.texIdx);
    }

    inline bool operator==( const VertexData &rhs ) const
    {
        return std::tie(posIdx, normIdx, texIdx) == std::tie(rhs.posIdx, rhs.normIdx, rhs.texIdx);
    }
};

std::vector<VertexData> verts;

int findIndex( const std::vector<VertexData> &vec, const VertexData &val ) const
{
    std::vector<VertexData>::const_iterator it;
    int idx = 0;
    for ( it = vec.begin(); it != vec.end(); ++it, ++idx )
        if ( *it == val )
            return idx;

    return -1;
}

Answer 1

您能否使用诸如 boost::multi-index 数组之类的东西来为未排序的 vector 保存一组已排序的唯一索引？这样你每次都可以避免额外的工作。

通常，算法修复总是比蛮力更好。