topN using a heap

[Ilya via Digitalmars-d]

On Tuesday, 19 January 2016 at 01:04:03 UTC, Andrei Alexandrescu 
wrote:
> On 1/18/16 7:46 PM, Ilya wrote:
>> On Tuesday, 19 January 2016 at 00:38:14 UTC, Timon Gehr wrote:
>>> On 01/19/2016 01:12 AM, Ilya wrote:
>>>>>
>>>>
>>>> There is already implementation with predictable seed. Proof:
>>>> https://github.com/D-Programming-Language/phobos/blob/master/std/random.d#L1151
>>>>
>>>> --Ilya
>>>
>>> The default RNG is seeded with unpredictableSeed. What is the 
>>> point
>>> you are trying to make?
>>
>> unpredictableSeed is initialized only once and can be easily 
>> estimated.
>> --Ilya
>
> https://github.com/D-Programming-Language/phobos/blob/v2.069.2/std/random.d#L1120
>
> unpredictableSeed uses MinstdRand0. The sources of randomness 
> used for initializing MinstdRand0 are the PID, the thread ID, 
> and the system time at the moment of the seeding. Then at each 
> subsequent call to unpredictableSeed, the time of the call is 
> XORed with the current value of the MinstdRand0.
>
> How do you think things could be improved?
>
>
> Andrei

A good variant with minimal overhead is to call unpredictableSeed 
for sorting big arrays each time (one seed per array):
    a. A hacker would not be able to estimate a seed using other 
API calls. For example, "give me a set of random numbers".
    b. A hacker would not be able to estimate a seed using a small 
arrays because they don't use RNGs. (and they have not any 
overhead!)
    c. A hacker would not be able to estimate a seed for big 
arrays, because attack based on time measurement would not work 
for big arrays.

EDIT:
   c. ... because each big array has own seed and time measurement 
would not work for big arrays with different seeds.

__EDIT2__:
To be fair (c) is not really correct. To do (c) correct a thread 
local global seed should be used to generate unpredictableSeed 
for each big arrays.

Ilya