1

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

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

以防万一：这是我使用的向量和搜索功能：

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;
}
4

1 回答 1

2

你可以使用类似 boost::multi-index 数组的东西来为你的未排序向量保存一组排序的唯一索引吗？这样你就可以避免每次的额外工作。

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

于 2013-08-18T21:44:50.313 回答