Небольшое руководство для людей, которые хотят более быстрый код, но не хотят углубляться в оптимизацию низкого уровня.
Я часто вижу, что люди недостаточно используют стандартную библиотеку Python. Хотя это излишне раздувает код и затрудняет обслуживание, это также может привести к неэффективному и медленному коду. Поэтому в этой статье я хочу затронуть последний пункт и показать вам несколько вещей, которые позволяют писать более быстрый код.
После очень простых оптимизаций, которые я собираюсь показать вам, программы могут работать в тысячи раз быстрее при почти нулевых усилиях с вашей стороны. Это может быть разница между ожиданием завершения программы в течение минуты или ожиданием в течение всего дня.
Поскольку я математик, мне нравится решать задачи высокого уровня. Я не хочу переключаться между битами и получать из своего кода последний процент производительности. Я восхищаюсь инженерами, которые могут это делать, и рад, что они дают нам так много отличных и эффективных программ, но мне самому это не нравится.
Однако иногда мне приходится что-то кодировать самому. Такое случается. И когда это происходит, я использую несколько очень простых приемов, чтобы ускорить процесс, не заходя слишком глубоко под капот.
Вот мой вам совет.
1. Используйте наборы
Наборы полезны для множества задач. С высокого уровня вы можете видеть наборы как списки, которые не допускают повторяющихся значений. Пишу
l = [1, 1, 2, 3, 3, 3] s = set(l)
оставит вас с набором s = {1, 2, 3}. Вы можете объединить несколько наборов в новые наборы, используя объединения, пересечения, дополнения, симметричные различия. Вы можете проверить, входит ли один набор в другой. Возможности безграничны!
Но я действительно хочу вам сказать следующее: используйте наборы всякий раз, когда вы хотите проверить группу элементов, содержатся ли они в списке - извините, установлен!
Представьте, что мы получили кучу случайных чисел меньше 50 000, и нам нужно проверить, являются ли они простыми числами. Более того, мы хотим проверить, какова вероятность выпадения простого числа. Итак, давайте сначала определим простые числа до 50 000.
def is_prime(n):
for i in range(2, n):
if n%i == 0:
return False
return True
primes = [n for n in range(2, 50000) if is_prime(n)]
Теперь мы можем приступить к вычислению вероятности с помощью моделирования Монте-Карло. Это делается путем деления количества выпавших простых чисел на общее количество выпавших чисел.
n_numbers = 10000
counter = 0
some_numbers_to_test = np.random.randint(0, 50000, n_numbers)
for number in some_numbers_to_test:
if number in primes:
counter += 1
probability = counter / n_numbers
print(probability)
Этот код выполняется примерно 6 секунд на моем компьютере, но мы работаем с очень небольшим числом здесь, поэтому на данном этапе этого не должно происходить! Я бы ожидал миллисекунды, может быть, даже наносекунды.
Эта проблема
Как вы уже догадались, проблема в том, что primes - это список. Тестирование, если элемент содержится в списке, занимает в среднем линейное время по длине списка, так как каждый элемент должен проверяться один за другим! Это означает следующее: если у вас есть список из 10 000 элементов, и поиск элемента занимает 1 секунду, то при поиске этого элемента в списке, содержащем 1 000 000 элементов, потребуется 100 секунд.
Конечно, нам может повезти, и элемент, который мы ищем, находится в начале, значит, поиск выполняется быстро. Но в среднем мы можем ожидать, что наш элемент будет где-то посередине, а в худшем случае элемента даже нет в списке, и мы смотрим на все элементы в списке.
Решение
Используйте наборы! Магия в том, что внутренне элементы внутри наборов хешируются. Проще говоря, вы можете видеть это как каждый элемент, имеющий фиксированный адрес, как в обычном массиве. Таким образом, проверка того, входит ли элемент в набор, сводится к хешированию элемента, просмотру этого адреса, выбиванию двери и проверке, есть ли там кто-нибудь. Это можно сделать за постоянное время (хеширование обычно незначительно).
Сравнение времени поиска в списках и наборах дает на моей машине следующие результаты:
Итак, давайте исправим наш код очень простым способом:
primes = set(primes) # <- the fix!
n_numbers = 10000
counter = 0
some_numbers_to_test = np.random.randint(0, 50000, n_numbers)
for number in some_numbers_to_test:
if number in primes:
counter += 1
probability = counter / n_numbers
print(probability)
Теперь код выполняется на моей машине 2 миллисекунды, что значительно улучшилось в 3000 раз!
Обратите внимание на вероятность: на самом деле она составляет около 1 / ln (50 000) ≈9,24% согласно Теореме о простых числах!
Как видите, доработать код оказалось очень просто. Достаточно лишь небольшого добавления ключевого слова set.
2. Кэш
Иногда, особенно при использовании рекурсивных функций, значения некоторых функций вычисляются снова и снова. В качестве простого примера возьмем последовательность Фибоначчи.
def fibonacci(n):
if n in [0, 1]: # a list is ok here ;)
return 1
else:
return fibonacci(n-2) + fibonacci(n-1)
Вычисление 35-го числа Фибоначчи на моей машине занимает около 4 секунд, что опять же довольно медленно. Я не хочу думать о том, что происходит, когда я считаю сотое число. Но почему?
Эта проблема
Если вы выполните это таким образом, это будет работать, но это также очень неэффективно, поскольку многие значения функций вычисляются снова и снова. Возьмем, к примеру, дерево выполнения fibonacci(4):
Вы можете видеть, что fibonacci (2) вычисляется в двух разных местах: вызовы с номерами 7 и 8 являются избыточными, поскольку это точно такие же вызовы, которые уже выполнялись как 2-й и 3-й вызовы.
Проблема становится еще хуже, чем выше становятся числа Фибоначчи. Дерево становится глубже, следовательно, будет возникать все больше и больше дубликатов и бесполезных повторных вычислений. Если мы вычисляем фибоначчи (n), мы, например, повторно вычислим fib (2) n -2 раза. Мы пересчитаем fib (3) n -3 раза, fib (4) n -4 раза и т. Д., Это катастрофа.
Решение
Импортируйте lru_cache из functools! Это декоратор, который позволяет вашей функции сохранять уже вычисленные значения и повторно использовать их при необходимости. Вам больше ничего не нужно делать, просто импортируйте это и украсьте свою функцию!
from functools import lru_cache
@lru_cache()
def fibonacci(n):
if n in [0, 1]: # a list is ok here ;)
return 1
else:
return fibonacci(n-2) + fibonacci(n-1)
Благодаря этому усовершенствованию дерево выполнения выглядит примерно так:
Вы также можете увидеть улучшение времени работы. Теперь вычисление 35-го числа Фибоначчи занимает 0,05 миллисекунды, что примерно в 80000 раз, чем раньше!
Итак, кеширование определенно помогает, хотя вы должны иметь в виду, что на вашем компьютере достаточно места для хранения.
3. Многопроцессорность и многопоточность
Когда ничто другое не помогает, вы всегда можете продолжить, как и раньше, но делать что-то параллельно или одновременно. Многие ресурсы рассказывают вам, в чем разница между многопроцессорностью (параллелизм) и многопоточностью (параллелизм).
Небольшой пример приготовления
Представьте, что вам нужно пожарить мясо, нарезать овощи и испечь пирог.
Если вы один и не умеете выполнять несколько задач одновременно, возможно, вы сначала нарежете овощи, а затем полностью испечете торт. После этого вы начинаете жарить мясо. Конечно, это медленно, но ваша программа обычно работает именно так.
Для сравнения, параллельность - это когда вы выполняете эту задачу вместе с несколькими поварами (обработчиками). Кто-то из вашей команды жарит мясо, другой нарезает овощи, а третий печет торт одновременно. Это уже намного лучше!
При использовании многопроцессорной обработки (параллелизма) несколько задач выполняются параллельно. Он работает лучше всего, когда вам приходится иметь дело с большим количеством вычислительно тяжелых задач, а центральный процессор является узким местом.
Параллелизм - это когда вы снова сами по себе, но намного умнее и / или более опытны. Вы кладете пирог в духовку, бросаете мясо в сковороду, затем нарезаете овощи и заканчиваете, прежде чем мясо будет готово. Затем вы продолжаете с мясом и, в конце концов, снова занимаетесь пирогом, так как он требует больше всего времени. Параллелизм заключается в том, чтобы не бездельничать, когда вам нужно дождаться завершения процесса.
При использовании многопоточности (параллелизма) всегда выполняется одна задача одновременно, но если есть время ожидания, задача переключается. Это лучше всего работает, когда вам часто приходится ждать завершения других процессов, а ввод-вывод является узким местом.
Я сделал для вас небольшой рисунок, чтобы проиллюстрировать различия:
Если вы не уверены, использовать ли многопроцессорную или многопоточную обработку, попробуйте оба варианта. Код на Python почти такой же, просто посмотрите. Это так же просто, как заменить слово ThreadPoolExecutor на ProcessPoolExecutor или наоборот.
Это может произойти из-за того, что не всегда ясно различие между задачей, связанной с процессором, или задачей, связанной с вводом-выводом. Возьмем, к примеру, обработку изображений. Представьте, что у вас на диске много больших изображений, и вы хотите применить к ним какое-то преобразование.
Заранее сложно сказать, является ли загрузка изображений узким местом всего процесса или самой трансформацией.
Теперь перейдем к конкретному примеру. Представьте, что вы хотите получить HTML-код для некоторых веб-сайтов, потому что вы хотите что-то из него проанализировать. Ваш код может выглядеть так:
import requests urls = ['https://google.com', 'https://yahoo.com', 'https://bing.com', 'https://amazon.com'] get_url = lambda url: requests.get(url).content for url in urls: get_url(url)
Для меня это занимает примерно 3,5 секунды. Опять же, это можно сделать более эффективно!
Эта проблема
Вы повар, который не выполняет несколько задач одновременно! Вы запрашиваете веб-сайт, ждете, пока не получите его, а затем переходите к следующему. А пока просто подожди.
Вот как это исправить.
Решение
Вы можете импортировать ThreadPoolExecutor Python из пакета concurrent.futures. Затем вы можете использовать метод map для применения функции get_url ко всем URL-адресам. Результаты собираются в итераторе result.
import requests from concurrent.futures import ThreadPoolExecutor urls = ['https://google.com', 'https://yahoo.com', 'https://bing.com', 'https://amazon.com'] get_url = lambda url: requests.get(url).content with ThreadPoolExecutor(max_workers=4) as executor: result = executor.map(get_url, urls)
Таким образом, вы отправляете запрос всем веб-сайтам и собираете ответы по мере их поступления. Для меня сейчас это занимает всего 1,6 секунды, что примерно в два раза быстрее, чем раньше.
Бонус: используйте более умные алгоритмы
Часто вы можете немного настроить производительность своих алгоритмов с помощью этих простых и довольно неинвазивных методов. Однако иногда лучше придумать алгоритм получше.
Есть лучшие способы проверить, является ли число простым, чем делить его на все потенциальные делители (хотя в первом примере это не было проблемой). Есть более эффективные способы вычисления последовательности Фибоначчи, поскольку для этого доступна закрытая формула!
Следите за более умными алгоритмами. Вам не обязательно придумывать их самостоятельно, но вы должны хотя бы найти их и посмотреть, действительно ли они улучшают вашу работу! Возможно, вы никогда не будете использовать пузырьковую сортировку на практике (я надеюсь), а вместо этого положитесь на быструю сортировку или другой лучший алгоритм сортировки, если вам придется писать метод сортировки самостоятельно.
Заключение
Мы видели несколько простых способов улучшить производительность ваших задач почти бесплатно. Эти способы являются высокоуровневыми и могут быть реализованы каждым, кто хоть немного разбирается в Python. Мы узнали следующее:
- Используйте наборы. Или, что еще более важно, используйте правильную структуру данных. Некоторые структуры отлично подходят для простой записи, некоторые структуры данных отлично подходят для чтения записей (наборов!).
- Кэш: не вычисляйте вещи снова и снова. Если у вас есть хранилище (обычно оно есть), воспользуйтесь им.
- Многопроцессорность и многопоточность. Часто приходится вычислять функцию для множества различных входных данных. Просто делайте это параллельно или одновременно, не позволяйте процессорам отдыхать!
- Используйте лучшие алгоритмы. Этот алгоритм может быть трудным, но всегда учитывайте его. Либо подумайте о лучшем алгоритме самостоятельно, либо попробуйте найти подходящий алгоритм для решения вашей проблемы в Интернете.
Если вы примените эти советы на практике, вы сделаете свою работу намного быстрее и у вас будет больше времени для решения новых интересных проблем!
Надеюсь, что сегодня вы узнали что-то новое, интересное и полезное. Спасибо за прочтение!
В качестве последнего пункта, если вы
- хотите помочь мне написать больше о машинном обучении и
- все равно планируете получить подписку Medium
почему бы не сделать это по этой ссылке? Это мне очень поможет! 😊
Чтобы быть прозрачным, цена для вас не меняется, но около половины стоимости подписки идет непосредственно мне.
Большое спасибо, если вы считаете, что поддержите меня!
Если возникнут вопросы, напишите мне в LinkedIn!
