Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 
Вернуться
Тема: Если вы решаете задачу 1780 на Python и получаете Runtime Error на 4-м тесте, то вам нужно всего лишь...
1
  1  Хворых Павел, 28 ноября 2022 г. 5:27:26
      Это не самодурство разработчиков CPython, решение было продиктовано компаниями, использующими CPython. Ведь этот явный breaking change еще и бэкпортировали на все поддерживаемые версии CPython, чтобы компании могли обновить патч-версию, не боясь поломать что-то еще.

"Более эффективные" не значит "эффективные": наличие более эффективных алгоритмов не повлияло бы на решение о введении ограничения, ведь они по прежнему медленные. Разве что могло немного повысить планку. Речи об отмене ограничения не идёт и идти не может.

Числа в памяти хранятся в двоичном виде, его можно получить и без дампа: преобразования в двоичные системы счисления выполняются за линейное время, поэтому их не ограничили. В частности, ограничение не действует на hex(n) и int(s, 16).
  2  Лукьянов Иван, 27 ноября 2022 г. 21:29:08
      Спасибо за разъяснение.

Насчёт «практического» сценария пассаж удивительный. Как в анекдоте: явление есть, а слова нет. Работа с большими числами не воспрещается, а посмотреть на них (по умолчанию) нельзя, разве только сдампить из памяти. Мейнтейнеров в обсуждениях справедливо пропесочили: дескать, им лучше сломать старый код, чем реализовать более эффективные алгоритмы либо напомнить бэкендерам проверять данные перед обработкой. Споры безрезультатные, а позиция каждой из сторон принципиальная.

А ведь любая версия питона, будь то 3.11 или какая-то ещё, очень долго будет оставаться установленной на многих компьютерах... Я не верю, что новое ограничение будет снято. Тем больше поводов отказаться от CPython.
  3  Хворых Павел, 27 ноября 2022 г. 15:32:33
      Вы что-то напутали. В CPython реализован алгоритм Карацубы, так что умножение выполняется относительно быстро. И никто вам не запрещает перемножать сколь угодно большие числа. Речь в этой уязвимости идёт только о преобразовании чисел в строку и из строки: они в CPython выполняются за квадратичное время. Сложно представить практический сценарий, когда требуется вывести или распарсить числа длиной в тысячи знаков, поэтому улучшением не занимались. А вот злоупотребления видимо были, поэтому и решили добавить ограничение.

В связи с этой ситуацией активизировалась работа над более эффективными алгоритмами. В частности, в CPython 3.12 уже реализован субквадратичный алгоритм для таких преобразований. Посмотрим, приведет ли это к повышению лимита. В PyPy, кстати, тоже квадратичный алгоритм использовался, они уже скопипастили себе более эффективный из CPython 3.12.
  4  Лукьянов Иван, 27 ноября 2022 г. 12:29:33
      Упрямая позиция разработчиков Python: с длинными числами пользователь работать не должен. Если получилось число длиннее 10 тысяч бит, то это аж целая уязвимость CVE-2020-10735, потому что в CPython умножение длинных чисел работает за квадратичное время. Несмотря на то что в других библиотеках реализовано эффективное умножение. Просто блестяще.

Пора отказываться от CPython и переходить на PyPy, там такой ерунды (пока) нет.
  5  Меньшиков Фёдор Владимирович, 21 ноября 2022 г. 13:50:50
      these APIs were added in security patch releases in versions before 3.11
  6  Тер-Саркисов Богдан Олегович, 06 ноября 2022 г. 20:23:56
      Ничоси. А то я думал, почему даже обычный алгоритм отваливается.
  7  Хворых Павел, 06 ноября 2022 г. 19:49:24
      ... переключиться на PyPy. А если серьезно, то в версии CPython 3.11 была запрещена печать слишком длинных чисел. Это поведение можно отключить следующим кодом:
import sys
sys.set_int_max_str_digits(0)
1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru