Разберём задачу, решение которой на Python работает быстрее, чем на PyPy. Задача на длинную арифметику:
Для программистов на C++ или Pascal задача выглядит очень страшно и сложно: надо брать все циклические сдвиги строки, преобразовывать в числа, сравнивать (или сравнивать строки, но не в алфавитном порядке, а как числа). Ужас просто.
Но на Python мы уложимся в 9 строк (можно и меньше, но нельзя, чтобы страдала читаемость кода). Сначала надо понять, что максимальную разность можно получить, если вычитать самое маленькое из возможных чисел из самого большого. Эта мысль сильно ускоряет программу, потому теперь не надо проверять все пары (как это сделано в условии задачи в качестве примера), а можно независимо для строк s и t найти наибольшее и наименьшее числа соответственно.
В худшем случае (с максимальными входными данными) нам надо будет 6000 раз (по 3000 циклических сдвига для каждой строки) перевести в число строку из 3000 символов. Получается примерно 18 млн операций, что довольно много для Python, но давайте попробуем.
Считаем данные и проинициализируем переменные для ответа:
В mx положили 0, потому что во входных данных число строго больше нуля, и при переборе мы точно улучшим ответ. В mn положили число на единицу большее, чем может быть в t (из всех девяток).
Для нахождения максимума среди циклических сдвигов строки s переберём их все (а точнее индексы, с которых начинаются сдвиги). Зная индекс начала сдвига, с помощью слайсов легко строится циклический сдвиг строки. А дальше пара стандартных функций int и max всё сделают за нас:
Для нахождения минимума будем делать всё то же самое, но надо учесть, чтобы число не начиналось с нуля. Формально в предыдущем цикле это надо тоже учитывать, но мы же знаем, что число, начинающееся с нуля, меньше числа с тем же количеством цифр, но начинающегося с любой другой цифры. Поэтому это условие выполнялось автоматически. А для минимума надо проверять символ, с которого начинается циклический сдвиг:
Вот и всё, выводим ответ:
Отправив решение, видим, что оно работает примерно за полсекунды. Да, это сильно дольше, чем решение на C++, но очень быстро для решения на Python. Почему так получилось? Дело в хорошей оптимизации операций с длинной арифметикой внутри языка. И, как я и обещал в самом начале, если это решение отправить с помощью PyPy, мы получаем превышение времени работы, потому что локальное ускорение в циклах, работе с памятью, проигрывает комплексному ускорению на уровне логики работы.
Предыдущий выпуск: Задача 17. Поле чудес
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.