Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Intel Community
- Software
- Software Development SDKs and Libraries
- Intel® oneAPI Threading Building Blocks
- Sort two arrays simultaneously using TBB sort

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

Pavanakumar_M_

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-19-2014
07:43 AM

205 Views

Sort two arrays simultaneously using TBB sort

Hi

The problem I am having is as follows,

1) I have arrays A and B of size N.

2) I have to sort A and also make B in the same sorted permutation as that of A.

This is how currently I have implemented in my code using TBB sort. But I find that the in-place re-ordering algorithm is a serial implementation and is a major bottleneck in my code. How can I do this more efficiently using only TBB sort and possibly avoid the use of permutation array ?

std::vector<unsigned> order(N);

std::vector<double> A(N), B(N);

for( unsigned i = 0; i < N; ++i ) order* = i;*

CompFunctor compare(A);

tbb::parallel_sort( order.begin(), order.end(), compare ); /// Runs in parallel

InPlacePermute( &A[0], &B[0], &order[0], N ); /// Runs in serial

/// Comparison functor definition

struct CompFunctor {

CompFunctor( std::vector<double> &a )

: _data(a) { }

inline bool operator()( uintT i, uintT j ) const {

return _data* < _data ;*

}

private:

std::vector<double> &_data;

}

/// Inplace permute

template < typename T1, typename T2 >

void InplacePermutation( T1 *data1, T2 *data2, unsigned *perm, size_t size ) {

T1 temp1;

T2 temp2;

unsigned j, k;

for( unsigned i = 0; i < size; ++i ) {

if( i != perm* ) {*

temp1 = data1*;*

temp2 = data2*;*

j = i;

while( i != perm

k = perm

data1

data2

perm

j = k;

}

data1

data2

perm

}

}

}

Link Copied

6 Replies

RafSchietekat

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-19-2014
08:16 AM

205 Views

Why don't you write a parallel algorithm to do the permutations to different vectors and then swap the results?

You might also be able to do some black magic with a special iterator type, so that both vectors are sorted at the end of calling tbb::sort, but that seems a bit far-fetched.

Pavanakumar_M_

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-19-2014
10:28 PM

205 Views

Alexey_K_Intel3

Employee

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-20-2014
12:20 AM

205 Views

There is no ready-to-use solution for this problem for tbb::parallel_sort. Actually, as far as I can tell after a bit of digging in the Web, there is no ready-to-use solution for this problem even for std::sort. And tbb::parallel_sort uses std::sort inside for sequential code, so you would need a special iterator that works with both.

Let me give you a couple of links that I have found with some ideas or hand-made prototypes that might be helpful:

http://stackoverflow.com/questions/13840998/sorting-zipped-locked-containers-in-c-using-boost-or-the...

http://www.stanford.edu/~dgleich/notebook/2006/03/sorting_two_arrays_simultaneou.html

My recommendation is to first develop (or borrow) something that works with std::sort, and then try to use it with tbb::parallel_sort.

RafSchietekat

Black Belt

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-20-2014
01:10 AM

205 Views

I latched on to "But I find that the in-place re-ordering algorithm is a serial implementation and is a major bottleneck in my code.", so I didn't know you would favour the other approach because of space restrictions. Luckily it has already been implemented, as Alexey has found.

If these arrays are so huge, I wonder if it wouldn't be cheaper to really zip them first, sort the zipped array, and then unzip it again. That does add O(n) storage and time, but maybe you'll more than gain that back in improved sorting performance because of the cache, i.e., because a fraction of O(n*log(n)) might still be larger than the O(n) above. Does that sound plausible at all?

Chris_M_5

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-20-2014
02:21 PM

205 Views

Maybe you can initiate a struct array that contains an element from each array, then sort that?

struct packed { int array_0; int array_1; } packed packed_data = malloc(N); // initialize packed_data with data sort(packed_data, [](&a, &b) { return a.array_0 > b.array_0; });

// now for each packed_data element, array_0 is in order, and array_1 is in order

Adrien_Guinet

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

03-20-2014
02:53 PM

205 Views

Just did that with std::sort (but it should work with tbb::parallel_sort). It involved a bit of work, but you can inspire yourself from this :

https://github.com/quarkslab/libleeloo/blob/properties/src/include/leeloo/sort_permute.h

The idea is to make a kind of "zip iterator" that would be compatible with the tbb::parallel_sort interface.

Here is an example of usage (adapted from https://github.com/quarkslab/libleeloo/blob/properties/src/include/leeloo/list_intervals_properties.... line 182) :

tbb::parallel_sort(make_sort_permute_iter(container1.begin(), container2.begin()), make_sort_permute_iter(container1.end(), container2.end()), sort_permute_iter_compare<container1_type::iterator, container2_type::iterator>())

Hope that will help !

Topic Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

For more complete information about compiler optimizations, see our Optimization Notice.