lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index] 

Alternatively, the attached is based on "A Killer Adversary for
Quicksort". At least for 2^8, it ends up finding a remarkably similar
bad-case input:

$ lua -l adversary
Lua 5.2.1  Copyright (C) 1994-2012 Lua.org, PUC-Rio
> for k=1,15 do
tic = os.clock(); x = adversary(2^k); toc=os.clock()
dt = toc-tic
print(k,#x,dt)
end
1       2       0
2       4       0
3       8       0
4       16      0
5       32      0
6       64      0
7       128     0.0030000000000001
8       256     0.0090000000000003
9       512     0.023000000000001
10      1024    0.078
11      2048    0.23
12      4096    0.89
13      8192    3.678
14      16384   14.514
15      32768   57.052
>

$ lua -l adversary
> print(adversary(2^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,255,256}

On Thu, Nov 5, 2015 at 7:36 AM, Dirk Laurie <dirk.laurie@gmail.com> wrote:
> 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}

Attachment: adversary.lua
Description: Binary data