Для группы
757 Python Meetup кто-то предложил посмотреть какой-то код Python, который у них был медленный. В коде реализована вариация системы
рейтингов шахмат Эло . Он применял рейтинги к другим видам спорта и использовал набранные очки, а также базовые победы / поражения / ничьи для определения рейтинга спортивных команд. Очень умные вещи.
Но.
Это было описано как ужасно медленный. Поскольку в нем было всего 400 строк кода, это была отличная тема для обзора на встрече Python. Я мог бы показать некоторые твики и советы по производительности.
Гипотетический шаг 1. Профиль.
Первой моей мыслью было запустить профилировщик и посмотреть, что всплыло в качестве возможной основной причины замедления.
Как правило, существует три вида проблем с производительностью.
- Неверная структура данных . Или неверный алгоритм. (Это просто противоположные стороны одной медали.) Это обычно приводит к драматическим, потрясающим улучшениям.
- Слабые практики программирования . Этот вид тонкой настройки дает незначительные улучшения. В некоторых случаях никаких измеримых изменений вообще нет.
- Ошибок . Каждый раз, когда меня просят улучшить «рабочий» код, я обнаруживаю, что в нем есть ошибки. Каждый раз. Это может усугубить проблемы с производительностью. Интересно, что большинство из них становятся очевидными во время первоначального опроса: т.е. просто читая код, чтобы увидеть, как он работает. Попытка создать модульные тесты для целей рефакторинга часто выявляет дополнительные ошибки.
Я не знал, что я собираюсь увидеть в этой программе из 400 строк.
Гипотетически, профилирование поможет показать, какие у нас проблемы.
Конечно, перед профилированием нам нужно выполнить чертову штуку. К счастью, они предоставили некоторые типичные входные файлы. Например, результаты школьного футбольного сезона 1979 года. 159 строк терпеливо собранных команд и очков.
Когда мы попытались запустить его с помощью профилировщика, мы обнаружили, что у нас есть ошибка. Отслеживание ошибки выявило и существенную проблему с производительностью.
Это проявилось в ряде действительно плохих ошибок проектирования. Плюс, это представлено как фактическая, серьезная ошибка.
Для составления командного рейтинга в программе был составлен список команд.
Я повторю это для людей, которые занимаются скиммингом.
Для составления командного рейтинга в программе был составлен список команд.
Не точное отображение названия команды в деталях команды. Но простой
список . Поиск команды в списке означал итерацию по списку в поисках подходящей команды. В самом деле.
for t in team_list:
if t['name'] == target_name:
process( t )
Такого рода вещи повторялись в нескольких местах.
И в одном из этих повторов была ошибка.
То, что мы имеем здесь, это «неправильная структура данных». Замена списка продиктованным будет иметь потрясающее влияние на производительность.
Ошибка, BTW, была циклом поиска, который требовал добавления недостающих команд. Он пытался использовать структуру
for-else . Это был предполагаемый код (не фактический код).
for t in team_list:
if t['name'] == target_name:
return
else:
t['name']= init_new_team(target_name)
Это первый класс Python.
Еще статья на
для заявления является реальной особенностью языка. Тем не менее, это достаточно неясно, что легко ошибиться.
Тем не менее, это также уникально для Python, и такие вещи могут привести к путанице. Я препятствую его использованию.
Мы делаем TDRE на небольшом кусочке развлекательного программирования. Это означает, что нам необходимо изготовить модульные тесты для кода, который должен работать. Некоторые люди любят называть это «пробным тестированием» (фраза, которая противоречива и, следовательно, бессмысленна). Мы «исследуем». Мы не «тестируем».
После исправления основной ошибки мы можем запустить пример данных через приложение, чтобы получить результаты «большой картины». Мы можем извлечь биты из примеров данных и выполнять различные функции изолированно, чтобы определить, что они на самом деле делают сейчас, включая ошибки.
Поскольку это так просто — и мы собираемся рассмотреть его во время двухчасовой встречи — и ничего не происходит, мы можем обойтись несколькими простыми юнит-тестами. Мы запустим чертову штуку один раз, чтобы создать ожидаемый результат. Мы сохраняем вывод и используем этот единственный выходной журнал в качестве ожидаемых результатов от каждого шага рефакторинга.
Более сложные приложения требуют больше юнит-тестов. Для оплачиваемой работы TDRE в прошлом году мне пришлось создать 122 модульных теста, чтобы успешно провести рефакторинг программы, содержащей более 6000 строк кода. Прошло несколько недель.
Реальный шаг 1: исправить структуру данных
Перед профилированием (но после запуска для захвата некоторого вывода) мы должны исправить основную структуру данных. Повторное сканирование списка никогда не будет работать хорошо.
Весь смысл изучения «структур данных» состоит в том, чтобы предотвратить (или оптимизировать) поиск.
В этом случае мы можем предотвратить линейный поиск по списку, используя словарь. Это, очевидно, работа первая.
Это было повсеместное переписывание. По сути, все в этой маленькой программе содержало тупой цикл поиска команды в списке. Сам алгоритм Эло, который уже равен
O (
n
2 ), сокращается с помощью линейного поиска команды противника еще четыре раза, что делает его
равным O (
n
3 ).
Цикломатическая сложность
Одной из больших «проблем» является использование
операторов if в алгоритме оценки.
Если оператор создает
цикломатическую сложность и может привести к проблемам производительности. Как правило,
если заявления следует избегать.
Этот алгоритм применяет некоторые коэффициенты нормализации для согласования оценки с числами побед / поражений в различных видах спорта. Баскетбол, в частности, предполагает в целом высокие результаты. Так как есть 2-х и 3-х точечные возможности для подсчета очков, фактор используется для нормализации очков в «цели». У футбола, также, есть многочисленные возможности выигрыша со значениями 1, 2, 3 и 6 очков; баллы здесь также нормализованы.
Эта нормализация была сделана с помощью
оператора if, который был оценен глубоко внутри алгоритма Эло. Неоднократно. Оценивается.
Две функции, которые обрабатывали нормализации, а также факторы нормализации, являются идеальными кандидатами на проектирование ОО. Здесь есть четкая иерархия классов. Суперкласс обрабатывает большинство видов спорта, а два полиморфных подкласса отвечают за нормализацию футбола и баскетбола.
Оператор
if теперь «выталкивается» в самое начало программы, где создается экземпляр объекта спортивной нормализации. Методы этого объекта затем используются алгоритмом Эло для нормализации оценок.
Обледенение на торте
После того, как мы исправили ошибку и заменили список на dict, все остальное просто обледенение.
Некоторые другие изменения ОО.
- Информация «Команда» не должна быть простым анонимным словарем. Это должно быть правильное определение класса с надлежащими атрибутами. Существует не так много методов, поэтому их легко создать.
- Информация об игре читается csv.DictReader . Однако это не должно оставаться простым анонимным диктом. Как и в Team, простой класс может быть создан для обработки Game.
- Общая структура приложения должна быть разбита на два раздела. Интерфейс командной строки анализирует параметры, открывает файлы и обычно все настраивает. Фактический алгоритм ранжирования должен представлять собой функцию, которой для нормализации предоставляется открытый объектоподобный объект плюс объект Sport. Это позволяет повторно использовать алгоритм ранжирования в других контекстах, кроме командной строки (то есть веб-службы).
Более тонким аспектом разработки ОО является вопрос «изменчивости». Команда в этом приложении немного больше, чем имя. Есть также множество «состояний» значений, которые являются частью алгоритма Эло. Игра, аналогично, представляет собой неизменную пару команд и очков. Тем не менее, он имеет некоторые изменяемые значения, которые являются частью алгоритма Эло.
На самом деле, у нас есть неизменные объекты Team и GameHistory, а также несколько значений, которые используются как часть вычисления Elo. Я большой поклонник отделения этих изменчивых и неизменных объектов друг от друга.
Я подозреваю, что алгоритму Эло на самом деле не
нужно обновлять «состояние» объекта. Я подозреваю, что он фактически создает (и отбрасывает) ряд неизменяемых объектов ранжирования кандидатов. Итерация, которая приводит к сходимости, может быть скорее вопросом создания объекта, чем обновления. Я не делал этого изменения, так как это требовало реальной работы, и у нас не было времени.
Чем больше раз я делаю TDRE для повышения производительности, тем больше понимаю, что все дело в ошибках и структурах данных.
Это развлекательное приложение заняло 45-60 секунд, чтобы обработать годовой рекорд игр для данной лиги. Теперь для выполнения такого же объема работы требуется менее 0,2 секунды. Два теста, включающие полный прогон из 159 записей, выполняются за 0,411 секунды. Это 1/100 раз просто от переключения структур данных.
Идея «настройки» рабочей программы для повышения производительности, как правило, вводит в заблуждение. Это может случиться, но воздействие в лучшем случае ничтожно мало.
Вот контрольный список для получения улучшений 100: 1.
- Удалить поиски.
- Удалить глубоко вложенные операторы if .
Как правило, уменьшить цикломатическую сложность.