sort_heap complexity guarantee

[François Dumont]

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!) ?

Ok to commit those new tests ?

2014-10-06  François Dumont  <fdumont@gcc.gnu.org>

     * testsuite/util/testsuite_counter_type.h
     (counter_type::operator<(const counter_type&)): Update
     less_compare_count when called.
     * testsuite/25_algorithms/make_heap/complexity.cc: New.
     * testsuite/25_algorithms/pop_heap/complexity.cc: New.
     * testsuite/25_algorithms/push_heap/complexity.cc: New.
     * testsuite/25_algorithms/sort_heap/complexity.cc: New.


Tested under Linux x86_64.

François
-------------- next part --------------
A non-text attachment was scrubbed...
Name: complexity.patch
Type: text/x-patch
Size: 7666 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20141006/5bfe45f6/attachment.bin>