Это вторая часть серии Видимое и Незримое. В этой части я реализую геометрическую серию и подробно объясняю, как различные решения, принятые во время реализации, влияют на видимое и невидимое.

Простое расширение геометрического ряда выглядит так.

Я работаю над частным случаем геометрической серии, где 𝑎 = 1 и | 𝑟 | ‹1, r представлено как x.

Серия Тейлора - это бесконечная серия, но я не могу запускать цикл вечно, поэтому мне нужно найти условие завершения. Поскольку | 𝑥 | ‹1, член приближается к 0 с увеличением мощности. Я буду использовать это как условие завершения. Таким образом, наивная реализация найдет значение каждого члена до тех пор, пока оно не достигнет нуля, добавит их к сумме и в конце вернет сумму.

Увиденное сделано. У меня есть функция, отвечающая требованиям, она дает значение геометрического ряда по формуле. Ранее я говорил обо всех невидимых аспектах программирования и о том, как они улучшают его. Что насчет них? Дает ли наивная реализация правильный результат для всех значений 𝑥? Мне нужно протестировать его для разных значений 𝑥. Тестирование вручную будет медленным, и я не смогу охватить все случаи. Мне нужна функция, которая проверяет gpsum_naive() для нескольких тестовых случаев.

Привет! Я определил общую функцию тестирования theSeenAndTheUnseenTest(), которую я буду использовать для тестирования gpsum_naive().

Два графика для gpsum_naive() и gp() одинаковы, но график ошибок показывает, что существует ошибка 1𝑒-13% между отдельными тестовыми примерами.

Теперь у меня есть наивная реализация, которая отлично работает для разных тестовых случаев. Но как насчет времени его вычисления? Время вычисления одинаково для всех значений 𝑥? Это другое? Как его найти?
Библиотеку Python timeit можно использовать для измерения времени небольших фрагментов кода Python, как показано ниже.

Выполнение этого для разных значений 𝑥 займет много времени. Как и в случае с функцией тестирования, я могу создать общую функцию, которая будет отображать время выполнения для различных значений 𝑥. find_time(function, testcase) будет использовать timeit.Timer() для измерения времени function для разных значений 𝑥 в testcase и возврата их в виде списка. plot_time(testcase, plotNaive, **kwargs) отобразит список вместе с ускорением по сравнению с наивной реализацией. Затем я позвоню plot_time(testcase, plotNaive, **kwargs) на gpsum_naive(), чтобы узнать среднее время выполнения вместе со временем выполнения для отдельных тестовых случаев.

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

По мере увеличения числа термина значение термина уменьшается. Скорость, с которой это происходит, зависит от 𝑥. Для более низких значений 𝑥 условия выпадают намного быстрее. Вот почему время и количество итераций увеличиваются с увеличением значения x.

Зачем я все это сделал? Наивная реализация сделана и дает правильный результат, но этого недостаточно. Ранее я говорил о производительности как о невидимом аспекте хорошего программного обеспечения. Хорошее программное обеспечение дает нужный результат за минимальное время. Чтобы оптимизировать функцию, мне нужно понимать, какие факторы влияют на ее производительность. С помощью визуализации я понял, чем отличается время выполнения для разных значений 𝑥 и какова связь между ними. Итак, теперь я могу придумать один способ повысить производительность - это уменьшить количество итераций. Я могу придумать другие способы оптимизации, наблюдая за наивной реализацией. Поскольку я вычисляю мощность на каждой итерации, я мог бы найти более быстрый способ сделать это. Также обратите внимание на то, как я нахожу каждый термин. Я непосредственно нахожу xⁿ, тогда как само определение говорит, что каждый термин является продуктом предыдущего термина и общего отношения. Это будет мой третий вариант оптимизации. В конце я объединю эти 3 случая и посмотрю, какое влияние я получу на скорость и точность. На диаграмме ниже показаны различные оптимизации, которые я буду выполнять наивно.

Дело 1

Во-первых, давайте посмотрим на количество итераций, предпринятых наивной реализацией для разных значений 𝑥. Ниже приводится общая функция, которая будет отображать количество итераций для любой переданной ей функции.

Количество итераций увеличивается до 7074 при = 0,9. Поскольку 𝑥 имеет значение с плавающей запятой, xⁿ также будет иметь значение с плавающей запятой, а python имеет 53 бита точности для числа с плавающей запятой, поэтому функция продолжает повторяться до последнего бита. Этот уровень точности дает ошибку 2,153e-14%. Моя цель - получить ошибку менее 0,01, что полностью удовлетворяет, но, возможно, я мог бы обменять точность на скорость, достаточную для того, чтобы ошибка оставалась ниже 0,01%.

gpsum_iterations(), gpsum_naive() и gp() выглядят одинаково. Но посмотрите на график ошибок, насколько они разные. Я снова вызываю тестовую функцию на gpsum_naive(), чтобы вы могли увидеть сходство и различие между двумя функциями. Без графика ошибок я бы просто знал, что средняя ошибка составляет

Теперь давайте посмотрим на ускорение gpsum_iterations ().

Это в 100 раз быстрее

Обратите внимание, что максимальное время, затраченное на gpsum_iterations(), по-прежнему меньше минимального времени, затрачиваемого на gpsum_naive(). Я получил это ускорение за счет уменьшения количества итераций. Чтобы сравнить количество итераций gpsum_naive() и gpsum_iterations(), я напишу функцию, которая строит их для разных значений 𝑥. Поскольку я бы сравнивал итерации для других оптимизаций в экспоненциальной или синусоидальной, косинусной серии, я сделаю эту функцию универсальной.

Посмотрите, как выглядят графики времени выполнения и итераций. Время выполнения gpsum_naive() во многом зависит от количества итераций. Ограничив количество итераций ровно настолько, чтобы достичь желаемой точности, я получил ускорение в 100 раз. В gpsum_iterations() я немного теряю точность, но получаю ускорение в 100 раз.

Случай 2

Я заменил одну встроенную функцию другой, чтобы проверить, как она влияет на производительность, но перед этим давайте проверим сходство или различие между ошибками двух функций. Я снова вызываю тестовую функцию gpsum_naive().

Визуализируя данные, я мог понять, что ошибка для двух встроенных функций одинакова. Чтобы увидеть, как это влияет на производительность, я позвоню plot_time() на gpsum_power().

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

Случай 3

Вместо того, чтобы находить мощность на каждой итерации, я умножу a на предыдущий член.

В gpsum_cal() я умножаю a на каждой итерации, из-за чего значение члена никогда не падает до нуля, а цикл выполняется бесконечно. Когда я написал gpsum_cal(), я ожидал, что он будет работать для всего, как и для предыдущих случаев. Логически это правильно, и создается впечатление, что он будет работать быстрее и давать такой же результат. Без тестирования я бы не узнал об этой ошибке. Это один из важных примеров того, почему важно тестирование.

Чтобы точно показать, что происходит с терминами и результатом, я запущу цикл до 7100 итераций и распечатаю результат.

По мере увеличения итераций изменение значения термов почти равно нулю, как и изменение ′ 𝑠 ′. Условием завершения gpsum_cal() является 𝑡! = 0, но к тому времени, когда оно достигает нуля, значение члена становится настолько маленьким, что не имеет никакого значения для результата. Я буду использовать это как условие завершения для gpsum_calculation. Я остановлюсь, когда не будет изменений в значении термина.

Наряду с изменением расчета мощности происходит изменение условия завершения. Мне нужно проверить, дают ли эти функции правильный результат, я вызову функцию тестирования на gpsum_calculation().

С новым условием завершения и изменением реализации я все еще могу поддерживать ошибку ниже 0,01%. Используя plot_time(), я проверю gpsum_calculation() на ускорение.

Среднее ускорение составляет 2 ×

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

Случай 4

Я заменю условие завершения на условие завершения gpsum_iterations() и добавлю изменения, внесенные в оптимизацию gpsum_calculation().

После внесения этих двух изменений мне нужно проверить эту функцию на правильность.

Ага! Условие gpsum_iterations() удерживает ошибку ниже 0,01. Теперь посмотрим на производительность gpsum_allopts.

Ускорение 200 ×

Благодаря всем этим оптимизациям максимальное время вычислений снизилось с 0,05𝑠 до примерно 0,1𝑚𝑠.

Используя plot_time(), я построю график производительности всех функций, чтобы суммировать все, что было сделано до сих пор.

Это время выполнения всех функций вместе взятых. График времени выполнения превратился в линейный график из экспоненциального графика. Посмотрите на ускорение gpsum_allopts на втором графике. Визуализация помогает понять влияние изменений, внесенных в функцию, на ускорение и время выполнения. Визуализация также упрощает сравнение, а не просто чтение чисел.

Я мог бы добиться ускорения 200x для простой реализации геометрических рядов, обращая внимание на невидимые аспекты программирования. Наблюдая за невидимыми аспектами, я мог подвергнуть сомнению свой дизайн реализации и придумать различные идеи, чтобы оптимизировать его и сделать видимое лучше. Функция тестирования помогла мне понять, что случай 3. Оптимизация вычислений работала нормально для меньших значений x, но для более высоких значений x превратилась в бесконечный цикл. Логически функция казалась правильной, но только после тестирования я понял, что с ней не так. Я также написал еще несколько общих функций для поиска времени выполнения и итераций, что способствовало аспекту ремонтопригодности программирования.

В части 3 я использую пример экспоненциальной функции и объясняю, как разные варианты реализации влияют на видимое и невидимое.