Community
cancel
Showing results for 
Search instead for 
Did you mean: 
reeba
Beginner
67 Views

how to use list in parallel_sort

can anyone tell me how to sort a list using parallel_sort???
Thanks in advance
0 Kudos
4 Replies
robert-reed
Valued Contributor II
67 Views

The simple answer is: you can't get there from here.

The documentation for parallel_sort makes it clear: it has the same requirements for the sequences it sorts as std::sort, namely, the iterator by which you access the sequence must be at least a random access iterator, which is not usuallytrue of iterators attachable to lists. In particular, the algorithm underlying both std::sort and tbb::parallel_sort is based on Hoare's Quicksort algorithm, which needs to be able to partition subsequences and exchange elements of the sequence.

nagy
New Contributor I
67 Views

From the reference document.
The requirementson the iterator and sequence are the same as for std::sort. Specifically,
RandomAccessIterator must be a random access iterator, ...
Which I believebasicallymeans that the container must have a random access iterator, which is not the case for std::list. The only solution I can think of is to copy the entire list into an std::vector, sort it and then copy it back, which could be very inefficient. I think your better of either using std::vector from the beginning or using the std::list::sort function.
EDIT: Updated accordingly to the next post
ARCH_R_Intel
Employee
67 Views

Even for sequential code, it might actually be faster to copy to a std::vector, apply std::sort, and copy back to the list. Vectors are much friendly to caches than lists, and a cache miss is on the order of at least a hundred clock cycles. I tried a quick experiment with list of length 100,0000 and 1,000,000 on Linux with gcc 4.3.2. The sequence, where the input x is a std::list:
    {
        vector tmp( x.begin(), x.end() );
        sort(tmp.begin(),tmp.end());
        x.assign(tmp.begin(),tmp.end());
    }

was about twices as fast as x.sort().

Of course if the list is short or there is a large overhead for copying list items, then the results will not be as good. But perhapssorting avector of pointers to the items might work well (I did not try this).

reeba
Beginner
67 Views

thanks for all the replies :)
Reply