Никогда не делайте компараторов на базе вычитания

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

Рассмотрим следующий код:

import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;
import java.util.Collections;
import java.util.List;
import static java.util.Arrays.*;
import static org.testng.Assert.assertEquals;

public class ComparatorAlgTest {
    List<Integer> list1, list2;

    @BeforeMethod
    public void init(){
        list1 = asList(1,2);
        list2 = asList(Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    void check(String name){
        System.out.println(name+" list1 = " + list1);
        System.out.println(name+" list2 = " + list2);

        assertEquals(list1, asList(1,2) );
        assertEquals(list2, asList(Integer.MIN_VALUE, Integer.MAX_VALUE) );
    }

    @Test
    public void testWrong() {
        Collections.sort(list1, (Integer a, Integer b) -> a-b );
        Collections.sort(list2, (Integer a, Integer b) -> a-b );
        check("wrong");
    }

    @Test
    public void testFine() {
        Collections.sort(list1, (Integer a, Integer b) -> a.equals(b)? 0: a>b ? 1:-1 );
        Collections.sort(list2, (Integer a, Integer b) -> a.equals(b)? 0: a>b ? 1:-1 );
        check("fine");
    }
}

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

fine list1 = [1, 2]
fine list2 = [-2147483648, 2147483647]
wrong list1 = [1, 2]
wrong list2 = [2147483647, -2147483648]


На самом деле, пара чисел (Integer.MIN_VALUE, Integer.MAX_VALUE) является далеко не единственной комбинацией, при которой subtraction-driven компаратор сработает неверно. Для того, чтобы результат был некорректным, необходимо и достаточно, чтобы при вычитании произошло переполнение. Например, можно подставить asList(-2, Integer.MAX_VALUE), и subtraction-driven сравнение не сработает тоже.

Автор: chabapok

Источник