Ошибка сортировки

Недавно я поддался ностальгии и согласился провести некоторые консультации для клиента. Задача состояла в том, чтобы провести аудит внутреннего качества приложения и, наконец, дать рекомендации по улучшению кодовой базы и возмещению технического долга. Разбирая исходный код, я не мог не заметить ошибку в реализации Comparator .

Этот пост предназначен для того, чтобы понять, как работает сортировка в Java, что такое Comparator и как предотвратить попадание других разработчиков в ту же ловушку. Даже если это очевидно для опытных разработчиков, я все равно считаю, что это хорошее обновление.

Контекст

Большинство языков предлагают готовую реализацию (или нескольких) алгоритмов сортировки.

Scala обеспечивает/| Быструю сортировку Ruby
также предлагает быструю сортировку Python
использует Timsort Java позаимствовала свою реализацию у Python
и т.д.

Предоставление общих утилит как части языкового стека (или библиотеки) имеет два основных преимущества:

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

API сортировки Java

Тем не менее, несмотря на то, что алгоритм предоставлен, он опирается на некоторые свойства базовых элементов, подлежащих сортировке. На Яве, и Я верю, что в каждом строго статически типизированном языке это обеспечивается API через типы.

Обратите внимание, что в последних версиях Java алгоритм сортировки был перенесен из Collections.sort() к методу List.sort() . Последний является методом default . Для получения дополнительной информации об этом шаге, пожалуйста, проверьте мой предыдущий пост на эту конкретную тему.

Метод List.sort() принимает аргумент Comparator . Если это null , алгоритм будет сортировать в соответствии с естественным порядком элементов, который является контрактом Comparable . Если это не так, он будет отсортирован в соответствии с аргументом Comparator . По сути, контракт Comparator.compare() заключается в следующем:

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

— Явадок

Подводя итог, он возвращает o1 минус o2 : разработчик должен определить реализацию операции минус в контексте типа T . При этом Timsort может сравнивать элементы попарно и творить свое волшебство.

Ошибка

Итак, реализация, на которую я наткнулся, заключалась в следующем:

(foo1, foo2) -> {
  if (foo1 == null || foo2 == null) {       // 1
    return 0;
  } else {
    return foo1.compareTo(foo2);            // 2
  }
}

Позаботьтесь о нулевых значениях
Сравните, используя определенный метод. Я использую |/compareTo() в качестве простой иллюстрации

Можете ли вы определить проблему?

Это работает, как и ожидалось, до тех пор, пока null значения не станут частью Списка , подлежащего сортировке. Во время сортировки значение null будет сравниваться с другими значениями Foo : поскольку оно возвращает 0 в этом случае оно будет считаться равным другому значению, даже если последнее не равно null ! Короче говоря, это означает, что null значения не будут переупорядочены и сохранят свой индекс в коллекции.

Исправление

Я считаю, что решение очень простое:

(foo1, foo2) -> {
  if (foo1 == null && foo2 == null) return 0;  // 1
  if (foo1 == null)                 return -1; // 1
  if (foo2 == null)                 return 1;  // 1
  return foo1.compareTo(foo2);
}

Исправление

Вернувшись -1 если оба значения не равны null , значения null всегда рассматриваются как меньшие, чем любое другое значение. Точно так же можно было бы принять решение вернуться 1 чтобы переместить null значения в конец отсортированного списка.

В целом, результат процесса сортировки должен быть одинаковым независимо от начального порядка элементов. Чтобы достичь этого, необходимо последовательно обрабатывать значения null .

Первоначально опубликовано на Фанат Java 26 июля th , 2020

Оригинал: “https://dev.to/nfrankel/a-sorting-bug-fdp”