Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   nth_element + sort versus partial_sort (http://www.velocityreviews.com/forums/t745258-nth_element-sort-versus-partial_sort.html)

Scott Meyers 03-17-2011 03:22 AM

nth_element + sort versus partial_sort
 
At http://wordaligned.org/articles/top-ten-percent , Thomas Guest shows
how he found that running nth_element followed by sort produced results
*much* faster than simply running partial_sort. I ran the test myself,
and I got the same kinds of results he did. I've mentioned this to
others, and some have been motivated to run the test themselves.
They've been as astonished as me at the results.

On the other hand, I ran across this at http://tinyurl.com/47qhrqy :

> I recently stumbled across partial_sort in stl; fwiw,
> std:partial_sort( A, A + sqrt(N), A + N ) is ~ 10 times faster than
> std:sort
> on my old mac ppc, even for N 100.
> Also fwiw, nth_element alone is ~ twice as slow as partial_sort --
> odd.


What are others' experiences with and comments about using nth_element
followed by sort instead of partial_sort to sort the top part of some
range of values? For purposes of discussion, assume that random access
iterators are available.

Thanks,

Scott

--
* C++ and Beyond: Meyers, Sutter, & Alexandrescu, Aug 7-10 in Banff
(http://cppandbeyond.com/)


All times are GMT. The time now is 05:54 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.