Re: Soundness of table.sort

[Dirk Laurie <dirk.laurie@...>]

2015-11-04 22:04 GMT+02:00 Roberto Ierusalimschy <roberto@inf.puc-rio.br>:

> About DoS atacks based on "bad data", if that is a real problem it can
> be easily solved introducing some randomness when choosing a pivot.

In fact, Sedgewick's more recent publications do just that.

> (I must confess that I do not know the "known worst case" Dirk talked
> about.)

Attached. (BTW is it just my system, or does

$ lua -l worstcase
Lua 5.3.1  Copyright (C) 1994-2015 Lua.org, PUC-Rio
> for k=1,16 do
x = worstcase(k)
tic = os.clock(); table.sort(x); toc=os.clock()
dt = toc-tic
print(k,#x,dt)
end
1    2    5.9999999999999e-06
2    4    3e-06
3    8    3.0000000000004e-06
4    16    7.0000000000001e-06
5    32    1.8e-05
6    64    5.8e-05
7    128    0.000231
8    256    0.000798
9    512    0.003118
10    1024    0.012059
11    2048    0.034195
12    4096    0.135313
13    8192    0.539751
14    16384    2.156882
15    32768    8.627574
16    65536    34.557539
>

$ lua5.2 -l worstcase
Lua 5.2.4  Copyright (C) 1994-2015 Lua.org, PUC-Rio
> print(worstcase(8))
{1,129,3,193,5,131,7,225,9,133,11,195,13,135,15,241,17,137,19,197,21,139,23,
227,25,141,27,199,29,143,31,249,33,145,35,201,37,147,39,229,41,149,43,203,
45,151,47,243,49,153,51,205,53,155,55,231,57,157,59,207,61,159,63,253,65,
161,67,209,69,163,71,233,73,165,75,211,77,167,79,245,81,169,83,213,85,171,
87,235,89,173,91,215,93,175,95,251,97,177,99,217,101,179,103,237,105,181,
107,219,109,183,111,247,113,185,115,221,117,187,119,239,121,189,123,223,
125,191,127,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,
48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98,
100,102,104,106,108,110,112,114,116,118,120,122,124,126,128,130,132,134,
136,138,140,142,144,146,148,150,152,154,156,158,160,162,164,166,168,170,
172,174,176,178,180,182,184,186,188,190,192,194,196,198,200,202,204,206,
208,210,212,214,216,218,220,222,224,226,228,230,232,234,236,238,240,242,
244,246,248,250,252,254,256,255}

--- worstcase.lua
-- Lua table.sort requires more than k^2/4 comparisons for the array
-- of length k=2^n generated by the following subroutine with n>1.

local concat = table.concat
return function (n)
   local a=setmetatable({},{__tostring = 
      function(t) return '{'..concat(t,',')..'}' end})
   local i=1
   n=2^n
   a[1]=1; a[n]=n-1
   for k=1,n/2-1,2 do a[k]=k end   
   for k=n/2,n-1 do a[k]=2*k-n+2 end
   local d,j,j0=4,2,1
   for k=n/2+1,n-2,2 do
      a[j]=k; j=j+d;  
      if j>n/2 then 
         d=d*2 
         j0=j0+1; 
         while a[j0] do j0=j0+1 end
         j=j0 
      end
   end
   return a   
end