jeudi 1 août 2019

How to build a deterministic random plot

I have this interesting problem, a simple but not easy goal:

My server is serving a JSON containing a random plot, in the range [-1,+1]. Each value is sent with the corresponding timestamps, here an example of JSON:

[
 { 1560765102, -0.53 },
 { 1560765103, -0.54 }, 
 { 1560765104, -0.43 }, 
 { 1560765105, -0.21 }, 
 { 1560765106, -0.11 }, 
 { 1560765107, 0.21 }, 
 { 1560765108, 0.34 }, 
 { 1560765109, 0.2 }, 
]

As you can see, the plot is not generated straight from a PRNG (like Math.rand()), otherwise it will look like white noise. Instead, each point value is a function of the previous one. This way the plot looks more like a plausible random temperature signal, which is what I want to show. This is the generator:

var rndvalue = 0;
function random(timestamp)
{
    rndvalue += randomDet(timestamp) * 0.2 - 0.1;
    if(rndvalue > 1) rndvalue = 1;
    if(rndvalue < -1) rndvalue = -1;
    return rndvalue;
}

randomDet() is nothing more than a very simple hash function which gets a timestamp and spits out a real number in the range [-1,+1]. The signal is clamped to -1, +1.

The client requests the plot in a given range, startTimestamp and endTimestamp, the server just loops through all the timestamps in between and builds the JSON:

function getPlot(startTick, endTick)
{
    var points = [];
    var t = startTick;

    while(t < endTick)
    {
        var row = { tick: t, value: random(t) };
        points.push(row);
        t++;
    }

    return points;
}

The problem is, every time the client asks again for the same timestamp interval, the server returns a different plot (zooming in/out get confusing, as the plot changes every time instead of just being re-scaled accordingly). I'd like to have the plot to be deterministic (i.e. to be always the same, if the same timestamp interval is requested)

What I tried

I tried modifying the random() function is such a way that, for every timestamp, it always return the same point value. To do so I had to add a for loop and recompute the entire plot since timestamp = 0 up to the requested timestamp point value. It works but it is very slow, since it's a O(N^2) for every point value, where N is the requested point timestamp.

var rndvalue = 0;
function random(tick)
{
    rndvalue = 0;
    for(var t = 0; t < tick; t++)
    {
        rndvalue += randomDet(t) * 0.2 - 0.1;
        if(rndvalue > 1) rndvalue = 1;
        if(rndvalue < -1) rndvalue = -1;
    }
    return rndvalue;
}

How can it be done in a more efficient way? Ideally O(1)




Aucun commentaire:

Enregistrer un commentaire