Trouvez la date la plus proche dans le tableau avec JavaScript

J'ai un tableau avec des jours. Chaque jour est un objet, par exemple:

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

J'ai également ajouté un attribut d'horodatage à chaque jour, en utilisant:

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

Les jours dans le tableau sont arbitraires, donc il n'y a pas de véritable logique.

Maintenant, je souhaite trouver les deux jours les plus proches à une date donnée. Donc, si le tableau contenant des jours contient

  • 2 août 2012
  • 4 août 2012
  • 23 août 2012

Et je recherche le 11 août 2012, je veux qu'il retourne le 4 août 2012 et le 23 août 2012.

J'ai essayé d'utiliser une réponse d'une autre question qui ressemble à ceci:

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

Cependant, cela revient unidentified .

Quel serait le moyen le plus efficace (moins de processeur / mémoire) pour y parvenir?

Modifier: "Cependant, comment ces résultats sont-ils" étranges "? Pourriez-vous fournir un exemple de votre code et de vos données?"

J'utilise maintenant ce qui suit pour générer un tableau de dates:

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

La partie étrange est, en utilisant le code ci-dessous, cela ne fonctionne que pour un ensemble de 10 dates ou plus court. Chaque fois que j'utilise un tableau de 11 ou plus de dates, les résultats deviennent inattendus.

Par exemple: en utilisant un tableau de 15 dates, à partir du 6 août 2012, au 21 août 2012. Si je puis appeler findClosest(full_day_array, new Date("30/07/2012"); vous vous attendez à ce qu'il retourne {nextIndex: 0, prevIndex: -1} . Cependant, il retourne {nextIndex: 7, prevIndex: -1} . Pourquoi?

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

Vous pouvez facilement utiliser la fonction de sort avec une fonction de comparateur personnalisée:

 // 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] 

Pour obtenir uniquement les résultats avant ou après le diffdate , vous pouvez filtrer le tableau pour cela:

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

Si vous avez votre matrice personnalisée avec les {the_date_object: new Date(...)} , vous devrez adapter l'algorithme de tri avec

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

Si vous utilisez un ensemble d'objets Date au lieu de votre structure auto définie, cela peut être réalisé très facilement dans 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] */ 

Si le tableau est trié, il peut être atteint dans O (log N) avec recherche binaire.

Edit: "il est crucial que je trouves le match le plus proche avant et après la date"

 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 */ 

La réponse de Zeta est excellente, mais j'étais intéressé par la façon dont vous abordiez cela si vous vouliez connaître les objets N les plus proches dans les deux sens. Voici ma coucou:

 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]]]); 

Cela fonctionne, quelle que soit la durée du rang de dates:

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