使用JavaScript查找数组中最接近的日期

Question

我有一个包含日期的数组。每个日期都是一个对象，例如：

{day_year: "2012", day_month: "08", day_number: "03", day_name: "mon"}

我还通过使用如下代码向每个日期对象中添加了一个时间戳属性：

function convertDays() {
    var max_i = days.length;
    for(var i = 0; i < max_i; i++) {
        var tar_i = days[i];
        tar_i.timestamp = new Date(tar_i.day_year, tar_i.day_month, tar_i.day_number);
    }
}

这个数组中的日期是随意的，所以没有真正的逻辑关系。

现在我想找到离任何给定日期最近的两个日期。如果这个日期数组包含以下日期：

• 2012年8月2日
• 2012年8月4日
• 2012年8月23日

并且我搜索的日期是2012年8月11日，那么我希望它返回2012年8月4日和2012年8月23日。

我尝试使用另一个问题的答案，看起来像这样:

function findClosest(a, x) {
    var lo, hi;
    for(var i = a.length; i--;) {
        if(a[i] <= x && (lo === undefined || lo < a[i])) lo = a[i];
        if(a[i] >= x && (hi === undefined || hi > a[i])) hi = a[i];
    }
    return [lo, hi];
}

然而，这返回了未标识。

如何以最高效的方式（最少的处理器/内存开销）实现这一点？

编辑： "然而，那些结果为何"奇怪"？ 你能提供你的代码和数据的一个例子吗？"

我现在正在使用以下内容生成日期数组：

var full_day_array = [];
for(var i = 0; i < 10; i++) {
    var d = new Date();
    d.setDate(d.getDate() + i);
    full_day_array.push({day_year: d.getFullYear().toString(), day_month: (d.getMonth() + 1).toString(), day_number: d.getDate().toString()});
}

奇怪的是，使用下面的代码时，只有长度为10或更短的日期数组才有效。每当我使用11个或更多日期的数组时，结果就会变得出乎意料。

例如：使用一个由15个日期组成的数组，从2012年8月6日到2012年8月21日。如果我调用findClosest(full_day_array, new Date("30/07/2012"));，你会期望它返回{nextIndex: 0, prevIndex: -1}。然而，它却返回了{nextIndex: 7, prevIndex: -1}。为什么呢？

function findClosest(objects, testDate) {
    var nextDateIndexesByDiff = [],
        prevDateIndexesByDiff = [];

    for(var i = 0; i < objects.length; i++) {
        var thisDateStr = [objects[i].day_month, objects[i].day_number, objects[i].day_year].join('/'),
            thisDate    = new Date(thisDateStr),
            curDiff     = testDate - thisDate;

        curDiff < 0
            ? nextDateIndexesByDiff.push([i, curDiff])
            : prevDateIndexesByDiff.push([i, curDiff]);
    }

    nextDateIndexesByDiff.sort(function(a, b) { return a[1] < b[1]; });
    prevDateIndexesByDiff.sort(function(a, b) { return a[1] > b[1]; });


    var nextIndex;
    var prevIndex;

    if(nextDateIndexesByDiff.length < 1) {
        nextIndex = -1;
    } else {
        nextIndex = nextDateIndexesByDiff[0][0];
    }
    if(prevDateIndexesByDiff.length < 1) {
        prevIndex = -1;
    } else {    
        prevIndex = prevDateIndexesByDiff[0][0];
    }
    return {nextIndex: nextIndex, prevIndex: prevIndex};
}

- Rein

---

为什么你用那种格式呢？你能把它们改成时间戳的格式吗？这样你就可以更容易地解析它们为正确的日期对象了。 - Esailija

我确实可以将它们更改为时间戳，例如通过循环遍历这些天并向它们添加一个名为“timestamp”的属性：days[i].timestamp = new Date(days[i].day_year, days[i].day_month, days[i].day_number); 这样做有帮助吗？ - Rein

如果你想谈论效率，那么你应该定义如何使用它。例如，重要的是你需要在一组日期中找到最近的一个日期，还是你将拥有相同的日期集并多次搜索它们。 - Snowbear

我有最多五组天数，每组包含约200天。然后我有最多100个日期需要找到最接近的两个天数。 - Rein

应该是 typeof lo == "undefined"。 - James

请注意，Date构造函数接受一个MM/DD/YYYY格式的字符串。不幸的是，new Date("30/07/2012");会被解析为字符串"Invalid Date"，而不是抛出异常。 - cantlin

Answer 1

你可以轻松地使用sort函数与自定义的比较器函数：

// assuming you have an array of Date objects - everything else is crap:
var arr = [new Date(2012, 7, 1), new Date(2012, 7, 4), new Date(2012, 7, 5), new Date(2013, 2, 20)];
var diffdate = new Date(2012, 7, 11);

arr.sort(function(a, b) {
    var distancea = Math.abs(diffdate - a);
    var distanceb = Math.abs(diffdate - b);
    return distancea - distanceb; // sort a before b when the distance is smaller
});

// result:
[2012-08-05, 2012-08-04, 2012-08-01, 2013-03-20]

要获取diffdate之前或之后的结果，您可以为数组进行筛选：

var beforedates = arr.filter(function(d) {
    return d - diffdate < 0;
}),
    afterdates = arr.filter(function(d) {
    return d - diffdate > 0;
});

如果您使用自定义数组，并且该数组包含 {the_date_object: new Date(...)} 对象，则需要调整排序算法。

    var distancea = Math.abs(diffdate - a.the_date_object);
    var distanceb = Math.abs(diffdate - b.the_date_object);

- Bergi

---

+1：sort() 的使用很好。但是这样不会导致 O(N log N) 的运行时间吗？ - Zeta

当然，这取决于您是想按顺序获取所有日期还是只需要一个选择算法。 - Bergi

我喜欢这个，filter()方法没想到过。也可以很好地转换为underscore等工具库。 - cantlin

Answer 2

如果你使用一个 Date 对象数组代替你自定义的结构，这个问题可以非常容易地以 O(N) 的复杂度解决：

var testDate = new Date(...);
var bestDate = days.length;
var bestDiff = -(new Date(0,0,0)).valueOf();
var currDiff = 0;
var i;

for(i = 0; i < days.length; ++i){
   currDiff = Math.abs(days[i] - testDate);
   if(currDiff < bestDiff){
       bestDate = i;
       bestDiff = currDiff;
   }   
}

/* the best date will be days[bestDate] */

如果数组已排序，则可以使用二分查找以O(log N)的时间复杂度实现。

编辑：“在找到日期之前和之后，找到最接近的匹配非常重要”

var testDate = new Date(...);

var bestPrevDate = days.length;
var bestNextDate = days.length;

var max_date_value = Math.abs((new Date(0,0,0)).valueOf());

var bestPrevDiff = max_date_value;
var bestNextDiff = -max_date_value;

var currDiff = 0;
var i;

for(i = 0; i < days.length; ++i){
   currDiff = testDate - days[i].the_date_object;
   if(currDiff < 0 && currDiff > bestNextDiff){
   // If currDiff is negative, then testDate is more in the past than days[i].
   // This means, that from testDate's point of view, days[i] is in the future
   // and thus by a candidate for the next date.
       bestNextDate = i;
       bestNextDiff = currDiff;
   }
   if(currDiff > 0 && currDiff < bestPrevDiff){
   // If currDiff is positive, then testDate is more in the future than days[i].
   // This means, that from testDate's point of view, days[i] is in the past
   // and thus by a candidate for the previous date.
       bestPrevDate = i;
       bestPrevDiff = currDiff;
   }   

}
/* days[bestPrevDate] is the best previous date, 
   days[bestNextDate] is the best next date */

- Zeta

---

我可以将日期对象添加到数组中，但是日期必须成为子对象，因为每个日期对象还包含其他（与此问题无关的）信息。您的方法是否也能够搜索数组中对象的属性并返回包含最接近匹配属性的对象？ - Rein

此外，我必须找到目标日期之前和之后最接近的匹配日期，这非常重要，因此我必须始终得到两个日期，除非目标日期在数组中的第一天之前或最后一天之后。 - Rein

@ReinoudSchuijers：上面提供的方法不需要排序数组。但是，你说的那些结果为什么“奇怪”呢？你能提供一下你的代码和数据的例子吗？ - Zeta

我明白。然而，days[4]是未定义的（数组长度为4，因此数组中的最后一个对象是days[3]），而且days[0]并不是最好的下一个日期，因为它实际上是过去的日期。 - Rein

@ReinoudSchuijers：我真是太傻了，不小心使用了错误的比较方式。此外，“bestNextDiff”和“bestPrevDiff”的起始值也是错误的。 - Zeta

Answer 3

您可以尝试像这样使用它。

var dates = [
'July 16, 1995 03:24:00',
'Aug 18, 1995 03:24:00',
'August 19, 1995 03:24:00',
'September 17, 1995 03:24:00',
'September 14, 1995 03:24:00',
'August 18, 1995 03:24:00',
'July 16, 1995 03:24:00',
'December 15, 1995 03:24:00',
'July 13, 1995 03:24:00',
]

var temp = dates.map(d => Math.abs(new Date() - new Date(d).getTime()));
var idx = temp.indexOf(Math.min(...temp));
console.log(dates[idx]);

- Talha Noyon

Answer 4

Zeta的回答非常好，但是如果你想知道两个方向上最近的N个对象，你会如何处理呢？这是我的尝试：

var objects = [
    { day_year: "2012",
      day_month: "08",
      day_number: "02"
    },
    { day_year: "2012",
      day_month: "08",
      day_number: "04"
    },
    { day_year: "2012",
      day_month: "08",
      day_number: "23"
    }
];

var testDate = new Date('08/11/2012'),
    nextDateIndexesByDiff = [],
    prevDateIndexesByDiff = [];

for(var i = 0; i < objects.length; i++) {
    var thisDateStr = [objects[i].day_month, objects[i].day_number, objects[i].day_year].join('/'),
        thisDate    = new Date(thisDateStr),
        curDiff     = testDate - thisDate;

    curDiff < 0
        ? nextDateIndexesByDiff.push([i, curDiff])
        : prevDateIndexesByDiff.push([i, curDiff]);
}

nextDateIndexesByDiff.sort(function(a, b) { return a[1] < b[1]; });
prevDateIndexesByDiff.sort(function(a, b) { return a[1] > b[1]; });

console.log(['closest future date', objects[nextDateIndexesByDiff[0][0]]]);
console.log(['closest past date', objects[prevDateIndexesByDiff[0][0]]]);

- cantlin

---

因为某些原因，这个方法对我有效，而Zeta的回答并没有。【编辑】：在你改变它之前它是有效的。现在我在 “...? nextDateIndexesByDiff.push([i, curDiff]); : prevDateIndexesByDiff...”处收到一个错误（意外token ;)）。 - Rein

抱歉，当我将if/else转换为三元运算符时，添加了语法错误。 - cantlin

没问题。对于未来的日期，可以通过以下方式改进日志记录：if(nextDateIndexesByDiff.length < 1) { console.log("没有未来的日期"); } else { console.log(['最接近的未来日期', objects[nextDateIndexesByDiff[0][0]]]); } if(prevDateIndexesByDiff.length < 1) { console.log("过去没有日期"); } else { console.log(['最接近的过去日期', objects[prevDateIndexesByDiff[0][0]]]); }否则会出现错误。 - Rein

这个方法似乎仍然存在问题。每当日期数组超过10个时，就会出现问题。我使用以下代码来生成数组：for(var i = 0; i < 11; i++) { var d = new Date(); d.setDate(d.getDate() + i); full_day_array.push({day_year: d.getFullYear().toString(), day_month: (d.getMonth() + 1).toString(), day_number: d.getDate().toString()}); } - Rein

请查看我对这个问题的评论。 - cantlin

Answer 5

这是我们使用的内容：

该函数在数组中查找最接近日期（名为dateParam）到dateToCompare的项目。

对于每个项[dateParam]，返回具有最接近日期的数组元素dateToCompare。

getClosestDateInArray (array, dateParam, dateToCompare) {
  let minDiff = null;
  let mostAccurateDate = array[0];
  array.map((item) => {
    const diff = Math.abs(moment(dateToCompare).diff(item[dateParam], 'minutes', true));
    if (!minDiff || diff < minDiff) {
      minDiff = diff;
      mostAccurateDate = item
    }
  });
  return mostAccurateDate;
}

这个解决方案需要使用momentJS库。

- Philippe Genois

Answer 6

无论日期数组有多长，这都是有效的：

function newFindClosest(dates, testDate) {
    var before = [];
    var after = [];
    var max = dates.length;
    for(var i = 0; i < max; i++) {
        var tar = dates[i];
        var arrDate = new Date(tar.day_year, tar.day_month, tar.day_number);
        // 3600 * 24 * 1000 = calculating milliseconds to days, for clarity.
        var diff = (arrDate - testDate) / (3600 * 24 * 1000);
        if(diff > 0) {
            before.push({diff: diff, index: i});
        } else {
            after.push({diff: diff, index: i});
        }
    }
    before.sort(function(a, b) {
        if(a.diff < b.diff) {
            return -1;
        }
        if(a.diff > b.diff) {
            return 1;
        }
        return 0;
    });

    after.sort(function(a, b) {
        if(a.diff > b.diff) {
            return -1;
        }
        if(a.diff < b.diff) {
            return 1;
        }
        return 0;
    });
    return {datesBefore: before, datesAfter: after};
}

- Rein