Intel® oneAPI Threading Building Blocks
Ask questions and share information about adding parallelism to your applications when using this threading library.

how to use list in parallel_sort

reeba
Beginner
417 Views
can anyone tell me how to sort a list using parallel_sort???
Thanks in advance
0 Kudos
4 Replies
robert-reed
Valued Contributor II
417 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.

0 Kudos
nagy
New Contributor I
417 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
0 Kudos
ARCH_R_Intel
Employee
417 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).

0 Kudos
reeba
Beginner
417 Views
thanks for all the replies :)
0 Kudos
Reply