Классы: реализация класса Poly

От вас требуется реализовать класс Poly, используемый для представления многочленов и операций над ними. Реализация класса Poly должна работать с классом Fraction, поэтому в сдаваемом файле также должна быть реализация класса Fraction, полностью проходящая тестирование по предыдущему листку.

Полное описание класса Poly в отдельном документе.

Требования к сдаваемой программе

Программа должна содержать реализацию класса Fraction, реализацию класса Poly. На проверку сдаётся только реализация этих двух классов.

При проверке к вашей программе добавляется следующий код:

exec(open('input.txt', encoding='utf-8').read())

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

Список задач

A: конструктор __init__ (при этом также должен быть реализован и метод __str__).
B: метод __str__.
C: сложение многочленов и чисел.
D: вычитание многочленов и чисел.
E: умножение многочленов и чисел.
F: быстрое возведение многочлена в степень.
G: вычисление значения многочлена в точке.
H: деление многочленов с остатком.
I: методы __len__, __getitem__, __setitem__.
J: композиция многочленов (метод __call__).

Целью каждой задачи является проверка полноты соответствия указанной части спецификации класса Poly поставленной задаче. Задачи содержат тесты, покрывающие, по возможности, все аспекты спецификации.

Проблемы реализации

Как сделать, чтобы работала операция Fraction + Poly

Для этого необходимо, чтобы метод __add__ для класса Fraction возвращал специальную константу NotImplemented, тогда будет вызван метод __radd__ для класса Poly. Подробности смотрите ниже.

Почему не проходятся специальные тесты на методы __iadd__ и т.д.?

Методы __iadd__ (оператор +=), __isub__ (оператор -=), __imul__ (оператор *=), __ipow__ (оператор **=), __ifloordiv__ (оператор //=), __imod__ (оператор %=) должны модифицировать значение левого операнда (к которому они применяются), а не просто возвращать значение.

Почему в задаче G (вычисление значения многочлена) ответ, близкий к эталонному, не засчитывается?

Вам нужно реализовать вычисление значения многочлена по схеме Горнера, тогда ответы будут совпадать.

Почему в задаче H (деление с остатком) возникает Time Limit?

Скорее всего это происходит из-за того, что функция divmod использует другие функции работы с многочленами: вычитание, умножение и т.д. Из-за многократного вызова других функций время работы многократно растет. Реализуйте функцию divmod так, чтобы она работала только со списками коэффициентов на “низком” уровне, не вызывая реализованные методы выполнения действий над многочленами.

Как вызываются методы __add__ и __radd__?

При реализации операции сложения многие столкнулись с проблемой: как реализовать операцию вида Fraction + Poly? Ведь в этом случае будет вызываться метод __add__ для класса Fraction, а не метод __radd__ для класса Poly.

Чтобы решить эту проблему, нужно понять, в каком порядке вызываются эти методы.

Пусть у нас есть два объекта A и B. Они могут быть объектами как стандартных классов, так и классов, созданных пользователем. Пусть в коде программы используется операция A + B. Что при этом происходит?

Сначала делается попытка вызова A.__add__(B). Если этот метод не определен или этот метод вернет константу NotImplemented, то делается попытка вызова B.__radd__(A). То есть константа NotImplemented как раз нужна для того, чтобы сообщить о том, что объект A не может реализовать операцию + для объекта B.

В нашем случае класс Fraction является более фундаментальным классом, нежели Poly. Класс Fraction вообще ничего не должен знать о существовании класса Poly. При попытке сложения Fraction и Poly класс Fraction должен сообщать, что он не умеет реализовывать такое действие, т.к. ему Poly неизвестен. Наоборот, класс Poly знает о существовании класса Fraction, и должен уметь реализовывать арифметические операции с классом Fraction.

Таким образом, класс Fraction должен содержать реализацию операций сложения для стандартных типов: int, float и самого класса Fraction. Во всех остальных случаях вызов метода __add__ должен возвращать NotImplemented. Итак, правильная реализация метода __add__ для класса Fraction следующая:

class Fraction:
    def __add__(self, other):
        if type(other) == int:
             # Возвращаем результат сложения Fraction + int
             return ...
        elif type(other) == float:
             # Возвращаем результат сложения Fraction + float
             return ...
        elif type(other) == Fraction:
             # Возвращаем результат сложения Fraction + Fraction
             return ...
        else:
             # Возвращаем сообщение о том, что сложение для данного типа не реализовано
             return NotImplemented

Использование профайлера

Для анализа производительности программы и поиска “тонких” мест в реализации можно использовать профайлер.

Самый простой способ запустить профайлер: запуск из командной строки

$ python3 -m cProfile program.py

После завершения работы профайлер выведет на стандартный вывод статистику о числе вызовов функций и времени их исполнения. Для удобства вывод лучше перенаправить в файл.