Упражнение 19: Улучшение производительности

Оригинал: Exercise 19: Improving Performance

Переводчик: Феликс Ло

Лицензия: CC BY-NC-SA 4.0

Гордо использует Google Translate

Это почти полностью видео-упражнение, где я демонстрирую, как можно улучшить производительность вашего кода до сих пор, но сначала вы должны попробовать это самостоятельно. Вы уже проанализировали скорость выполнения кода в упражнении 18, так что теперь самое время реализовать некоторые ваши идеи. При исправлении простых проблем производительности я предоставлю вам простой список мест для поиска и модификации:

• Вложенные циклы могут привести к избыточному вычислению. Бульбашка — это классический пример, поэтому именно так я его преподаю. Как только вы поймёте, насколько хуже работает сортировка пузырьком по сравнению с другими методами, вы начнёте понимать, что это распространённый шаблон, который следует избегать.+ Вычисление чего-то, что не меняется в процессе выполнения программы, или повторное вычисление одного и того же значения несколько раз во время изменения данных. Хорошим примером является функция count() в модуле sorted.py и других структурах данных. Вы можете отслеживать размер структуры данных внутри функции. При каждом добавлении увеличивайте его значение, а при каждом удалении уменьшайте. Вам не нужно каждый раз проходить через весь список. Вы также можете использовать этот заранее рассчитанный счётчик для улучшения логики других функций, проверяя условие count == 0.+ Использование неправильной структуры данных. В словаре я использовал DoubleLinkedList, чтобы продемонстрировать эту проблему. Словари требуют случайного доступа к элементам, как минимум к элементам списка бакетов. Использование DoubleLinkedList означает, что вам придётся пройтись по всем элементам до n-го, когда вы хотите получить доступ к n-му элементу. Замена его Python списком значительно повысит производительность. Это упражнение заключается в том, чтобы использовать существующий код для создания структуры данных из более простых структур данных, но это не обязательно будет лучшей реализацией Python словаря (она уже есть).

• Использование неправильного алгоритма для работы со структурой данных. Сортировка пузырьком — явно плохой алгоритм (не используйте его больше!), но помните, что слияние и быстрая сортировка могут быть лучше или хуже в зависимости от структуры данных. Слияние хорошо работает с этими типами связанных структур данных, но плохо работает с массивами типа Python list. Быстрая сортировка лучше всего работает с list, но плохо работает с связанными структурами данных.+ Неправильное место для оптимизации часто выполняемых операций. В DoubleLinkedList вы часто начинаете поиск значения с начала бакета. В текущем коде эти бакеты просто добавляются, когда они приходят, возможно, случайным образом, возможно, нет. Если вы примете правило, чтобы сортировать эти списки при вставке, то поиск элемента станет легче и быстрее. Когда значение бакета становится больше искомого значения, вы можете прекратить поиск, зная, что список отсортирован. Это делает вставку медленнее, но почти все остальные операции становятся быстрее, поэтому выберите правильный дизайн для этого упражнения. Если вам требуется большое количество вставок, это не очень умно. Но если ваш анализ показывает, что вам требуется мало вставок, но много запросов, это хороший способ ускорить работу.+ Ручное написание кода вместо использования существующего кода. Мы выполняем упражнения для изучения структур данных, но в реальном мире вы бы этого не делали. В Python уже есть хорошие структуры данных, которые встроены в язык и оптимизированы. Вы должны использовать эти структуры данных первым делом; если анализ производительности покажет, что ваши собственные структуры данных будут работать быстрее, тогда можно написать свои структуры данных. Даже в этом случае вам следует найти существующую структуру данных, которую кто-то уже протестировал и проверил, а не писать её самостоятельно. В рамках этого упражнения напишите несколько тестов, чтобы сравнить ваш Dictionary с встроенными типами данных Python, такими как list, и посмотреть, насколько более эффективными могут быть ваши структуры данных.+ Избегайте использования рекурсии в языках, которыми вы не очень хорошо владеете. Проще говоря, код merge_sort может сломаться, если ему передать список длиннее, чем размер стека вызовов в Python позволяет. Попробуйте передать ему сумасшедший список, такой как список из 3000 элементов, затем медленно уменьшайте количество элементов до тех пор, пока не найдёте значение, которое приведёт к исчерпанию стека вызовов Python. Python не выполняет некоторые оптимизации для рекурсии, поэтому без специальных мер рекурсия может провалиться таким образом. В данном случае лучше переписать merge_sort, используя цикл (хотя это будет намного труднее).Примечание: В исходном тексте использовались английские слова "madness" и "fails in such a way", которые были переведены как "безумие" и "не работает таким образом". Однако, для более естественного звучания текста, было принято решение заменить эти выражения на эквивалентные русскоязычные конструкции. При анализе упражнения 18 вы должны были получить некоторые важные результаты. Теперь ваша задача — попробовать реализовать эти результаты и повысить производительность кода.

Часто задаваемые вопросы

Попробуйте использовать ваши аналитические навыки и описанные рекомендательные улучшения, чтобы систематически повысить производительность кода. "Систематически" означает использование методологии шаг за шагом с контролем, используя данные для подтверждения того, что вы действительно улучшили что-то. Вот процесс, который вам следует придерживаться в этом упражнении:+ Выберите свой первый самый маленький и медленный кусок кода и убедитесь, что у вас есть тест, который показывает, насколько он медленный. Убедитесь, что у вас есть серия метрик, которая позволяет понять его скорость. Если возможно, отобразите это графически.

• Попробуйте увеличить скорость, затем запустите тест снова. Продолжайте пытаться выжать максимум из этого кода.
• Если вы меняете код и ничего не улучшаете, то вы можете быть уверены, что сделали что-то неправильно, и откатите изменения и попробуете другой подход. Это важно, потому что вы проверяете свои гипотезы, поэтому если вы оставите бесполезные изменения в коде, они могут повлиять на производительность других функций, которые вы могли бы исправить. Откатите изменения и попробуйте другой подход или перейдите к другому участку кода.
• Повторите измерение других самых маленьких и медленных фрагментов кода, чтобы узнать, изменились ли они. Ваши исправления могут повлиять на другие части кода, так что повторно подтвердите то, во что вы верили.
• Как только вы завершите все подтвержденные изменения, выполните измерения заново и выберите новый фрагмент кода для улучшения.
• Начните с первого шага и продолжайте тестирование (они должны быть автоматическими тестами), потому что вам нужно избежать регрессий.Если вы заметили, что изменения одной функции замедляют другие функции, тогда либо исправьте это, либо просто откатите изменения и попробуйте новые подходы.## Дополнительные материалы для изучения

Вы должны изучить оригинальное письмо о TimSort и ошибку, обнаруженную исследователями проекта EU FP7 ENVISAGE в 2015 году. Оригинальное письмо было отправлено в 2002 году, а реализация последовала за ним. Эта ошибка была найдена спустя 13 лет. При создании своих алгоритмических идей помните об этом. Даже верхи команд развития крупных проектов могут оставлять баги в своих алгоритмах, которые остаются невидимыми долгое время. Второй пример — это проект OpenSSL, где баги существуют десятилетиями, потому что все полагаются на "профессиональных криптографов", создавших код. Оказывается, даже так называемые профессиональные криптографы могут писать плохой код. Для того чтобы сделать новый алгоритм правильным, требуются специальные навыки, и я считаю, что использование средств для доказательства теорем может помочь в проверке корректности. Без такого фона создание новых алгоритмов и структур данных может быть опасным. Это относится как к криптографическим алгоритмам, так и к криптографическим сетевым протоколам. Однако если вы освоили навык реализации, то реализация уже проверенных алгоритмов других людей вполне нормальна и является хорошей практикой.Но не пытайтесь самостоятельно создавать грубые структуры данных без какой-либо помощи. Реализация уже проверенных алгоритмов других людей совершенно нормальна и является хорошей практикой. Но не пытайтесь самостоятельно создавать грубые структуры данных без какой-либо помощи.