Виталий Аксенов
Есть прок от олимпиадных программистов!
Внезапно решил вчера (06.09.2024 г.) почитать рекомендации в Гугл Хроме на телефоне – было время. Открываю, а там предлагают прочитать про историю сортировки в стандартной библиотеке Java (https://habr.com/ru/companies/sberbank/articles/841342/). Думаю, почему нет – вдруг что-то новое узнаю. Написал её Владимир Ярославский, собственно, работавший над ней. Это не перевод, как подумали некоторые. Кстати, у Владимира был доклад на эту тему на конференции Joker осенью 2023 г. (https://www.youtube.com/watch?v=bzAHm79aHbA).
Я читаю: прикольно и интересно. И вдруг читаю следующий текст: «Однажды мне написал программист и пожаловался, что на соревнованиях по спортивному программированию его команда проиграла. В спортивном программировании программа должна работать не только правильно, но и как можно быстрее. Изюминка того соревнования была в том, что тестовые данные для проверки решений задач участниками могли давать и жюри, и соперники. Соперники проигравшей команды знали версию JDK и что там используется Quicksort, а для любого Quicksort можно подобрать данные так, что алгоритм сортировки покажет квадратичное время. И в результате команда написавшего мне человека проиграла. Я пообещал исправить это. Так появился Heapsort, который, как и Quicksort, он работает за O(n*ln(n)) и не требует дополнительной памяти».
И тут я вспоминаю, что был при этом! Правда, уже не очень помню детали. В 2012 г. проходил раунд 136 на Codeforces (https://codeforces.com/contest/220), и у Нияза Нигматуллина простое решение по задаче A не прошло тесты (https://codeforces.com/contest/220/submission/2072333). Оно превысило заданное время работы. Нияз стал разбираться, и оказалось, что сортировка в Java работала медленнее, чем ожидалось. После этого Нияз с Мишей Кевером написали письмо в Oracle и попросили, чтобы это исправили. И, действительно они в коллаборации с Ниязом провели корректировку сортировки в Java, и теперь об этом написали историю со стороны, другой относительно той, на которой находился я.
Все-таки, есть прок от олимпиадных программистов!
А тем временем Нияз и Михаил на чемпионатах мира по программированию по версии ICPC побеждали дважды – в 2012 и 2013 гг., и поэтому им больше нельзя выступать на этих соревнованиях.
07.09.2024 г.