Блог пользователя SharpBlade

Автор SharpBlade, 12 лет назад, По-русски

Сегодня на контесте(Крок мвту финал) решал задачу Ц. Написал решение, прошло претесты, я был в нем уверен.

После финального тестирования оно упало на 36 тесте с вердиктом wa. Долго не мог понять в чем косяк, потом появился разбор, оказалось, что я так и решал. Никак не мог понять в чем ошибка. В итоге решил в поиске найти, кто тоже упал на этом же тесте. Нашел вот такую попытку — http://mirror.codeforces.com/contest/250/submission/2660008 . Сверил со своим, все так же. Посмотрел историю посылок, увидел, что задача в итоге сдалась. http://mirror.codeforces.com/contest/250/submission/2663690 . Проблема крылась в сравнении Integer (надо было equals вместо =).

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

Вроде бы нашел, почему такое происходит(https://www.owasp.org/index.php/Java_gotchas#Immutable_Objects_.2F_Wrapper_Class_Caching). Но остался вопрос, насколько лишний вызов метода может замедлять программу? И вообще, почему я раньше с этим не сталкивался, всегда писав == вместо equals, вроде бы эта проблема должна часто проявляться.

Спасибо.

p.s. весьма обидно, что так получилось, решил сегодня 3 задачи(одна по глупости слетела из торопливости и еще вот эта, а до финальных тестов был в топ50=( )

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

Проблема тут в том, что метод ArrayList.get() возвращает ссылку на объект типа Integer, так что сравнение через оператор == сравнивает именно ссылки, а не сами объекты. Почему Вы не сталкивались с этим раньше? А потому, что при сравнении вида al.get(i) == 0 в левой части происходит распаковка типа Integer в int.

Насчет замедления программы: в данном случае оно явно пренебрежимо мало в сравнении с замедлением от упаковки-распаковки.

Да, почему Вы не смогли отловить этот баг на простых тестах? А потому, что для целых чисел меньше какой-то небольшой константы Java заранее создает объекты и при попытке упаковать маленькое число просто возвращает уже существующий объект.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    ясно, спасибо

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    верно. я видел в коде какой-то реализации дипазон -128..127 т.е. char сиплюсплюсный.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      В C++ разрешается как наличие, так и отсутствие знака у char, это implementation-defined.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        И вообще у char недетерминированный размер, да-да

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      т.е. char сиплюсплюсный.

      Т.е. java-нский byte — говоря проще ;-)