This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: sort_heap complexity guarantee
- From: FranÃois Dumont <frs dot dumont at gmail dot com>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Mon, 06 Oct 2014 23:00:15 +0200
- Subject: Re: sort_heap complexity guarantee
- Authentication-results: sourceware.org; auth=none
- References: <5431A354 dot 2050404 at gmail dot com> <alpine dot DEB dot 2 dot 11 dot 1410052245150 dot 5366 at stedding dot saclay dot inria dot fr>
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
Index: testsuite/25_algorithms/make_heap/complexity.cc
===================================================================
--- testsuite/25_algorithms/make_heap/complexity.cc (revision 0)
+++ testsuite/25_algorithms/make_heap/complexity.cc (working copy)
@@ -0,0 +1,50 @@
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <random>
+#include <vector>
+#include <algorithm>
+
+#include <testsuite_counter_type.h>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using __gnu_test::counter_type;
+ const std::size_t nb_values = 1000;
+
+ std::random_device dev;
+ std::uniform_int_distribution<int> dist;
+ std::vector<counter_type> values;
+ values.reserve(nb_values);
+ for (std::size_t i = 0; i != nb_values; ++i)
+ values.push_back(dist(dev));
+
+ counter_type::reset();
+
+ std::make_heap(values.begin(), values.end());
+
+ VERIFY( counter_type::less_compare_count <= 3.0 * nb_values );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/25_algorithms/pop_heap/complexity.cc
===================================================================
--- testsuite/25_algorithms/pop_heap/complexity.cc (revision 0)
+++ testsuite/25_algorithms/pop_heap/complexity.cc (working copy)
@@ -0,0 +1,53 @@
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <cmath>
+#include <random>
+#include <vector>
+#include <algorithm>
+
+#include <testsuite_counter_type.h>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using __gnu_test::counter_type;
+ const std::size_t nb_values = 1000;
+
+ std::random_device dev;
+ std::uniform_int_distribution<int> dist;
+ std::vector<counter_type> values;
+ values.reserve(nb_values);
+ for (std::size_t i = 0; i != nb_values; ++i)
+ values.push_back(dist(dev));
+
+ std::make_heap(values.begin(), values.end());
+
+ counter_type::reset();
+
+ std::pop_heap(values.begin(), values.end());
+
+ VERIFY( counter_type::less_compare_count <= 2.0 * std::log(nb_values) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/25_algorithms/push_heap/complexity.cc
===================================================================
--- testsuite/25_algorithms/push_heap/complexity.cc (revision 0)
+++ testsuite/25_algorithms/push_heap/complexity.cc (working copy)
@@ -0,0 +1,54 @@
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <cmath>
+#include <random>
+#include <vector>
+#include <algorithm>
+
+#include <testsuite_counter_type.h>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using __gnu_test::counter_type;
+ const std::size_t nb_values = 1000;
+
+ std::random_device dev;
+ std::uniform_int_distribution<int> dist;
+ std::vector<counter_type> values;
+ values.reserve(nb_values);
+ for (std::size_t i = 0; i != nb_values; ++i)
+ values.push_back(dist(dev));
+
+ std::make_heap(values.begin(), values.end());
+ values.push_back(dist(dev));
+
+ counter_type::reset();
+
+ std::push_heap(values.begin(), values.end());
+
+ VERIFY( counter_type::less_compare_count <= std::log(values.size()) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/25_algorithms/sort_heap/complexity.cc
===================================================================
--- testsuite/25_algorithms/sort_heap/complexity.cc (revision 0)
+++ testsuite/25_algorithms/sort_heap/complexity.cc (working copy)
@@ -0,0 +1,53 @@
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <cmath>
+#include <random>
+#include <vector>
+#include <algorithm>
+
+#include <testsuite_counter_type.h>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using __gnu_test::counter_type;
+ const std::size_t nb_values = 1000;
+
+ std::random_device dev;
+ std::uniform_int_distribution<int> dist;
+ std::vector<counter_type> values;
+ values.reserve(nb_values);
+ for (std::size_t i = 0; i != nb_values; ++i)
+ values.push_back(dist(dev));
+
+ std::make_heap(values.begin(), values.end());
+
+ counter_type::reset();
+
+ std::sort_heap(values.begin(), values.end());
+
+ VERIFY( counter_type::less_compare_count <= 2.0 * nb_values * std::log(nb_values) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/util/testsuite_counter_type.h
===================================================================
--- testsuite/util/testsuite_counter_type.h (revision 215958)
+++ testsuite/util/testsuite_counter_type.h (working copy)
@@ -95,7 +95,10 @@
{ return val == rhs.val; }
bool operator<(const counter_type& rhs) const
- { return val < rhs.val; }
+ {
+ ++less_compare_count;
+ return val < rhs.val;
+ }
};
int counter_type::default_count = 0;