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

Завал java.util.Arrays.sort()
Автор AlexanderBolshakov, 13 лет назад, По-русски

Собственно, данный пост ориентирован больше на новичков (большинство профессионалов с проблемой уже знакомы). Как известно, многие из тех, кто пишут quicksort вручную, попадались на anti-quicksort, и их решения получали TLE или, еще хуже, Stack Overflow. Явакодеров, казалось бы, эта проблема не касается: они пользуются стандартной функцией, которая, по идее, должна быть написана корректно. Не тут-то было... Короче, прилагаю исходник (лицензия GNU GPL 2 with Classpath exception, т.к. основан на исходном коде из OpenJDK). Запускать следует с параметром -Xss64m; сгенерированный массив выведется в файл.


P.S. Прошу прощения за ужасное качество исходника, выкладываю чисто для демонстрации. Более подробную информацию для интересующихся я добавлю потом.

UPD. Исправил ошибку с неправильным измерением времени сортировки.
  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится
Блиииииин, ну зачем ты это написал? Я сам хотел взломать Egor-а и Petr-а
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

    Мне кажется, что вот они-то это знают :).


    UPD. Я написал про то же Михаилу Расиховичу с неявным предложением добавить что-то такое в систесты, а он мое сообщение проигнорировал. Поэтому я написал сюда.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    Ну вот скажи мне, зачем мы это готовили, а?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Если бы Михаил Расихович не имел обыкновения игнорировать то, что ему пишут в ЛС, ваши труды зря бы не пропали... А лично я извиняюсь за свою публикацию. Мне самому хотелость хакнуть кого-то из топа, но я-то синий, и за 1 раунд со своими очками в первый дивизион точно не выйду :(.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится
        > Мне самому хотелость хакнуть кого-то из топа, но я-то синий, и за 1 раунд со своими очками в первый дивизион точно не выйду :(

        И вместо того, чтобы прокачиваться и добиться своей мечты, ты запостил это. Великолепно.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится
          Когда мне наконец-то подвернется шанс кого-то хакнуть, уже выйдет Java 7 с ее dual-pivot quicksort.
          → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Петя, помнится, отлично выучил на своей шкуре аналогичную проблему для C# на онсайте TTB
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Егор, не пали контору, не поднимай топик. Мы готовим месть ситхов день взломов на codeforces.
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        "Поздняк метаться" :-) Уже спалились с потрохами. Уже писалось - в чем проблема и как её можно решать. Кто осведомлен - тот защищен ;-)
        Хотя этих топиков нет в английской версии сайта, так что можете попробовать оттянуться на наших "забугорных" товарищах если сильно охота.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          Думаешь, AntiQuickSort - главная фишка? Поиски смешных вещей продолжаются.

          Жалко, закончились времена компиляции на delphi7. У нее смешная бага в функции eoln, у кого есть, может проверить, что eoln() == false для позиции, кратной 0x80

          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Я смотрю Вас не хило распирает от желания кому то испортить контест из-за огрех авторов библиотек и компиляторов.
            Вот придумал человек как решить задачу.
            Счастье просто переполняет, а тут "бац", и сиди, думай в чем проблема. И из-за времени, потраченного на поиск непонятно от куда берущегося бага человек лишился возможности получить опыт в решении других задач. Печаль, однако.
            → Ответить
            • 13 лет назад, # ^ |
              ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              [trollface.jpg] Egor лишился возможности получить опыт.

              Мы же не на детях это применять будем. Наша задача - tourist, Petr && ACRush 0.

              → Ответить
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                А мне так нужен опыт перед финалом GCJ... Хнык :(
                → Ответить
            • 13 лет назад, # ^ |
              ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              Чуть не забыл добавить. Времени исправить не будет ]:->
              → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Блин... кажется это тот баг, который я когда то словил и так и не понял в чём косяк. Дело было как раз в delphi7.. сгенерированный программой файлик и потом обрабатываемый программой почему-то получал чары с кодами 10 и 13, причём вообще не понятно было как это возможно, если всё в цикле, без исключений.
            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Просто при подготовке одной из олимпиад в одном из тестов один из членов жюри выровнял пробелами по 32 символа файл, который надо было читать посимвольно. Он не хотел того, что получилось в итоге.

              Для авторов, пишущих на делфи (слава Ктулху я уже писал на С++) это стало ужасной проблемой. Потом уже, имея на руках тест, я нашел косяк. Вот он:


              function _Eoln(var t: TTextRec): Boolean;
asm
// -> EAX Pointer to text record
// <- AL  Boolean result
        CMP     [EAX].TTextRec.Mode,fmInput
        JNE     @@readChar
        MOV     EDX,[EAX].TTextRec.BufPos
        CMP     EDX,[EAX].TTextRec.BufEnd
        JAE     @@readChar
        ADD     EDX,[EAX].TTextRec.BufPtr
        TEST    [EAX].TTextRec.Flags,tfCRLF
[...]
@@readChar:
        PUSH    EAX
        CALL    _ReadChar
        POP     EDX
        CMP     AH,cEOF
        JE      @@eof
        DEC     [EDX].TTextRec.BufPos
        XOR     ECX,ECX
        XCHG    ECX,EAX
        TEST    [EDX].TTextRec.Mode,tfCRLF
        JNE     @@testLF
[...]
end;

              Размер буфера 0x80. Можно заметить, что в случае отсутствия в буфере символа проверяется поле Mode вместо Flags, это дает всегда ответ false (там магия).

              → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Да, я помню, как на одном из давних чемпионатов СПбГУ команда финалистов три часа на этот баг убила. Причём тесты были такие не специально; жюри, кажется, узнало об этом баге тогда же. Просто это неизбежно проявляется, когда в файле много строк разной длины.

            Мораль была, что можно использовать seekeoln.

            Но вот во FreePascal-е функции seekX ведут себя не так, как в Delphi (причём документация об этом молчит): проверяют, что достигнут конец X, а потом, собаки, возвращают курсор обратно!
            → Ответить