From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 20079 invoked by alias); 6 Oct 2014 21:05:09 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 20062 invoked by uid 89); 6 Oct 2014 21:05:09 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.8 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail-wg0-f50.google.com Received: from mail-wg0-f50.google.com (HELO mail-wg0-f50.google.com) (74.125.82.50) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Mon, 06 Oct 2014 21:05:07 +0000 Received: by mail-wg0-f50.google.com with SMTP id a1so7761339wgh.9 for ; Mon, 06 Oct 2014 14:05:03 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.194.21.101 with SMTP id u5mr7063208wje.113.1412629503877; Mon, 06 Oct 2014 14:05:03 -0700 (PDT) Received: by 10.216.187.4 with HTTP; Mon, 6 Oct 2014 14:05:03 -0700 (PDT) In-Reply-To: <543302DF.7080607@gmail.com> References: <5431A354.2050404@gmail.com> <543302DF.7080607@gmail.com> Date: Mon, 06 Oct 2014 21:05:00 -0000 Message-ID: Subject: Re: sort_heap complexity guarantee From: =?ISO-8859-1?Q?Daniel_Kr=FCgler?= To: =?ISO-8859-1?Q?Fran=E7ois_Dumont?= Cc: "libstdc++@gcc.gnu.org" , gcc-patches Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-SW-Source: 2014-10/txt/msg00499.txt.bz2 2014-10-06 23:00 GMT+02:00 Fran=E7ois Dumont : > On 05/10/2014 22:54, Marc Glisse wrote: >> >> On Sun, 5 Oct 2014, Fran=E7ois 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 showi= ng: >>> >>> 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_h= eap >> to be legal, and if pop_heap makes 2*log(n) comparisons, that naively su= ms >> 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 necessaril= y < > 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 someo= ne > prefer the stricter 2*log(n!) ? Fran=E7ois, 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 ? Thanks, - Daniel