From: "François Dumont" <frs.dumont@gmail.com>
To: "Daniel Krügler" <daniel.kruegler@gmail.com>
Cc: "libstdc++@gcc.gnu.org" <libstdc++@gcc.gnu.org>,
gcc-patches <gcc-patches@gcc.gnu.org>
Subject: Re: sort_heap complexity guarantee
Date: Tue, 07 Oct 2014 21:11:00 -0000 [thread overview]
Message-ID: <54345705.1060108@gmail.com> (raw)
In-Reply-To: <CAGNvRgAGOAzjauDGxXOE6+NT2Hz0BY8XzvKih0-+GgCyw=SGpg@mail.gmail.com>
On 06/10/2014 23:05, Daniel Krügler wrote:
> 2014-10-06 23:00 GMT+02:00 François Dumont <frs.dumont@gmail.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
>>>> 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...
>>>
>> 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:
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#submit_issue
>
> ?
>
I just did requesting to use 2N log(N).
And is it ok to commit those ?
François
next prev parent reply other threads:[~2014-10-07 21:11 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <5431A354.2050404@gmail.com>
[not found] ` <alpine.DEB.2.11.1410052245150.5366@stedding.saclay.inria.fr>
2014-10-06 21:00 ` François Dumont
2014-10-06 21:05 ` Daniel Krügler
2014-10-07 21:11 ` François Dumont [this message]
2014-10-07 21:13 ` Daniel Krügler
2014-10-08 8:43 ` Jonathan Wakely
2014-10-18 8:03 ` Marc Glisse
[not found] ` <54456EEC.9000707@gmail.com>
[not found] ` <alpine.DEB.2.11.1410202237520.19590@stedding.saclay.inria.fr>
2014-10-22 21:13 ` François Dumont
2014-10-22 23:53 ` Jonathan Wakely
2014-10-23 0:18 ` Paolo Carlini
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=54345705.1060108@gmail.com \
--to=frs.dumont@gmail.com \
--cc=daniel.kruegler@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=libstdc++@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).