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

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

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 сравнение не сработает тоже.

Комментарии (25)


  1. apangin
    02.03.2016 01:56
    #8788907
    +7

    Никогда не говорите "никогда" :)
    Даже среди стандартных классов немало примеров компараторов с вычитанием:

    java.lang.Enum

            return self.ordinal - other.ordinal;

    java.lang.String

            while (k < lim) {
            char c1 = v1[k];
            char c2 = v2[k];
            if (c1 != c2) {
                return c1 - c2;
            }
            k++;
        }
        return len1 - len2;

    java.time.Year

            return year - other.year;

    Вычитание и лаконичней, и эффективней. Но, естественно, нужно осознавать диапазон значений.


    1. apangin
      02.03.2016 02:03
      #8788909
      +3

      Кстати, из той же серии. Типичная ошибка при реализации всякого рода lookup-таблиц:

          int hash = Math.abs(obj.hashCode());
    return table[hash % table.length];

      В чём тут подвох? :)


      1. yTko
        02.03.2016 02:13
        #8788921
        +1

        деление на 0?


        1. gurinderu
          02.03.2016 13:05
          #8789783

          В java HashMap table.lenght лежит в промежутке от 1 до 1<<30. Не будет тут 0)


      1. mbait
        02.03.2016 06:25
        #8789021
        +11

        Note that if the argument is equal to the value of Integer.MIN_VALUE, the most negative representable int value, the result is that same value, which is negative.

        Но знают далеко не многие. Я узнал от статического анализатора.


      1. monkegoist
        02.03.2016 13:51
        #8789971

        Это еще модуль вы добавили. Мы недавно словили такой баг, когда ключ одного из объектов перевели из int в String, а id % count заменили просто на id.hashCode() % count. При этом, поскольку это использовалось для распределения нагрузки между нодами, часть объектов просто не обрабатывалась и когда это обнаружили, не сразу стало понятно в чем дело =)


      1. Beholder
        02.03.2016 14:14
        #8790043

        Integer.MIN_VALUE % (1 << x) для любого x равно 0


    1. Beholder
      02.03.2016 13:09
      #8789799

      java.lang.Enum
      Номер в перечислениях отрицательным быть не может.
      java.lang.String
      char неотрицательный.
      java.time.Year
      Ну тут да, если считать какие-нибудь астрономические или геологические периоды, то могут быть проблемки. «Ой».


  1. nickolaym
    02.03.2016 12:30
    #8789693
    +2

    Если элементы набора лежат в интервале [-m,+n], то результаты вычитания будут [-m-n,+m+n].

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


  1. senneco
    02.03.2016 12:44
    #8789719
    +6

    Целая статья на хабре на такую тему. Хабр умирает? Похоже, что да.


    1. Aquahawk
      02.03.2016 13:58
      #8789993
      +1

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


      1. senneco
        02.03.2016 14:19
        #8790059
        +4

        Тогда, по-моему автор должен был хотя бы разобраться, почему это происходит? Рассказать всем причину. Показать пути решения без изобретения велосипеда (например, если известно, что сравнение будет основываться на полях объекта, которые Comparable, то просто возвращать их сравнение через compare). Или собрать сборник подобных случаев-открытий автора. Тогда это будет похоже на статью. А так – чуть сократить и получится лаконичный твит =)

        PS: а если все начнут постить свои небольшие открытие, то хабр превратится непонятно во что.


        1. chabapok
          02.03.2016 15:47
          #8790379
          +1

          О причине рассказано в конце статьи.

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

          Написать про Comparable? Тогда было бы слишком похоже на документацию, был бы смещен акцент, было бы скучно. Вы бы первый раскритиковали.


  1. Artyushov
    02.03.2016 14:12
    #8790041
    +2

    Удивлён, что никто ещё не написал про Integer.compare (Long, Character, Short, etc)


  1. sci_nov
    02.03.2016 17:07
    #8790597
    +2

    Под компаратором обычно подразумевают микросхему с аналоговыми входами, поэтому я думаю, что лучше назвать "… сравнения двух чисел на базе...". А то я было задумался как можно обойтись без вычитания, если простейшая модель работы операционного усилителя и является вычитанием с усилением K(u1 — u2)…
    https://en.wikipedia.org/wiki/Comparator


    1. TachikomaGT
      04.03.2016 13:11
      #8793869
      +3

      Если бы тематикой поста была бы не Java, а схемотехника, вы были бы абсолютно правы.


      1. sci_nov
        04.03.2016 17:09
        #8794257
        -1

        Да, Java не заметил… Но всё равно компараторы не связаны с языками программирования.


        1. TachikomaGT
          04.03.2016 20:28
          #8794503
          +1

          Как интересно) И что им мешает быть связанными?


          1. sci_nov
            05.03.2016 09:30
            #8794855
            -2

            Ну нет такого в программировании. Среди чисто программистской братии многие удивятся, услышав компаратор. Это удел электроники (исторически так вышло). Спор ни о чем. Компаратор как электронное устройство создали намного раньше появления языка Java, поэтому по принципу старшинства (или большинства ассоциаций).
            Тогда уж (раз в Java есть интерфейс Comparator) "… не делайте интерфейса Comparator на базе...".


            1. dougrinch
              05.03.2016 09:50
              #8794865
              +1

              1. Если уж придираться к хрени, то интерфейс Comparator вообще нельзя сделать. Он уже давно готов. "… не делайте реализаций интерфейса Comparator на базе...".

              2. В java-сообществе слово "компаратор" имеет один главный смысл. Данный пост находится в единственном хабе — JAVA. Прошу заметить, даже не в программировании.

              3. Спор ни о чем.
                Спор о том, что вы пришли в одно сообщество со сленгом из другого.


              1. sci_nov
                05.03.2016 10:09
                #8794873

                Да, реализаций интерфейса. Будет лучше.
                Когда я прочитал заголовок статьи среди списка, то на хаб не обратил внимания (где-то там мелко набрано Java).


                1. chabapok
                  05.03.2016 12:02
                  #8794917

                  Можете оценить по шкале от 1 до 100 масштаб трагедии?

                  Вы прочитали "компаратор" и настроились на железные аналоговые компараторы. Дальше идет фраза "на базе вычитания". Вопрос касается этой фразы. Какие ассоциации она у вас вызвала?


                  1. sci_nov
                    05.03.2016 14:45
                    #8795023

                    Трагедии никакой, то есть 1.
                    Ассоциации: а как ещё можно сделать?


  1. TachikomaGT
    04.03.2016 13:07
    #8793865
    +1

    Не совсем про компаратор, но еще интересный нежданчик может вызвать URL.equals()

    Two URL objects are equal if they ...
    «… reference equivalent hosts», а это может быть попыткой обращения к DNS.


    1. grossws
      04.03.2016 14:34
      #8794011

      Там же написано, что операция потенциально блокирующая, и что есть known issue про некорректность этого поведения с virtual hosts.

      Во всяких Set'ах и Map'ах лучше использовать URI (с нормальным человеческим equals) или просто строки.