(but is it necessary?)

Ie i want to do the opposite of this:
viewtopic.php?f=74&t=94839

the reason is that i want to use STL's nth_element function on
the content of VectorXd...

More precisely: i have a vector

const VectorXd d = VectorXd::Random(n)

and i want a vector

VectorXi d_prime

to contain the indexes of the m (1<m<<n) smallest
entry of d.





Best,

you can simply do that:

std::nth_element(d.data(), d.data()+n);

sorry, but i don't understand:


double hst(int& n, int& m){
VectorXd d = VectorXd::Random(n);
std::nth_element(d.data(),d.data()+n);
return d(m);
}



gives a bug:

error: no matching function for call to ‘nth_element(Eigen::PlainObjectBase<Eigen::Matrix<double, -0x00000000000000001, 1, 0, -0x00000000000000001, 1> >::Scalar*, Eigen::PlainObjectBase<Eigen::Matrix<double, -0x00000000000000001, 1, 0, -0x00000000000000001, 1> >::Scalar*)’

I've been too fast, I only wanted to show you you can use raw pointer as iterators, so in your case this should be:

std::nth_element(d.data(),d.data()+m, d.data()+n);

thank you very much sire,

so my code now is [simplifying a bit]:

float hst(VectorXf& d,int& m){
// VectorXf d = VectorXf::Random(n);
std::nth_element(d.data(),d.data()+m, d.data()+d.size());
return d(m);
}

then i:

A) do a copy of d named d_2;
B) feed d to hst();
C) compare all elements of d_2 to the return of hst() and
set aside the indexes of the ones that are smaller unto a
vector of int d_prim.

Now,

i) is this efficient (given that i won't need d/d_2 again latter)?
ii) is there a recommended way to do A) and C) (assuming they are necessary)?

Thanks in advance,

if m is not that small then the overhead of A) and C) should be totally negligible. An alternative would be to to use your own iterator storing references to both d and d_prim. d_prim would be initialized with 0 1 2 3 ... and then after call nth_element, d_prim.head(m) sill be the result you're looking for. This avoid A and C but add the initialization of d_prim and the nth_element step will be more costly because it will have to swap one float and one int every time instead of a single float. So overall I'm not sure at all that's worth the effort. Since I did something similar recently here is an exemple:

Code: Select all

template<typename Scalar, typename Index> struct ValIndexRef;

template<typename Scalar, typename Index>
struct ValIndex
{
  ValIndex(Scalar v, Index i)
    : m_value(v), m_index(i)
  {}
  ValIndex& operator=(const ValIndex& other)
  {
    m_value = other.m_value;
    m_index = other.m_index;
    return *this;
  }

  ValIndex(const ValIndexRef<Scalar,Index>& other)
    : m_value(other.m_value), m_index(other.m_index)
  { }

  bool operator<(const ValIndex& other) const { return m_index < other.m_index; }
  bool operator<(const ValIndexRef<Scalar,Index>& other) const { return m_index < other.m_index; }

  Scalar m_value;
  Index m_index;
};

template<typename Scalar, typename Index>
struct ValIndexRef
{
  ValIndexRef(Scalar& v, Index& i)
    : m_value(v), m_index(i)
  {}
  ValIndexRef& operator=(const ValIndexRef& other)
  {
    m_value = other.m_value;
    m_index = other.m_index;
    return *this;
  }

  ValIndexRef& operator=(const ValIndex<Scalar,Index>& other)
  {
    m_value = other.m_value;
    m_index = other.m_index;
    return *this;
  }

  bool operator<(const ValIndexRef& other) const { return m_index < other.m_index; }
  bool operator<(const ValIndex<Scalar,Index>& other) const { return m_index < other.m_index; }

  Scalar& m_value;
  Index&  m_index;
};

template<typename Scalar, typename Index>
class ValIndexIterator
{
public:
  typedef ValIndex<Scalar,Index> value_type;
  typedef std::ptrdiff_t difference_type;
  typedef ValIndexRef<Scalar,Index> reference;
  typedef ValIndexIterator pointer;
  typedef std::random_access_iterator_tag iterator_category;

  ValIndexIterator(Scalar* v, Index* i)
    : m_valuePtr(v), m_indexPtr(i)
  {}
  ValIndexIterator& operator++()
  {
    ++m_valuePtr;
    ++m_indexPtr;
    return *this;
  }
  ValIndexIterator& operator--()
  {
    --m_valuePtr;
    --m_indexPtr;
    return *this;
  }

  ValIndexIterator operator+(std::ptrdiff_t offset) const
  {
    return ValIndexIterator(m_valuePtr+offset, m_indexPtr+offset);
  }

  ValIndexIterator operator-(std::ptrdiff_t offset) const
  {
    return ValIndexIterator(m_valuePtr-offset, m_indexPtr-offset);
  }

  difference_type operator-(const ValIndexIterator& other) const
  {
    return  m_indexPtr-other.m_indexPtr;
  }

  reference operator*() { return reference(*m_valuePtr, *m_indexPtr); }

  bool operator<(const ValIndexIterator& other) const { return  m_indexPtr < other.m_indexPtr; }
  bool operator>(const ValIndexIterator& other) const { return  m_indexPtr > other.m_indexPtr; }
  bool operator!=(const ValIndexIterator& other) const { return  m_indexPtr != other.m_indexPtr; }
  bool operator==(const ValIndexIterator& other) const { return  m_indexPtr == other.m_indexPtr; }

protected:
  Scalar* m_valuePtr;
  Index* m_indexPtr;
};



std::nth_element(
    ValIndexIterator<double,int>(d.data(),   d_prim.data()),
    ValIndexIterator<double,int>(d.data()+m,   d_prim.data()+m),
     ValIndexIterator<double,int>(d.data()+n,   d_prim.data()+n),
);




Ok thanks a lot,

PS: it's really a beginner's problem i guess, but for future reference [?]
i place below the final version:

VectorXi hst(VectorXf& d,int& h){
VectorXf e = d;
VectorXi f(h);
int j=0;
std::nth_element(d.data(),d.data()+h,d.data()+d.size());
for(int i=0;i<d.size();i++){
if(e(i)<=d(h)){
f(j)=i;
j++;
}
if(j==h) break;
}
return f;
}