https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968
--- Comment #14 from Stephen Howe ---
(In reply to Anders Kaseorg from comment #13)
> (In reply to Patrick J. LoPresti from comment #12)
> > I am familiar with the usual algorithmic complexity definitions.
> >
> > So, just to be clear... Your as
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968
--- Comment #13 from Anders Kaseorg ---
(In reply to Patrick J. LoPresti from comment #12)
> I am familiar with the usual algorithmic complexity definitions.
>
> So, just to be clear... Your assertion is that the C++ standards committee
> adopte
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968
--- Comment #12 from Patrick J. LoPresti ---
(In reply to Anders Kaseorg from comment #11)
> (In reply to Patrick J. LoPresti from comment #10)
> > Complexity: Linear on average.
> >
> > It is not obvious (to me) what distribution the "on averag
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968
Anders Kaseorg changed:
What|Removed |Added
CC||andersk at mit dot edu
--- Comment #11
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968
Patrick J. LoPresti changed:
What|Removed |Added
CC||lopresti at gmail dot com
--- Comm
--- Comment #9 from paolo dot carlini at oracle dot com 2010-01-28 17:16
---
Roger told me in private that he doesn't mean to actively work on this issue
any time soon. Unassigning.
--
paolo dot carlini at oracle dot com changed:
What|Removed |Add
--- Comment #8 from paolo dot carlini at oracle dot com 2009-12-15 17:19
---
Roger, are you still actively working on this?
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968
--- Comment #7 from sjhowe at dial dot pipex dot com 2008-04-28 20:17
---
Roger
I agree with your analysis. I am slightly crestfallen as I was suspicious that
Barriato, Hofri etc's paper never mentioned "worst case" only "approximate
case". And I have now seen BFPRT73 paper where it m
--- Comment #6 from bkoz at gcc dot gnu dot org 2008-04-24 23:39 ---
Can I re-classify this as an enhancement?
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968
--- Comment #5 from roger at eyesopen dot com 2008-04-24 15:01 ---
Well, I've now had time to read the Barriato, Hofri et al. 2002 paper, and the
bad news is that such an approximate median selection algorithm can't be used
to guarantee an O(N) worst-case std::nth_element implementation.
--- Comment #4 from sjhowe at dial dot pipex dot com 2008-04-21 18:51
---
Yes. You want a partition that is O(1) that each time round eliminates N/2
elements (bearing in mind the post-condition for nth_element where iterators
greater than the kth iterator have elements that are >= the k
--- Comment #3 from pcarlini at suse dot de 2008-04-21 08:24 ---
Many thanks Roger for your further help on nth_element, excellent news.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968
--- 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 use
--- Comment #1 from pcarlini at suse dot de 2008-04-20 17:30 ---
Roger, can you have a look? Thanks in advance.
--
pcarlini at suse dot de changed:
What|Removed |Added
14 matches
Mail list logo
