On 01/19/2016 12:39 AM, Andrei Alexandrescu wrote:
On 1/18/16 6:18 PM, Ilya wrote:
On Monday, 18 January 2016 at 20:45:56 UTC, Ivan Kazmenko wrote:
On Monday, 18 January 2016 at 12:00:10 UTC, Ivan Kazmenko wrote:
Here goes the test which shows quadratic behavior for the new version:
http://dpaste.dzfl.pl/e4b3bc26c3cf
(dpaste kills the slow code before it completes the task)
Correction: this is the result of removing a uniform call in pull
3921. Since we are supposed to discuss the improvements related to
pull 3934 here, I created a separate entry for the issue:
https://issues.dlang.org/show_bug.cgi?id=15583.
A RNGs don't improve worst case. It only changes an permutation for
worst case. --Ilya
Well it does improve things. The probability of hitting the worst case
repeatedly is practically zero, and it's impossible to create an attack
input.
I'm not sure whether we should worry about this. Probably we do because
sort attacks are a press favorite.
The nice thing about not relying on randomness is that pure functions
can call sort, topN etc.
As a sort of a compromise I was thinking of seeding the RNG with not
only the length of the range, but also the integral representation of
the address of the first element. This would still allow an attack if
the input is always at the same address.
Thoughts?
Andrei
https://en.wikipedia.org/wiki/Introselect
