This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: sort_heap complexity guarantee
- From: Marc Glisse <marc dot glisse at inria dot fr>
- To: François Dumont <frs dot dumont at gmail dot com>
- Cc: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>
- Date: Sun, 5 Oct 2014 22:54:12 +0200 (CEST)
- Subject: Re: sort_heap complexity guarantee
- Authentication-results: sourceware.org; auth=none
- References: <5431A354 dot 2050404 at gmail dot com>
- Reply-to: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>
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
valid ?
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...
--
Marc Glisse