0

There are a couple of other posts about sorting a vector A based on values in another vector B. Most of the other answers tell to create a struct or a class to combine the values into one object and use std::sort.

Though I'm curious about the performance of such solutions as I need to optimize code which implements bubble sort to sort these two vectors. I'm thinking to use a vector<pair<int,int>> and sort that.

I'm working on a blob-tracking application (image analysis) where I try to match previously tracked blobs against newly detected blobs in video frames where I check each of the frames against a couple of previously tracked frames and of course the blobs I found in previous frames. I'm doing this at 60 times per second (speed of my webcam).

Any advice on optimizing this is appreciated. The code I'm trying to optimize can be shown here:

http://code.google.com/p/projectknave/source/browse/trunk/knaveAddons/ofxBlobTracker/ofCvBlobTracker.cpp?spec=svn313&r=313

important: I forgot to mention that the size of the vectors will never be bigger than 5, and mostly have only 3 items in it and will be unsorted (maybe I could even hardcode it for 3 items?)

Thanks

4

2 回答 2

3

C++ 提供了许多排序选项，从std::sort算法到排序容器，如std::map和std::set. 您应该始终尝试使用这些作为您的第一个解决方案，并且只尝试“优化冒泡排序”之类的东西作为最后的手段。

于 2010-06-02T22:20:11.063 回答
1

我前一段时间实现了这一点。另外，我认为您的意思是按照与 A 的排序值相同的方式对向量 B 进行排序。

Index包含 的排序顺序data。

/** Sorts a vector and returns index of the sorted values
 * \param Index Contains the index of sorted values in the original vector
 * \param data The vector to be sorted
 */
template<class T>
void paired_sort(vector<unsigned int> & Index, const vector<T> & data)
{
    // A vector of a pair which will contain the sorted value and its index in the original array
    vector<pair<T,unsigned int>> IndexedPair;
    IndexedPair.resize(data.size());
    for(unsigned int i=0;i<IndexedPair.size();++i)
    {
        IndexedPair[i].first = data[i];
        IndexedPair[i].second = i;
    }
    sort(IndexedPair.begin(),IndexedPair.end());
    Index.resize(data.size());
    for(size_t i = 0; i < Index.size(); ++i) Index[i] = IndexedPair[i].second;
}
于 2010-06-02T22:20:59.223 回答