почему мы должны возвращать 0, когда Comparator.compare становятся равными - PullRequest
2 голосов
/ 07 октября 2019

Я понимаю, что при реализации метода сравнения интерфейса Comparator нам нужно вернуть

  • + 1, если o1> o2
  • -1, если o1
  • 0, если o1 == o2

мой вопрос, почему мы должны возвращать 0, когда оба равны? каков вариант использования или где он используется? если рассматривать сортировку, когда o2 больше, чем o1, или o2, равное o1, это не меняет ее местоКто-нибудь может прийти, чтобы объяснить практический пример использования этого?

Документация Java гласит:

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

Означает ли это, что значение возврата -1 или возврата 0 имееттакое же влияние?

ноль или положительное целое число

 @Override
    public int compare(Test f1, Test f2) {
        if (f1.getId() > f2.getId()) {
            return 1;
        } else if (f1.getId() < f2.getId()) {
            return -1;
        } else {
            return 0;
        }

    }

Ответы [ 3 ]

6 голосов
/ 07 октября 2019

Если вы вернете -1, когда два сравниваемых значения равны, compare(f1,f2) и compare(f2,f1) оба вернут -1. Это означает, что порядок ваших элементов не будет последовательным. Это может нарушить некоторые алгоритмы сортировки.

Вот почему общий контракт compare требует:

sign(compare(f1,f2)) = -sign(compare(f2,f1))

, что означает, что вы должны вернуть 0, когда два значения равны.

1 голос
/ 07 октября 2019

Когда вы сортируете, -1 и 0 , по сути, очень похожи на порядок сортированного списка, так как элементы, где compareTo оценивается в 0, будут простосгруппированы вместе.

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

Скажем, у нас есть объект Book следующим образом:

import java.util.Comparator;

public class Book implements Comparable {

  String isbn;
  String title;

  public Book(String id, String title) {
    this.isbn = id;
    this.title = title;
  }

  String getIsbn() {
    return isbn;
  }

  String getTitle() {
    return title;
  }

  @Override
  public int compareTo(Object o) {
    return Comparator
            .comparing(Book::getIsbn)
            .thenComparing(Book::getTitle)
            .compare(this, (Book) o);
  }

  @Override
  public  String toString() {
    String output = new StringBuilder()
            .append(isbn).append(":").append(title)
            .toString();
    return output;
  }
}

Здесь мы переписали compareTo книги, чтобы создать пользовательское сравнение, которое сначала проверяет книги isbn, а затемзаглавие.

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

public class Library {

  public static void main(String [] args) {
    List<Book> library = new ArrayList<>();
    library.add(new Book("9780593098240", "Children of Dune"));
    library.add(new Book("9780593098233", "Dune Messiah"));
    library.add(new Book("9780441172719", "Dune"));
    // Just to show the sorting, based on multiple attributes.
    Collections.sort(library);
    System.out.println("Books in library: " + Arrays.toString(library.toArray()));

    // You would obviously have some code for entering a book here, but easier to just create the object for an example. 
    Book newBook = new Book("9780593098240", "Children of Dune");
    for (Book bookInLibrary : library) {
        if (bookInLibrary.compareTo(newBook) == 0) {
            System.out.println("We already have that book in the library.");
            break;
        }
    }
  }
}
1 голос
/ 07 октября 2019

Можно подумать о Алгоритм двоичного поиска со следующей реализацией:

function binary_search(A, n, T):
    L := 0
    R := n − 1
    while L <= R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else if A[m] > T:
            R := m - 1
        else:
            return m
    return unsuccessful

Предположим, существует Comapator, который возвращает одинаковое значение для равных и меньших случаев:

public int compare(Test f1, Test f2) {
        if (f1.getId() > f2.getId()) {
            return 1;
        } else {
            return -1; 
}

Теперь A[m] < T или A[m].compareTo(T) < 0 будет true, когда T равно A[m] и когда A[m] меньше T.

Итак, в этой ситуации:

1 2 3 4 // array and A[m] is 2
2 // target T

2.compareTo(2) возвращает -1, что заставляет алгоритм перейти к следующему выполнению L = m + 1 -> вместо возврата правильного значения.

На самом деле бинарный поиск застревает в бесконечном цикле, прыгая с 2.compareTo(2) и 3.compareTo(2). Надеюсь, это поможет.

...