Hi,

i have the following Matlab statement I have to implement efficiently using Eigen:

Code: Select all

d = D(i,:);
[dummy, idx] = sort(d, 'ascend');
IDX(i, :) = idx(1:5);


Basically it takes a row from the matrix D and saves it in d. Then it sorts d, but I only need the indexes of the sorting. Then I save the first 5 sort indices in another matrix.

I have a solution but that is realy slow:

Code: Select all

VectorXf d = D.row(i);
VectorXi sort_ind;
sort_vector(d, sort_ind);
IDX.row(i) = sort_ind.head(5);


sort_vector implements insertion sort on both d and sort_ind.
I have to perform this operation a few thousand times, is there any
better solution to this problem?

To sort a Eigen vector, use STL algorithms. You need a pointer to the start of the vector's coeffs, use .data() to get it.

hm OK I have no idea if that gives you a good way to sort both the vector and the indices at the same time, to be efficient. Maybe you'll have to define your own element type consisting of a (float,int) pair, and use STL algorithm on that.

ok, I try to use now something similar to this:

Code: Select all

struct matrix_index {
    float data;
    int index;
};

struct by_matrix {
    bool operator()(matrix_index const &a, matrix_index const &b) {
        return a.data < b.data;
    }
};
vector<matrix_index> test;
sort(test.begin(),test.end(),by_matrix());


now my remaining question is how to efficiently fill the vector<matrix_index> and after sorting get the indices as VectorXi so that i can use .head(5).
The indices should start at 0 and go up to size().
Currently i use a for loop, but is there a more direct conversion to a std:vector? From the resulting sorted vector back to VectorXi seems not to be so much important as I am going to take only the first 5 elements anyway...

IsmaelNetzel wrote:Hi,

i have the following Matlab statement I have to implement efficiently using Eigen:

Code: Select all

d = D(i,:);
[dummy, idx] = sort(d, 'ascend');
IDX(i, :) = idx(1:5);


Basically it takes a row from the matrix D and saves it in d. Then it sorts d, but I only need the indexes of the sorting. Then I save the first 5 sort indices in another matrix.

I have a solution but that is realy slow:

Code: Select all

VectorXf d = D.row(i);
VectorXi sort_ind;
sort_vector(d, sort_ind);
IDX.row(i) = sort_ind.head(5);


sort_vector implements insertion sort on both d and sort_ind.
I have to perform this operation a few thousand times, is there any
better solution to this problem?

Here is what usually do. First you define your own compare functor using index

Code: Select all

template<typename Iter>
class IndexCompare {
private:
   Iter _iter;
public:
   IndexCompare(Iter iter):_iter(iter)
   {}
   
   bool operator()(size_t i, size_t j) const
   {
      return *(_iter+i) < *(_iter+j);
   }
};

template<typename Iter>
IndexCompare<Iter> index_compare(Iter iter) \\ a helper function
{
   return IndexCompare<Iter>(iter);
}


Then you define another index vector, then sort it as

Code: Select all

   vector<size_t> index(n); \\ index vector
   for (size_t i = 0; i < n; ++i) {
      index[i] = i;
   }

   vector<double> value(n); \\ vector your want to sort
        ... \\ fill value
   sort(index.begin(), index.end(), index_compare(&value[0]));


Sort vector of Eigen is similar, you just pass the pointer of the internal data to the compare functor.

It occured to me that since you only want the top 5 entries, you should just apply the trivial algorithm of looking for the first one, then for the second one, etc. You will be done in 5*n=O(n) operations, compare to the O(n*log(n)) operations needed by sort algorithms.

bjacob wrote:It occured to me that since you only want the top 5 entries, you should just apply the trivial algorithm of looking for the first one, then for the second one, etc. You will be done in 5*n=O(n) operations, compare to the O(n*log(n)) operations needed by sort algorithms.

That's right. Instead using std::sort, he can use the std::nth_element algorithm which can return top k elements without ordering in O(n) which is irrelevant to k.