javascript - 如何构建确定性随机图

Question

我有一个有趣的问题，一个简单但(显然)不容易的问题:

我的服务器正在提供一个包含 [-1,+1] 范围内随机图的 JSON。每个值都带有相应的时间戳，这里是一个 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 }, 
]

如您所见，绘图不是直接从 PRNG(如 Math.rand())生成的，否则它看起来像白 AWGN 噪声。相反，每个点值都是前一个点的函数。这样，情节看起来更像是一个似是而非的随机温度信号，这就是我想要展示的。这是生成器:

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() 只不过是一个非常简单的散列函数，它获取时间戳并输出 [-1,+1] 范围内的实数。信号被钳位到 -1、+1。

客户端请求给定范围内的绘图，startTimestamp 和 endTimestamp，服务器只是循环遍历其间的所有时间戳并构建 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;
}

问题是，每次客户端再次请求相同的时间戳间隔时，服务器都会返回一个不同的图(放大/缩小会让人感到困惑，因为图每次都在变化，而不仅仅是相应地重新缩放)。我想让情节具有确定性(即始终相同，如果请求相同的时间戳间隔)

我尝试过的

我尝试修改 random() 函数，使其对于每个时间戳始终返回相同的点值。为此，我必须添加一个 for 循环并重新计算整个图，因为时间戳 = 0 到请求的时间戳点值。它有效，但速度很慢，因为每个点值都是 O(N^2)，其中 N 是请求的点时间戳。

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;
}

如何以更有效的方式完成它？理想情况下 O(1)

Answer 1

您不必在每次调用 getPlot() 时都重置 rndvalue 的值；因此，getPlot() 返回不同的结果，具体取决于调用该函数时 rndvalue 的值。事实上，函数应该尽可能独立，而不是依赖于“全局”变量。以下解决方案直接使用 randomDet() 并避免使用“全局”变量。请注意，rndvalue 现在是 getPlot() 的局部变量。

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

    while(t < endTick)
    {
        rndvalue += randomDet(t) * 0.2 - 0.1;
        if(rndvalue > 1) rndvalue = 1;
        if(rndvalue < -1) rndvalue = -1;
        var row = { tick: t, value: rndvalue };
        points.push(row);
        t++;
    }

    return points;
}