0

我对 javascript 相当陌生，我在寻找最有效的方法来计算以下问题时遇到了问题

我有一个对象数组。每个对象都有一个时间戳和一个总计字段。我有一个保存为变量的数字，我想遍历数组以找到总字段最接近我的数字的对象的时间戳。

这是一个排序数组，因此数字总是在增加，例如，数字可能如下所示：

Jan 125 
Feb 150 
Mar 200 
Apr 275

如果我的号码是205我想得到结果Mar。

它们是从 mongoDb 获取的对象，所以看起来像这样

{TimeStamp: "2013-06-24 01:00", Delivered: 464, Queued: 39, Total: 503}
{TimeStamp: "2013-07-02 01:00", Delivered: 485, Queued: 37, Total: 522}
{TimeStamp: "2013-07-05 01:00", Delivered: 501, Queued: 41, Total: 542}
{TimeStamp: "2013-07-08 09:48", Delivered: 501, Queued: 64, Total: 565}
4

4 回答 4

1

如果列表已经在正确的字段中排序，您可以使用此代码在 O(n) 中找到最小距离：

var data = [
    {total: 125, name: 'Jan'}, 
    {total: 150, name: 'Feb'}, 
    {total: 200, name: 'Mar'}, 
    {total: 275, name: 'Apr'}
];

function getClosest(arr, value) 
{
    var closest, mindiff = null;

    for (var i = 0; i < arr.length; ++i) {
        var diff = Math.abs(arr[i].total - value);

        if (mindiff === null || diff < mindiff) {
            // first value or trend decreasing
            closest = i;
            mindiff = diff;
        } else {
            // trend will increase from this point onwards
            return arr[closest];
        }
    }
    return null;
}

您跟踪当前最接近的对象及其在总值和搜索值之间的相应（绝对）差异。

只要差异减小，您就会不断更新这两个值。当这种情况不再发生时，您可以立即返回，因为您知道以后它永远不会减少。

要使用它：

getClosest(data, 200);
于 2013-07-08T08:33:44.587 回答
0 
var numbers = [122,231,323,53];
var myNumber = 200;
var difference = 9999; 
var nearest = null;
for (i = 0 ; i < numbers.lenght; i++){
    var candidate = numbers[i];
    var currentDifference = Math.abs(myNumber - candidate);
    if  (currentDifference  < difference) {
        nearest = candidate; difference = currentDifference;
    }
}
于 2013-07-08T08:27:01.567 回答
0

我有这个有用的通用函数：

function min(ary, key) {
    return ary.map(function(x) {
        return [key ? key(x) : x, x]
    }).reduce(function(m, x) {
        return x[0] < m[0] ? x : m;
    })[1]
}

key它使用比较函数在数组中找到最小元素。适用于您的问题：

 number = ...
 closestTimestamp = min(arrayOfRecords, function(record) {
       return Math.abs(number - record.total)
 }).TimeStamp;
于 2013-07-08T08:36:37.600 回答
0

您可以对该值使用二进制搜索。改编自这个答案：

function nearestIndex(arr, compare) { // binary search, with custom compare function
    var l = 0,
        r = arr.length - 1;
    while (l <= r) {
        var m = l + ((r - l) >> 1);
        var comp = compare(arr[m]);
        if (comp < 0) // arr[m] comes before the element
            l = m + 1;
        else if (comp > 0) // arr[m] comes after the element
            r = m - 1;
        else // this[m] equals the element
            return m;
    }
    // now, l == r+1
    // usually you would just return -1 in case nothing is found
    if (l == arr.length) return r;
    if (r == 0) return 0;
    if (Math.abs(compare(arr[l])) > Math.abs(compare(arr[r]))) // "closer"
        return r;
    else
        return l;

}

var items = […];
var i=nearestIndex(items, function(x){return x.Total-532;}); // compare against 532
console.log(items[i].TimeStamp);
于 2013-07-08T09:11:58.903 回答