* Re: sort_heap complexity guarantee
[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
` (2 more replies)
0 siblings, 3 replies; 9+ messages in thread
From: François Dumont @ 2014-10-06 21:00 UTC (permalink / raw)
To: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1954 bytes --]
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
[-- Attachment #2: complexity.patch --]
[-- Type: text/x-patch, Size: 7666 bytes --]
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;
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: sort_heap complexity guarantee
2014-10-06 21:00 ` sort_heap complexity guarantee François Dumont
@ 2014-10-06 21:05 ` Daniel Krügler
2014-10-07 21:11 ` François Dumont
2014-10-08 8:43 ` Jonathan Wakely
2014-10-18 8:03 ` Marc Glisse
2 siblings, 1 reply; 9+ messages in thread
From: Daniel Krügler @ 2014-10-06 21:05 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
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
?
Thanks,
- Daniel
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: sort_heap complexity guarantee
2014-10-06 21:05 ` Daniel Krügler
@ 2014-10-07 21:11 ` François Dumont
2014-10-07 21:13 ` Daniel Krügler
0 siblings, 1 reply; 9+ messages in thread
From: François Dumont @ 2014-10-07 21:11 UTC (permalink / raw)
To: Daniel Krügler; +Cc: libstdc++, gcc-patches
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
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: sort_heap complexity guarantee
2014-10-07 21:11 ` François Dumont
@ 2014-10-07 21:13 ` Daniel Krügler
0 siblings, 0 replies; 9+ messages in thread
From: Daniel Krügler @ 2014-10-07 21:13 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
2014-10-07 23:11 GMT+02:00 François Dumont <frs.dumont@gmail.com>:
> On 06/10/2014 23:05, Daniel Krügler wrote:
>> 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 ?
Looks fine to me - Thanks!
- Daniel
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: sort_heap complexity guarantee
2014-10-06 21:00 ` sort_heap complexity guarantee François Dumont
2014-10-06 21:05 ` Daniel Krügler
@ 2014-10-08 8:43 ` Jonathan Wakely
2014-10-18 8:03 ` Marc Glisse
2 siblings, 0 replies; 9+ messages in thread
From: Jonathan Wakely @ 2014-10-08 8:43 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 06/10/14 23:00 +0200, François Dumont wrote:
>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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: sort_heap complexity guarantee
2014-10-06 21:00 ` sort_heap complexity guarantee François Dumont
2014-10-06 21:05 ` Daniel Krügler
2014-10-08 8:43 ` Jonathan Wakely
@ 2014-10-18 8:03 ` Marc Glisse
[not found] ` <54456EEC.9000707@gmail.com>
2 siblings, 1 reply; 9+ messages in thread
From: Marc Glisse @ 2014-10-18 8:03 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On Mon, 6 Oct 2014, François Dumont wrote:
> * testsuite/25_algorithms/push_heap/complexity.cc: New.
This test is randomly failing in about 1% to 2% of cases.
--
Marc Glisse
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: sort_heap complexity guarantee
[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
0 siblings, 2 replies; 9+ messages in thread
From: François Dumont @ 2014-10-22 21:13 UTC (permalink / raw)
To: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1135 bytes --]
Then I think we need this patch which also fix other issues.
2014-10-22 François Dumont <fdumont@gcc.gnu.org>
* testsuite/25_algorithms/make_heap/complexity.cc: Add missing test
variable.
* testsuite/25_algorithms/sort_heap/complexity.cc: Likewise and use
log2.
* testsuite/25_algorithms/pop_heap/complexity.cc: Likewise and require
normal mode.
* testsuite/25_algorithms/push_heap/complexity.cc: Likewise.
Tested under Linux x86_64.
Ok to commit ?
François
On 20/10/2014 22:48, Marc Glisse wrote:
> On Mon, 20 Oct 2014, François Dumont wrote:
>
>> On 18/10/2014 09:24, Marc Glisse wrote:
>>> On Mon, 6 Oct 2014, François Dumont wrote:
>>>
>>>> * testsuite/25_algorithms/push_heap/complexity.cc: New.
>>>
>>> This test is randomly failing in about 1% to 2% of cases.
>>>
>> Is it for a particular platform ? I just run it thousands of times on
>> my Linux and never experimented any failure.
>
> x86_64-linux-gnu, debian testing
>
> Here is a deterministic version.
>
> By the way, when the standard says "log" and there isn't an implicit
> O(), it usually means "log2".
>
[-- Attachment #2: complexity.patch --]
[-- Type: text/x-patch, Size: 2827 bytes --]
Index: testsuite/25_algorithms/make_heap/complexity.cc
===================================================================
--- testsuite/25_algorithms/make_heap/complexity.cc (revision 216348)
+++ testsuite/25_algorithms/make_heap/complexity.cc (working copy)
@@ -26,6 +26,8 @@
void test01()
{
+ bool test __attribute__((unused)) = true;
+
using __gnu_test::counter_type;
const std::size_t nb_values = 1000;
Index: testsuite/25_algorithms/pop_heap/complexity.cc
===================================================================
--- testsuite/25_algorithms/pop_heap/complexity.cc (revision 216348)
+++ testsuite/25_algorithms/pop_heap/complexity.cc (working copy)
@@ -15,6 +15,7 @@
// with this library; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
+// { dg-require-normal-mode "" }
// { dg-options "-std=gnu++11" }
#include <cmath>
@@ -27,6 +28,8 @@
void test01()
{
+ bool test __attribute__((unused)) = true;
+
using __gnu_test::counter_type;
const std::size_t nb_values = 1000;
@@ -43,7 +46,7 @@
std::pop_heap(values.begin(), values.end());
- VERIFY( counter_type::less_compare_count <= 2.0 * std::log(nb_values) );
+ VERIFY( counter_type::less_compare_count <= 2.0 * std::log2(nb_values) );
}
int main()
Index: testsuite/25_algorithms/push_heap/complexity.cc
===================================================================
--- testsuite/25_algorithms/push_heap/complexity.cc (revision 216348)
+++ testsuite/25_algorithms/push_heap/complexity.cc (working copy)
@@ -15,6 +15,7 @@
// with this library; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
+// { dg-require-normal-mode "" }
// { dg-options "-std=gnu++11" }
#include <cmath>
@@ -27,6 +28,8 @@
void test01()
{
+ bool test __attribute__((unused)) = true;
+
using __gnu_test::counter_type;
const std::size_t nb_values = 1000;
@@ -44,7 +47,7 @@
std::push_heap(values.begin(), values.end());
- VERIFY( counter_type::less_compare_count <= std::log(values.size()) );
+ VERIFY( counter_type::less_compare_count <= std::log2(values.size()) );
}
int main()
Index: testsuite/25_algorithms/sort_heap/complexity.cc
===================================================================
--- testsuite/25_algorithms/sort_heap/complexity.cc (revision 216348)
+++ testsuite/25_algorithms/sort_heap/complexity.cc (working copy)
@@ -27,6 +27,8 @@
void test01()
{
+ bool test __attribute__((unused)) = true;
+
using __gnu_test::counter_type;
const std::size_t nb_values = 1000;
@@ -43,7 +45,7 @@
std::sort_heap(values.begin(), values.end());
- VERIFY( counter_type::less_compare_count <= 2.0 * nb_values * std::log(nb_values) );
+ VERIFY( counter_type::less_compare_count <= 2.0 * nb_values * std::log2(nb_values) );
}
int main()
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: sort_heap complexity guarantee
2014-10-22 21:13 ` François Dumont
@ 2014-10-22 23:53 ` Jonathan Wakely
2014-10-23 0:18 ` Paolo Carlini
1 sibling, 0 replies; 9+ messages in thread
From: Jonathan Wakely @ 2014-10-22 23:53 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
On 22/10/14 23:05 +0200, François Dumont wrote:
>Then I think we need this patch which also fix other issues.
>
>2014-10-22 François Dumont <fdumont@gcc.gnu.org>
>
> * testsuite/25_algorithms/make_heap/complexity.cc: Add missing test
> variable.
> * testsuite/25_algorithms/sort_heap/complexity.cc: Likewise and use
> log2.
> * testsuite/25_algorithms/pop_heap/complexity.cc: Likewise and require
> normal mode.
> * testsuite/25_algorithms/push_heap/complexity.cc: Likewise.
>
>Tested under Linux x86_64.
>
>Ok to commit ?
Yes, looks good - thanks.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: sort_heap complexity guarantee
2014-10-22 21:13 ` François Dumont
2014-10-22 23:53 ` Jonathan Wakely
@ 2014-10-23 0:18 ` Paolo Carlini
1 sibling, 0 replies; 9+ messages in thread
From: Paolo Carlini @ 2014-10-23 0:18 UTC (permalink / raw)
To: François Dumont, libstdc++, gcc-patches
Hi,
On 10/22/2014 11:05 PM, François Dumont wrote:
> + VERIFY( counter_type::less_compare_count <= 2.0 * std::log2(nb_values) );
Nit: log2 isn't in C89, thus we shouldn't use it unconditionally, ie, if
the test isn't guarded by { dg-require-cmath "" }. Thus, either the
latter, or just express log_2 in terms of log / log10.
Paolo.
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2014-10-22 23:53 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <5431A354.2050404@gmail.com>
[not found] ` <alpine.DEB.2.11.1410052245150.5366@stedding.saclay.inria.fr>
2014-10-06 21:00 ` sort_heap complexity guarantee François Dumont
2014-10-06 21:05 ` Daniel Krügler
2014-10-07 21:11 ` François Dumont
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
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).