sort_heap complexity guarantee

[François Dumont]

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
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 <***@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

[Daniel Krügler]

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

?

Thanks,

- Daniel

[François Dumont]

Post by Daniel Krügler

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

[Daniel Krügler]

Post by François Dumont

Post by Daniel Krügler
François, could you please submit a corresponding LWG issue by sending
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 ?

Looks fine to me - Thanks!

- Daniel

[Jonathan Wakely]

Post by François Dumont
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 ?

Yes please - thanks.