Лучший способ найти дату, ближайшую к цели в списке дат?

Question

У меня есть список объектов Date и целевой даты. Я хочу найти дату в списке, ближайшую к целевой дате, но только даты, предшествующие целевой дате.

Пример: 2008-10-1 2008-10-2 2008-10-4

С целевой датой 2008-10-3, я хочу получить 2008-10-2

Каков наилучший способ сделать это?

Answer 1

Решение Sietse de Kaper предполагает обратный отсортированный список, определенно не самая естественная вещь, чтобы иметь около

Естественный порядок сортировки в java соответствует возрастающему естественному порядку. (см. Collection.sort http://java.sun.com/j2se/1.5.0/docs/api/java/util/Collections.html#sort(java.util.List) документация)

Из вашего примера

target date = 2008-10-03 
list = 2008-10-01 2008-10-02 2008-10-04 

Если другой разработчик использует ваш метод с наивным подходом, он получит 2008-10-01, а это не то, что ожидалось

Не делайте предположений относительно порядка следования списка. Если вам необходимо по соображениям производительности попытаться следовать наиболее естественному соглашению (отсортировано по возрастанию) Если вам действительно нужно следовать другому соглашению, вам действительно следует задокументировать его.

private Date getDateNearest(List<Date> dates, Date targetDate){
  Date returnDate = targetDate
  for (Date date : dates) {
    // if the current iteration'sdate is "before" the target date
    if (date.compareTo(targetDate) <= 0) {
      // if the current iteration's date is "after" the current return date
      if (date.compareTo(returnDate) > 0){
        returnDate=date;
      }
    }
  }  
  return returnDate;
}

edit - мне также нравится ответ Treeset, но я думаю, что он может быть немного медленнее, поскольку это эквивалентно сортировке данных, затем их поиску => nlog (n) для сортировки, а затем из документации следует, что это log (n) для доступа, таким образом, было бы nlog (n) + log (n) против n

Answer 2

private Date getDateNearest(List<Date> dates, Date targetDate){
    return new TreeSet<Date>(dates).lower(targetDate);
}

Не требует предварительно отсортированный список, TreeSort это исправляет. Он вернет ноль, если не сможет найти его, поэтому вам придется изменить его, если это проблема. Не уверен в эффективности либо: P

Answer 3

В настоящее время я использую следующий метод, но я не уверен, что он наиболее эффективен, поскольку он предполагает уже отсортированный список и (потенциально) выполняет итерацию по каждой дате в списке.

private Date getDateNearest(List<Date> dates, Date targetDate){
  for (Date date : dates) {
    if (date.compareTo(targetDate) <= 0) return date;
  }

  return targetDate;
}

Answer 4

NavigableSet::lower

Ответ Keeg умно краток. Идея состоит в том, чтобы использовать метод lower, определенный в интерфейсе NavigableSet и реализованный в классе TreeSet.

Но, как и в других ответах, он использует старые устаревшие классы даты и времени, включенные в самые ранние версии Java. Ниже обновленная версия с использованием java.time классов.

Старый вопрос и ответы используют либо java.util.Date, который является моментом на временной шкале в UTC, представляющем как дату и время суток, либо java.sql.Date, который неловко расширяет время использования. Дата, притворяясь, что у нее нет времени суток. Запутанный беспорядок.

java.time

Эти неприятные старые классы были вытеснены классами java.time , встроенными в Java 8 и более поздние версии. См. Oracle Tutorial . Большая часть функциональности была перенесена в Java 6 & 7 в ThreeTen-Backport и дополнительно адаптирована для Android в ThreeTenABP .

LocalDate

Класс LocalDate представляет значение только для даты без времени суток и без часового пояса. Хотя эти объекты не хранят часовой пояс, обратите внимание, что часовой пояс (ZoneId) имеет решающее значение при определении текущей даты. В любой момент времени дата меняется по всему земному шару в зависимости от часового пояса.

ZoneId zoneId = ZoneId.of( "America/Montreal" );
LocalDate today = LocalDate.now( zoneId );  // 2016-06-25

ISO 8601

Подсказка: добавьте цифры месяца и дня месяца в начальный ноль. Это позволяет им соответствовать стандартным форматам даты и времени ISO 8601 . Эти форматы по умолчанию используются в java.time при разборе / генерации строк, представляющих значения даты и времени.

Поэтому используйте 2008-10-01 вместо 2008-10-1. Если заполнение невозможно, выполните синтаксический анализ, используя DateTimeFormatter.

NavigableSet dates = new TreeSet( 3 );
dates.add( LocalDate.parse( "2008-10-01" );
dates.add( LocalDate.parse( "2008-10-02" );
dates.add( LocalDate.parse( "2008-10-04" );
LocalDate target = LocalDate.parse( "2008-10-03" );
LocalDate hit = dates.lower( target );
// Reminder: test for `null == hit` to see if anything found.

Answer 5

Хотя ответ от Keeg действителен в 1.6 в 1.5, нет более низкого метода () (Мы неудачно развиваемся против 1.5 :-()

этот работает в 1,5

import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
import java.util.List;
import java.util.TreeSet;

public class GetNearestDate {

  public static void main( String[] args ) throws ParseException {

    final SimpleDateFormat simpleDateFormat = new SimpleDateFormat( "dd.MM.yyyy HH:mm:ss" );

    List< Date > otherDates = Arrays.asList( new Date[]{
      simpleDateFormat.parse( "01.01.2008 01:00:00" ) ,
      simpleDateFormat.parse( "01.01.2008 01:00:02" ) } );
    System.out.println( simpleDateFormat.parse( "01.01.2008 01:00:00" ).equals(
      get( otherDates , simpleDateFormat.parse( "01.01.2008 01:00:01" ) ) ) );
    System.out.println( simpleDateFormat.parse( "01.01.2008 01:00:02" ).equals(
      get( otherDates , simpleDateFormat.parse( "01.01.2008 01:00:03" ) ) ) );
    System.out.println( null == get( otherDates , simpleDateFormat.parse( "01.01.2008 01:00:00" ) ) );
  }

  public static Date get( List< Date > otherDates , Date dateToApproach ) {
    final TreeSet< Date > set = new TreeSet< Date >( otherDates );
    set.add( dateToApproach );
    final ArrayList< Date > list = new ArrayList< Date >( set );
    final int indexOf = list.indexOf( dateToApproach );
    if ( indexOf == 0 )
      return null;
    return list.get( indexOf - 1 );
  }

}

Answer 6

Вы смотрели на API JodaTime? Кажется, я помню, что такая функция была доступна.