------- Comment #2 from roger at eyesopen dot com 2008-04-21 03:22 -------
Yep, now that we're back in stage1, it's about time I got around to submitting
the O(n) worst case nth_element implementation that I mentioned last year. For
Steven's benefit, the implementation I've already coded up uses the
median-of-medians in groups of five strategy as a fallback to a modified
quickselect.
[Though I'll need to quickly read the paper you cite]
The trick for libstdc++ is to attempt to make the typical case as fast or
faster than the existing implementation. Whilst the standards now require
O(n) worst case, the perceived performance of g++'s users is the average
case and changing to an O(n) implementation that has a large co-efficient
constant may upset some folks.
--
roger at eyesopen dot com changed:
What |Removed |Added
----------------------------------------------------------------------------
AssignedTo|unassigned at gcc dot gnu |roger at eyesopen dot com
|dot org |
Status|UNCONFIRMED |ASSIGNED
Ever Confirmed|0 |1
Last reconfirmed|0000-00-00 00:00:00 |2008-04-21 03:22:22
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968
