用C++-AMP减少未排序向量搜索的运行时间

Question

我编写了一个程序，通过一个未排序的结构向量进行大量搜索，以找到唯一元素的索引。在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;
}

Answer 1

您是否可以使用诸如boost：：multi数组之类的方法来保存未排序向量的排序唯一索引集？这样你就可以避免每次额外的工作。

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