在一个数组中，如何找到最接近给定浮点值的键？

Question

在一个数组中，如何找到最接近给定浮点值的键？

3

我正在创建一个类似于这样的“加速度”数组：

acc["0100"] = 1;
acc["0300"] = 2;
acc["0600"] = 4;
acc["0900"] = 8;
acc["2000"] = 16;
acc["5000"] = 32;

当用户按下键盘时，我会启动一个计时器：this._startTick = (new Date()).getTime();

现在我有一个计时器来检查键是否仍然被按下。如果是，则我会执行类似以下操作：

this._delay = (new Date()).getTime() - this._startTick;

根据this._delay，现在我想找到先前的值之一（1、2、4或8）。你怎么做？

注意：如果该值大于“5.0”，则结果应始终为32。

注：我的目标是，在给定经过的时间后，找出最佳值。我已按照刚才解释的方式开始处理，但如果您有另一种解决方案，我会接受！

- Olivier Pons

你并没有将 acc 作为一个数组使用，而是将其作为一个对象使用（在 JavaScript 中这可以工作是因为数组继承自 _对象_）。 - Paul S.

@PaulS。好的，我的错。那么也许你有另一种方法来实现我想要做的事情吗？ - Olivier Pons

6个回答

2

操作数组比操作对象更容易：

var accArr = [];
for (time in acc) {
    accArr.push({time: time, value: acc[time]});
}

假设您有一个数组，可以执行以下操作：

function getValue(delay) {
    var diffs = accArr.map(function (e) { return Math.abs(e.time - delay); });
    return accArr[diffs.indexOf(Math.min.apply(null, diffs))].value;
}

编辑：

好的，你没有提到这是一个性能关键的函数。在这种情况下，我建议选择一个粒度（例如0.05，因此延迟的乘数为20），并预先计算从0到MAX_DELAY的所有值：

var multiplier = 20,
    granularity = 1 / multiplier;

var delayValues = (function () {
    var result = [];
    for (var delay = 0; delay <= MAX_DELAY; delay += granularity) {
        result.push(getValue(delay));
    }
    return result;
})();

在动画期间，获取值将是在一个相对较小的表中进行简单查找：

function getValueFast(delay) {
    return (delayValues[Math.round(delay * multiplier)] || 
            delayValues[delayValues.length - 1])
}

JSPerf比较了用这种方法和简单的if语句搜索中间值时的性能，发现它们的表现相同。

- Dzinx

在执行时间方面，是更容易还是更快？ - Olivier Pons

更容易是指“更方便”，因为数组具有对象没有的实用函数：map，indexOf等。对于列表/对象中的5个项目，请不要费心执行时间优化。 - Dzinx

如果我有100个精灵，并且我必须每1/60秒重新计算加速度，这意味着每秒进行60 * 100 * 5 = 30000次比较，而不是"Aadit M Shah"的＃1建议（平均每秒15000次比较）。我认为这是一个“基本”的优化问题，我应该处理好。我不知道我是否错了... - Olivier Pons

在游戏中有100个精灵是很少的（计分、气泡、提示、爆炸等数字，更不用说每个“真实”精灵之间的碰撞检测了（与之前的精灵没有任何碰撞））。 - Olivier Pons

好的，添加了一个针对速度而非优雅性能进行优化的版本 :) - Dzinx

显示剩余3条评论

1

我个人认为，解决这个问题最好的方法是编写一个函数，根据时间使用 if 语句来选择最佳加速度，具体如下：

function getAcceleration(time) {
    if (time < 0.20) return 1;
    if (time < 0.45) return 2;
    if (time < 0.75) return 4;
    if (time < 1.45) return 8;
    if (time < 3.50) return 16;
    return 32;
}

然而，这是一种静态解决方案。如果您可以接受，我建议您使用此方法。另一方面，如果您需要动态解决方案，则请改用以下方法：

var getAcceleration = createAccelerationMap(0.1, 0.3, 0.6, 0.9, 2.0, 5.0);

function createAccelerationMap(previous) {
    var length = arguments.length, limits = [];

    for (var i = 1; i < length;) {
        var current = arguments[i++];
        limits.push((previous + current) / 2);
        previous = current;
    }

    return function (time) {
        var length = limits.length, acceleration = 1;

        for (var i = 0; i < length;) {
            if (time < limits[i++]) return acceleration;
            acceleration *= 2;
        }

        return acceleration;
    };
}

无论哪种方式，您都可以按以下方式使用getAcceleration：

console.log(getAcceleration(0));          // 1
console.log(getAcceleration(0.33));       // 2
console.log(getAcceleration(0.64));       // 4
console.log(getAcceleration(1.42));       // 8
console.log(getAcceleration(3.14));       // 16
console.log(getAcceleration(123456.789)); // 32

查看演示：http://jsfiddle.net/QepT7/

- Aadit M Shah

0

var seconds = this._delay.toString().substring(0,2)

console.log(acc[seconds]);

这是一个直接解决问题的方法：首先将浮点数转换为字符串，然后截取第三个字符之后的所有内容。

- naloxx

这很简单，但如果延迟超过100怎么办？ - Abilash

0

你使用什么单位？

this._startTick = (new Date()).getTime();
//       ms     =                 ms

this._delay = (new Date()).getTime() - this._startTick;
//     ms   =                 ms     -       ms

所以，为了从毫秒转换成"0.1"/等等，我假设你正在进行以下操作：

(Math.floor(ms / 100) / 10).toString();

为什么不把所有东西都保留在ms/100中，这样你就可以使用整数了呢？

var acc = [];
acc[ 1] =  1;
acc[ 3] =  2;
acc[ 6] =  4;
acc[ 9] =  8;
acc[20] = 16;
acc[50] = 32;

然后，您可以创建一个像这样的“最近”查找函数。

function find(x) {
    var i = 0;
    x = x | 0; // The | 0 will cause a cast to int
    if (x < 0) x = 0;
    if (acc[x] !== undefined) return acc[x];
    if (x > acc.length) return acc[acc.length - 1];
    while (++i < acc.length) {
        if (acc[x - i] !== undefined) return acc[x - i];
        if (acc[x + i] !== undefined) return acc[x + i];
    }
}
find(this._delay / 100);

现在的例子如下：

find(30);    // 16
find(100.5); // 32
find(0);     //  1

- Paul S.

你说得完全正确，感谢您的建议，我会用这个想法修改我的代码，但不幸的是这并没有回答我的问题（我的键问题）。 - Olivier Pons

还有一个问题：如果(this._delay / 100) | 0给出的索引超出范围，我希望它能给出可能的最高值(acc[4])。你会怎么做？ - Olivier Pons

@OlivierPons 如果你预计存在大量的_undefined_值，只有少量的已定义值，你可能要考虑使用更接近这里描述的查找函数 https://dev59.com/mGoy5IYBdhLWcg3wZdGr - Paul S.

您还可以使用相应的值（例如acc[2] = 1）填充“acc”的所有元素，并摆脱while循环中的笨拙检查。 - Michael Foukarakis

0

如果0.1是秒数，而你想要保留一位小数，你可以这样做：

// 0.42332 * 10 = 4.2332 
// Math.round( ) will be 4
// 4 / 10 = 0.4
acc[ (Math.round(this._delay * 10) / 10).toString() ]

- Niels

但是几乎所有的指标都在0-1之间。你会如何处理这种情况？ - Abilash

如果没有相应的键怎么办？我的问题不够精确，我会进行修改。 - Olivier Pons

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kol · Accepted Answer

这是一个jsfiddle测试页面，链接在这里。

var getAccForDelay = (function () {
    var acc = {
        0.1: 1,
        0.3: 2,
        0.6: 4,
        0.9: 8,
        2.0: 16,
        5.0: 32
    };

    return function(delay) {
        var key,
            bestKey = undefined,
            absDiff, 
            absDiffMin = Number.MAX_VALUE;

        for (key in acc) {
            if (acc.hasOwnProperty(key)) {
                absDiff = Math.abs(delay - key);
                if (absDiffMin > absDiff) {
                    absDiffMin = absDiff;
                    bestKey = key;
                }
            }
        } 
        return bestKey === undefined ? undefined : acc[bestKey];
    };
}());

测试：

console.clear();
console.log(getAccForDelay(0));
console.log(getAccForDelay(0.33));
console.log(getAccForDelay(3.14));
console.log(getAccForDelay(123456.789));

输出：

=== 更新 ===

上述解决方案没有利用 acc 按键排序的事实。我通过将线性搜索替换为二分查找进行了代码优化，在长数组上速度更快。这里是测试页面。

var getAccForDelay = (function () {
    var accKey   = [ 0.1, 0.3, 0.6, 0.9, 2.0, 5.0 ],
        accValue = [   1,   2,   4,   8,  16,  32 ],
        accLength = accKey.length;

    return function(delay) {
        var iLeft, iMiddle, iRight;

        iLeft = 0;
        if (delay <= accKey[iLeft])
            return accValue[iLeft];
        iRight = accLength - 1;
        if (accKey[iRight] <= delay)
            return accValue[iRight];        
        while (true) {
            if (iRight - iLeft === 1)
                return delay - accKey[iLeft] < accKey[iRight] - delay ? accValue[iLeft] : accValue[iRight];
            iMiddle = ~~((iLeft + iRight) / 2);
            if (delay < accKey[iMiddle])
                iRight = iMiddle;
            else if (accKey[iMiddle] < delay)
                iLeft = iMiddle;
            else
                return accValue[iMiddle];
        }
    };
}());