Re: sort_heap complexity guarantee

[Marc Glisse <marc dot glisse at inria dot fr>]

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".

--
Marc Glisse

// 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 <iostream>

#include <testsuite_counter_type.h>
#include <testsuite_hooks.h>

void test01()
{
  using __gnu_test::counter_type;
  const std::size_t nb_values = 1000;

  std::vector<counter_type> values={2145604655,2144260022,2145012187,2141866166,2131613452,2138382577,2137717403,2132617961,2105512125,2112414349,2114703785,2131541206,2119204262,2126065515,2137359239,2042406308,2116041146,2054911938,2094366510,2035570266,2077813108,2075663321,2101223735,2082670785,2087992886,2107902297,2090108808,2086318644,2089667579,2125102971,2132822905,2001988033,2040150280,1846689080,2023779221,2041887478,2027318029,2014883947,2010599574,2018682342,2018970185,2074165366,2067452355,2034812998,1936483639,2090807064,2099017812,1939488392,2058052944,2078115166,1926215996,2063669762,2065234875,2014077916,2061931625,1995134491,2046226273,2021067410,2048443356,2036488030,2008523049,2085336564,1685296752,2000328762,1981160259,2028447833,1656807546,1750625230,1840259990,2021335379,1980297743,1923025936,1925713703,2026938331,1978813320,1940868105,1924821879,1905108614,1943354879,2012366659,1979594180,1895216121,1810480256,2005094933,2029982089,2057486179,2003239868,1587690653,1938940203,1895798101,1865706467,2074231364,1795433357,1978195172,2018346201,1805860140,1852305529,1854276844,1973189570,2019800647,2011847568,1838237762,1679438214,1985781479,2034220240,1806958376,2057337897,1722811873,1535163826,1960437177,1975008611,1968835848,1936409746,1939318236,1938153557,1943946622,1958428614,1970311780,1893032387,1862089912,1986113846,1901488868,1972037462,2079263157,1644881292,1402450960,1684687425,1960851178,1491815733,1857614276,1442978165,1398302654,1672575333,1633233697,1173553410,1369877731,1607028055,1508941415,1547519792,1664120107,1584259010,1556532540,1477342532,1846740262,1816956629,1800362308,1224393764,1586307374,1798444728,1751135325,1692060061,1676397917,1877497505,831913538,1707591807,1898426545,1889008098,1801926036,1711958994,1681675687,1942898180,1885194308,1402735004,1763178148,1725661001,1575918423,1535077085,1716791052,1885691574,1952109424,2010629373,2016507144,1964954090,1872085507,1332922344,1135370564,1347928709,1842595295,1301399931,1805356495,1790794807,1500674139,1729611847,1925405336,2000278723,1536499423,1705748172,1880754956,1920196784,1689599566,1879435967,1729897425,1689978706,1838016126,1439131441,1438909732,1350296632,1706820587,1791813533,1960527008,1899248574,1894245194,1829795133,1256767393,1735179809,1654637888,1502071805,1789867793,1974114964,1786633202,2026883943,1431108799,1712676995,2036986511,1880171170,1705505339,1416356983,1458396017,1518366926,1842886362,1413889020,1950067702,1852329797,1962182888,1856027141,1891553430,1142356626,1516263515,1491407155,1230673754,1809226674,1816214361,1734040430,1272720098,1597249952,773910485,1793907221,1448867965,1822807748,1825981191,1839614571,1464408096,1814143384,1630562139,1890443140,1807192764,1691835928,2046660450,1821758154,1043795448,1223877381,1074309507,1162035375,1021943432,577734112,794735260,1760819699,1231520432,1308371848,1518223314,1784313229,1135319460,1415059806,373782484,902293951,1151558085,1649514421,1244198171,1218764019,729686452,989132986,673076335,1068123179,1265271507,1569748880,1185947735,1110674096,1094980815,1449529846,1015812875,1141925799,875814514,739150961,518154457,1192553893,1469898734,763275127,1552515057,1450651157,1141247439,1203664382,1557043295,1671610912,644647122,1058390597,1471358976,1203447023,1448317557,1120216715,1710829116,1605983185,929271593,929801852,1063507561,1324004483,1723160694,1194565006,249809301,788895019,1665347588,190361226,1249968497,1792557244,1541808458,827628411,1635766711,1118137806,1696801462,1332754566,911946773,1582972312,1825784918,759348144,1502939950,1812312819,1181765134,1014264692,1043309103,1675342663,999171220,625053516,1456960973,1486617120,1180583790,1253157833,1540765495,1002945035,690969292,969028438,1908334501,902805067,1895966815,1544263722,1991627404,1923323595,1215887062,1547235029,1239861955,1531917165,1169887968,1083919332,913567521,186634239,1006748747,1145339652,1627625960,1516961652,1003173998,946771095,1604311472,1184563406,1342928241,1751730887,670796502,969497849,943395259,655014093,1486940645,1863241568,1012110633,1119406432,1497838231,1250991948,793778070,1646672808,1645997762,1614026060,1599741532,1503558460,1504654688,1669288609,1718410166,1201181062,1372633664,1502959397,802453627,1361831025,1760414145,1807198714,1373476325,1184891281,1333896836,1340143477,691708488,1014820349,1520166401,1235486276,1668097165,1563531801,1216750199,1123461795,1037566786,775114439,1180255255,1743684412,1762958708,1583119537,959304153,342363809,1312716119,1031068716,1210548978,1636279049,1238313264,1384522177,1607910392,732775483,1657332760,982468357,1184451552,883916015,1556122053,967431796,1112774102,918578010,580543361,1179245020,1920276514,868102089,1189684794,1851588864,820726514,1611393547,1214478256,1282972374,1250607217,945553469,1498248923,619488009,1071389670,1132710137,950879570,756870294,1368148193,1520692179,1516241041,1631130902,295718962,1611714323,1627710790,1521240858,1368851009,1474813385,868308083,983488689,1482050177,1441388598,1458209418,668290896,566063819,966193080,1045094216,1554689713,1776560287,1490770225,1557465328,1604297407,1085599055,1186999527,1348557849,1299628365,481431497,678052153,517344726,1520446082,1059858912,1182289389,1605554265,1771490450,1513549934,1301252903,1796694148,1652781743,823851265,1243128153,1088963638,868793957,1170779568,862176620,1861529923,1394715510,1270149609,1672629537,1211628624,1640365600,1935447561,1771536168,1636257755,1533699434,507826114,910118473,1171389349,669750828,947648378,282260075,480022485,679309624,924485935,673028736,528719308,149284240,464322776,607762622,1392025768,98299498,723795940,427281407,359831057,469005906,1075446019,837977746,1489974375,90016250,830399702,768512497,952597337,625651045,346893791,224042869,592677628,62826072,694219606,780909827,671967829,840960694,475922291,445772521,627866645,248677711,180337254,167487755,966298869,897764297,171148028,567692892,685216268,720798053,414013200,1075445425,74904182,659779684,454143746,1112931387,930692768,69310012,625043028,631314729,356931546,460872689,424912576,864486508,253294364,992149221,804073852,763256335,719378809,385048161,75396108,62857492,124232088,590811370,1323332351,765383351,692259246,14010523,1305822244,646299135,696892483,1328359569,870567978,776657352,273692790,645879678,582829455,1398318971,986488707,106156607,492179424,494579357,1020572343,419300870,111492318,940663889,1110911940,1034765218,633042166,33989949,589238998,153518338,7124416,250341183,1456823511,1574814339,335508222,126093896,37552902,437985219,406706996,826595391,451402508,769552235,523997898,390997881,717169152,1113318251,134259544,127012128,290615456,284293607,74299568,891560184,84247574,60045794,910080498,379040658,595941298,1631859752,1297821128,1097432189,235380019,780478956,1299999732,1475264420,246974285,298807631,1112977679,323868719,1092643814,43558411,364874810,504957426,1082546461,634613597,1387818366,860417938,569459082,433662281,536698109,1254413934,1398270491,490904702,454140742,710212507,142282064,569180046,356722579,413675825,181249746,1599298904,708486001,330698395,40685785,500127119,560925545,1221775615,733617206,874169523,387487402,752866519,1163806464,1025907973,703607752,436192999,451803492,929190930,533846734,270780312,124153051,888415513,724692099,758153528,689119482,680281247,166451015,441998225,1491314756,1392111533,1910273139,329920080,1273878962,471056028,23007635,463263875,504845674,227277093,886878777,455793582,363847210,420501962,412192148,139918270,317994461,854274117,586005325,319995804,173225244,113850687,850039102,352227697,1070583446,256498809,1224876800,364797541,1256928195,1289365084,119199279,683072475,869363758,226803731,1149023379,1174226744,60089217,24021075,615916730,913024785,148413888,1024594291,285074909,42920986,460807280,356714793,698005476,420075110,304466714,223509669,213864544,1390238934,304724457,932079960,290540549,870119218,842379991,614522787,847824791,1455636099,955435684,641628061,544683162,248669192,1216676440,1093585860,1105036732,1629350214,1391859316,1156532508,799831598,1526322411,160865469,644438124,851556424,1040704830,117495223,168509336,615807696,65217713,331218741,118545131,1345456871,1363417253,1009643864,1075037354,484019352,339887665,8414065,610871796,1307428993,1321138682,1043446418,191598146,1246047483,445552910,485062143,527069733,1263612297,1080653288,158075665,147272936,168888715,65620387,180279733,349994330,518424116,726024197,809525925,925853828,1607328916,1616268295,412303366,665135756,435462706,513313327,766620592,1070808954,261152585,797475067,449581284,144608217,757429993,606840189,1492834365,1145836209,1697546262,419702454,375737323,1334989029,897638936,362993316,48903729,118899417,1299723024,202824793,252141300,580630382,833140076,251664301,1477747109,1071328870,651605184,1046664814,950873706,576319872,456347157,1156541171,376582816,47472144,1171629387,1120151536,232648844,185481663,118905353,47598654,274930302,801657482,252981603,254035438,444517124,301600112,17851194,158919575,831620807,11831727,119318445,575555356,674220297,779520901,1181758492,1193530657,154676706,339409069,243171624,527439157,950658755,1660932403,392423049,93616347,494088825,150031357,356745595,505974986,469489732,464834704,189800473,713107695,844216690,438028767,852677800,62400966,65997419,496028039,2569207,61151977,1041314522,414911121,621675927,584276619,500854463,719779285,78619577,333478592,1384793695,559612300,191600217,621199488,1493981411,812132109,87299411,228433135,913372829,742916204,22264634,613626605,425542844,417131552,1007164789,656179748,256617604,1117847479,772896959,753730670,918787224,824733946,1227787495,1161222635,797048703,910342354,32304400,65656526,417835226,39933318,363020357,79236409,98340675,227986873,555603203,867333823,203302942,1550592742,1181160590,422764750,807859218,1399390048,568806022,558942093,933450100,343301523,487871824,515197592,89717332,1133725399,933466836,68968080,1014374151,678344781,250927882,175283876,173824694,132303332,58678155,475665462,1399036266,903219790,671733413,1033379914,37827130,338078218,347385647,328365892,792554902,1361236982,561626644,1355252478,400202763,462945028,1225813823,880391822,1172319591,735850667,15076655,693042104,969891793,384220175,612190352,393457417,465062274,478538718,805880659,514110418,596022233,380809751,772917014,152055244,1198332137,1142857181,561650389,60052677,275819398,883847085,939144091,397969516,621179247,639192820,314648515,1105762736,24646860,572309298,932853536,663776356,448512094,193359895,285344748,2142602217};
/*
  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));
  */
  auto save = values;

  counter_type::reset();

  std::push_heap(values.begin(), values.end());

  if (counter_type::less_compare_count > std::log(values.size()))
  {
    std::cout << "Dump:";
    for (auto i : save) std::cout << ' ' << i.val;
    std::cout << '\n';
    __builtin_exit(1);
  }
}

int main()
{
  test01();
  return 0;
}