This is the mail archive of the
mailing list for the libstdc++ project.
Re: sort_heap complexity guarantee
- From: François Dumont <frs dot dumont at gmail dot com>
- To: Daniel Krügler <daniel dot kruegler at gmail dot com>
- Cc: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Tue, 07 Oct 2014 23:11:33 +0200
- Subject: Re: sort_heap complexity guarantee
- Authentication-results: sourceware.org; auth=none
- References: <5431A354 dot 2050404 at gmail dot com> <alpine dot DEB dot 2 dot 11 dot 1410052245150 dot 5366 at stedding dot saclay dot inria dot fr> <543302DF dot 7080607 at gmail dot com> <CAGNvRgAGOAzjauDGxXOE6+NT2Hz0BY8XzvKih0-+GgCyw=SGpg at mail dot gmail dot com>
On 06/10/2014 23:05, Daniel Krügler wrote:
2014-10-06 23:00 GMT+02:00 François Dumont <email@example.com>:
On 05/10/2014 22:54, Marc Glisse wrote:
On Sun, 5 Oct 2014, François Dumont wrote:
I took a look at PR 61217 regarding pop_heap complexity guarantee.
Looks like we have no test to check complexity of our algos so I start
writing some starting with the heap operations. I found no issue with
make_heap, push_heap and pop_heap despite what the bug report is saying
however the attached testcase for sort_heap is failing.
Standard is saying std::sort_heap shall use less than N * log(N)
comparisons but with my test using 1000 random values the test is showing:
8687 comparisons on 6907.76 max allowed
Is this a known issue of sort_heap ? Do you confirm that the test is
I would first look for confirmation that the standard didn't just forget a
big-O or something. I would expect an implementation as n calls to pop_heap
to be legal, and if pop_heap makes 2*log(n) comparisons, that naively sums
to too much. And I don't expect the standard to contain an advanced
amortized analysis or anything like that...
Good point, with n calls to pop_heap it means that limit must be 2*log(1) +
2*log(2) +... + 2*log(n) which is 2*log(n!) and which is also necessarily <
2*n*log(n). I guess Standard comittee has forgotten the factor 2 in the
limit so this is what I am using as limit in the final test, unless someone
prefer the stricter 2*log(n!) ?
François, could you please submit a corresponding LWG issue by sending
an email using the recipe described here:
I just did requesting to use 2N log(N).
And is it ok to commit those ?