how to parallel sort?

[nandor.sieben]

I have a vector of integers something like v=(2,1,5,4). I'd like to
create a vector containing the indices in order of the values of this
vector. So the output would be (1,0,3,2). Note that
v[0]<v[1]<v[3]<v[2]. What's the easiest/most efficient way to do
this?

Is there something like a parallel sort that takes two vectors as its
input, sorts the first one and makes the same changes two the second
vector. So if v=(2,1,5,4) and w=(0,1,2,3) then parallel_sort(v,w)
would change this into v=(1,2,4,5) and w=(1,0,3,2).

Of course I can do this on my own with loops but I think that would
not be very efficient. I cannot match the built in STL sort algorithm.
What I'd like to know if there is an effective way of doing this with
the STL algorithms.

 

[zhangyw80]

I have a vector of integers something like v=(2,1,5,4). I'd like to
create a vector containing the indices in order of the values of this
vector. So the output would be (1,0,3,2). Note that
v[0]<v[1]<v[3]<v[2]. What's the easiest/most efficient way to do
this?

Is there something like a parallel sort that takes two vectors as its
input, sorts the first one and makes the same changes two the second
vector. So if v=(2,1,5,4) and w=(0,1,2,3) then parallel_sort(v,w)
would change this into v=(1,2,4,5) and w=(1,0,3,2).

Of course I can do this on my own with loops but I think that would
not be very efficient. I cannot match the built in STL sort algorithm.
What I'd like to know if there is an effective way of doing this with
the STL algorithms.

here is a program i did using stl sort algorithm:
struct ps_node
{
int value;
int index;
};

//global overloading operator< used by sort(...) to compare two
elements
bool operator <(const ps_node& lhs, const ps_node& rhs)
{
return lhs.value < rhs.value;
}

int main(int argc, char* argv[])
{
int v[4] = {2,1,5,4};
int w[4];

vector<ps_node> vp;
for(int i=0; i<4; i++)
{
ps_node pn;
pn.value = v;
pn.index = i;
vp.push_back(pn);
}

//refer stl doc to get the detailed usage of sort
//template<class RanIt>
//void sort(RanIt first, RanIt last);

sort(vp.begin(), vp.end());

for(i=0; i<vp.size(); i++)
{
v = vp.value;
w = vp.index;

printf("%d %d ", v, w);
}

return 0;
}

 

[nandor.sieben]

This certainly works but it's a bit long. There must be an easier way.
Could this be done without the ps_node and the bool operator? Maybe
with a binder or with boost::lambda? Or with a priority queue?

 

[peter koch]

I have a vector of integers something like v=(2,1,5,4). I'd like to
create a vector containing the indices in order of the values of this
vector. So the output would be (1,0,3,2). Note that
v[0]<v[1]<v[3]<v[2]. What's the easiest/most efficient way to do
this?

Is there something like a parallel sort that takes two vectors as its
input, sorts the first one and makes the same changes two the second
vector. So if v=(2,1,5,4) and w=(0,1,2,3) then parallel_sort(v,w)
would change this into v=(1,2,4,5) and w=(1,0,3,2).

Of course I can do this on my own with loops but I think that would
not be very efficient. I cannot match the built in STL sort algorithm.
What I'd like to know if there is an effective way of doing this with
the STL algorithms.

You can easily use STL. Just create the resulting vector with indices
from 0 to n and sort it using as sort criteria the values of the other
vectors index. Give it some time to learn it, then come back if you
get stuck.

/Peter

 

[Barry]

I have a vector of integers something like v=(2,1,5,4). I'd like to
create a vector containing the indices in order of the values of this
vector. So the output would be (1,0,3,2). Note that
v[0]<v[1]<v[3]<v[2]. What's the easiest/most efficient way to do
this?

Is there something like a parallel sort that takes two vectors as its
input, sorts the first one and makes the same changes two the second
vector. So if v=(2,1,5,4) and w=(0,1,2,3) then parallel_sort(v,w)
would change this into v=(1,2,4,5) and w=(1,0,3,2).

Of course I can do this on my own with loops but I think that would
not be very efficient. I cannot match the built in STL sort algorithm.
What I'd like to know if there is an effective way of doing this with
the STL algorithms.

Have a look at boost::zip_iterator
@(http://www.boost.org/libs/iterator/doc/zip_iterator.html)

IIRC, VC8's vector::iterator implementation doesn't support
zip_iterator
to modify the value referred by zip_iterator (Proxy).

 

[nandor.sieben]

You can easily use STL. Just create the resulting vector with indices

from 0 to n and sort it using as sort criteria the values of the other
vectors index. Give it some time to learn it, then come back if you
get stuck.

/Peter

This sounds like what I'd like to do but I don't know where to start
on changing the sort criteria. Do I need to write a function object
that has the other vector as extra input? I have a feeling this is
just a one liner sort command but it's beyond my knowledge of STL.

 

[Kai-Uwe Bux]

This sounds like what I'd like to do but I don't know where to start
on changing the sort criteria. Do I need to write a function object
that has the other vector as extra input?
Yes.

I have a feeling this is
just a one liner sort command but it's beyond my knowledge of STL.

Consider:

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>

template < typename Sequence >
class ForwardCompare {

Sequence const & the_sequence;

public:

ForwardCompare ( Sequence const & ref )
: the_sequence ( ref )
{}

bool operator() ( typename Sequence::size_type lhs,
typename Sequence::size_type rhs ) const {
return ( the_sequence[lhs] < the_sequence[rhs] );
}

};

template < typename Sequence >
ForwardCompare< Sequence > make_ForwardCompare ( Sequence const & seq ) {
return ( ForwardCompare< Sequence >( seq ) );
}

int main ( void ) {
std::vector< int > value;
value.push_back( 2 );
value.push_back( 1 );
value.push_back( 5 );
value.push_back( 4 );
std::vector< int > index;
for ( int i = 0; i < value.size(); ++i ) {
index.push_back( i );
}
std::sort( index.begin(), index.end(), make_ForwardCompare( value ) );
std::copy( index.begin(), index.end(),
std:stream_iterator< int >( std::cout, " " ) );
std::cout << '\n';
}


It would be a one-liner, if lambda allowed for:

std::sort( index.begin(), index.end(), value[_1] < value[_2] );

However, I think that does not work (and as long as the subscript operator
is required to be a member function, I don't see a way to implement lambda
so that it would work).


Best

Kai-Uwe Bux

 

[nandor.sieben]

It would be a one-liner, if lambda allowed for:

  std::sort( index.begin(), index.end(), value[_1] < value[_2] );

However, I think that does not work (and as long as the subscript operator
is required to be a member function, I don't see a way to implement lambda
so that it would work).

Thanks, this almost works. I figured it out. Here is the solution:

sort(index.begin(), index.end(), var(value)[_1] < var(value)[_2]);

 

[Jeff Schwab]

It would be a one-liner, if lambda allowed for:

std::sort( index.begin(), index.end(), value[_1] < value[_2] );

However, I think that does not work (and as long as the subscript operator
is required to be a member function, I don't see a way to implement lambda
so that it would work).

Thanks, this almost works. I figured it out. Here is the solution:

sort(index.begin(), index.end(), var(value)[_1] < var(value)[_2]);

I'm not sure what you mean by var(), but would love to know how your
solution works. Could you please post a compilable example?

 

[Anders Dalvander]

I'm not sure what you mean by var(), but would love to know how your
solution works. Could you please post a compilable example?

var is boost::lambda::var. See
http://www.boost.org/doc/html/lambda/le_in_details.html#lambda.delaying_constants_and_variables
for description of boost::lambda::var.

Regards,
Anders

 

[Jeff Schwab]

var is boost::lambda::var. See
http://www.boost.org/doc/html/lambda/le_in_details.html#lambda.delaying_constants_and_variables
for description of boost::lambda::var.

Thanks. Interestingly, that works when the original values are held in
vectors or in raw arrays, but GCC 4.2 chokes if the values are in a tr1
array, on the grounds that there is no match for operator<. I wonder
whether this is a limitation of GCC, Boost, or yours truly. (FWIW, the
error message contains a spectacular amount of information, only about
half of which do I currently understand.)

#include <algorithm>
#include <cstdlib>
#include <vector>

#include <tr1/array>

#include <boost/lambda/lambda.hpp>
#include <boost/iterator/counting_iterator.hpp>

int main() {

using std::sort;

using boost::lambda::_1;
using boost::lambda::_2;
using boost::lambda::var;

std::size_t const z = 4;

typedef int value_type;
typedef value_type raw_array[z];
typedef std::tr1::array<value_type, z> array;
typedef array::size_type index;
typedef boost::counting_iterator<index> index_iter;

/* Tr1 array, raw array, and std::vector with equivalent values. */
array a = {{ 2, 1, 5, 4 }};
raw_array ra = { a[0], a[1], a[2], a[3] };
std::vector<value_type> v(a.begin(), a.end());

/* Indexes to be sorted according to corresponding values. */
std::vector<index> iv(index_iter(0), index_iter(a.size()));

/* OK */
sort(iv.begin(), iv.end(), var(ra)[_1] < var(ra)[_2]);
sort(iv.begin(), iv.end(), var(v)[_1] < var(v)[_2]);

/* error: No match for operator<. */
// sort(iv.begin(), iv.end(), var(a)[_1] < var(a)[_2]);
}