Если у вас есть медленные циклы в Python, вы можете исправить это… пока не сможете

1656567884 esli u vas est medlennye czikly v python vy mozhete

Максим Мамаев

Давайте возьмем в качестве примера вычислительную задачу, напишем некоторый код и посмотрим, как мы можем улучшить время выполнения. Вот и мы.

Оформление сцены: проблема с ранцем

Это вычислительная задача, которую мы будем использовать в качестве примера:

Задача о ранце – хорошо известная задача комбинаторной оптимизации. В этой главе мы рассмотрим его самый распространенный вкус, the 0–1 задание с ранцем, и его решение посредством динамического программирования. Если вы знакомы с этой темой, вы можете пропустить эту часть.

Вам дается рюкзак емкости C и коллекцию Н предметов. Каждый предмет имеет вес w[i] и значение v[i]. Ваша задача – упаковать в рюкзак самые ценные вещи. Другими словами, вы должны максимизировать общую стоимость предметов, помещаемых в предмет ранца, с ограничением: общий вес взятых предметов нельзя превышает емкость ранца.

Когда вы получите решение, общий вес предметов в рюкзаке называется «весом раствора», а их общая стоимость – «ценностью раствора».

Проблема имеет множество практических применений. К примеру, вы решили инвестировать 1600 долларов в знаменитые акции FAANG (общее название для акций Facebook, Amazon, Apple, Netflix и Google, известных как Alphabet). Каждая акция имеет текущую рыночную цену и годовую оценку цены. По состоянию на один день 2018 они такие:

========= ======= ======= =========Company   Ticker  Price   Estimate========= ======= ======= =========Alphabet  GOOG    1030    1330Amazon    AMZN    1573    1675Apple     AAPL    162     193 Facebook  FB      174     216 Netflix   NFLX    312     327========= ======= ======= =========

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

Это проблема с ранцем. Ваш бюджет (1600 долларов США) – это мешок емкость (C). Акции – это предметы, подлежащие упаковке. Текущие цены таковы весы (w). Оценки цены таковы ценности. Проблема выглядит тривиальной. Однако решение не очевидно на первый взгляд — стоит ли покупать одну акцию Amazon или одну акцию Google плюс по одной в определенной комбинации Apple, Facebook или Netflix.

Конечно, в этом случае можно произвести быстрые расчеты вручную и прийти к решению: купить Google, Netflix и Facebook. Таким образом, вы потратите 1516 долларов и ожидаете получить 1873 долларов.

Теперь вы верите, что открыли Клондайк. Вы разбиваете свою копилку и собираете 10 000 долларов. Несмотря на ваше волнение, вы соблюдаете правила «одна акция – одна покупка». Поэтому имея больший бюджет, вам придется расширить свои возможности. Вы решили рассмотреть все акции из списка NASDAQ 100 в качестве кандидатов на покупку.

Будущее никогда не было более ярким, но вдруг вы понимаете, что для того, чтобы определить свой идеальный инвестиционный портфель, вам придется проверить около 2 ⁰⁰ комбинаций. Даже если вы очень оптимистично настроены по поводу неизбежности и повсеместности цифровой экономики, любой экономике нужна — по крайней мере, вселенная, в которой она работает. К сожалению, через несколько триллионов лет, когда ваши вычисления закончатся, наша Вселенная, вероятно, не будет.

Алгоритм динамического программирования

Мы должны отказаться от подхода грубой силы и запрограммировать какое-нибудь разумное решение. Маленькие проблемы с рюкзаками (а у нас, верите или нет) решаются с помощью динамического программирования. Основная идея состоит в том, чтобы начать с тривиальной проблемы, решение которой мы знаем, а затем постепенно прибавлять сложность.

Если вы считаете следующие объяснения слишком абстрактными, вот аннотированная иллюстрация решения очень маленькой проблемы с ранцем. Это поможет вам представить, что происходит.

Предположим, что учитывая первое я предметов коллекции, мы знаем значение решения s(i, k) для всех емкостей ранца к в диапазоне от 0 до C.

Другими словами, мы шили C+1 «вспомогательные» ранцы всех размеров от 0 до C. Затем мы отсортировали нашу коллекцию, взяли первую я предмет и временно отложите все остальное. А теперь мы предполагаем, что с помощью какой-то магии мы знаем, как оптимально упаковать каждый из мешков из этого рабочего набора я предметов. Предметы, которые мы выбираем из рабочего набора, могут отличаться для разных мешков, но сейчас нас не интересует, какие предметы мы берем или пропускаем. Это только значение решения s(i, k) что мы записываем для каждого из наших только что сшитых мешков.

Теперь мы берем следующий, (i+1)го, элемент из коллекции и добавить его в рабочий набор. Давайте найдем значение решения для всех вспомогательных рюкзаков с новым рабочим набором. Другими словами, находим s(i+1, k) для всех k=0..C дано s(i, k).

Если к меньше веса нового предмета w[i+1], мы не можем взять этот предмет. Действительно, даже если бы мы взяли только этот предмет, он сам по себе не поместился бы в ранец. поэтому s(i+1, k) = s(i, k) для всех k < w[i+1].

Для ценностей k >= w[i+1] мы должны сделать выбор: или мы берем обновку в рюкзак capaciтy k или мы его пропускаем. Нам нужно оценить эти два варианта, чтобы определить, какой из них дает нам большую ценность, упакованную в мешок.

Если мы возьмем (i+1)мы приобретаем значение v[i+1] и потратить часть емкости ранца, чтобы выдержать вес w[i+1]. Это оставляет нам возможности k–w[i+1] которые мы должны оптимально заполнить, используя (некоторые из) первых я предметов. Это оптимальное заполнение имеет значение раствора s(i, k–w[i+1]). Это число нам уже известно, поскольку, по предположению, мы знаем все значения решений рабочего множества я предметов. Итак, значение решения-кандидата для ранца к с предметом i+1 взято бы
s(i+1, k | i+1 взяты) = v[i+1] + s(i, k–w[i+1]).

Другой вариант – пропустить элемент i+1. В этом случае в нашем рюкзаке ничего не меняется, а значение решения-кандидата будет таким же, как s(i, k).

Чтобы определить лучший выбор, мы сравниваем два кандидата на значение решения:
s(i+1, k | i+1 взяты) = v[i+1] + s(i, k–w[i+1])
s(i+1, k | i+1 пропущено) = s(i, k)

Максимум из них становится решением s(i+1, k).

В итоге:

if k < w[i+1]:    s(i+1, k) = s(i, k)else:    s(i+1, k) = max( v[i+1] + s(i, k-w[i+1]), s(i, k) )

Теперь мы можем решить проблему с рюкзаком шаг за шагом. Начинаем с пустого рабочего набора (i=0). Очевидно, s(0, k) = 0 для любого к. Затем мы делаем шаги, добавляя элементы в рабочий набор и находим значение решения s(i, k) пока мы не придем в s(i+1=N, k=C) что является значением решения исходной задачи.

Обратите внимание, что для этого мы построили сетку NxC значение раствора.

Однако, несмотря на то, что мы узнали значение решения, мы не знаем, какие предметы были взяты в ранец. Чтобы выяснить, мы возвращаем сетку обратно. Начиная с s(i=N, k=C)сравниваем s(i, k) из s(i–1, k).

Если s(i, k) = s(i–1, k), яэтот предмет не взят. Повторяем с i=i–1 сохранение стоимости к без изменений. В противном случае, япредмет взят, и для следующего этапа проверки мы убавляем рюкзак w[i] — мы установили i=i–1, k=k–w[i].

Таким образом мы исследуем все предметы из Нго к первому и определите, какие из них уложили в ранец. Это дает нам решение проблемы с ранцем.

Код и анализ

Теперь, когда у нас есть алгоритм, мы сравним несколько реализаций, начиная с простого. Код доступен на GitHub.

Данные есть Nasdaq 100 список, содержащий текущие цены и оценки цен на сто акций (на один день 2018 года). Наш инвестиционный бюджет составляет 10000 долларов.

Напомним, что цены на акции – это не круглые долларовые числа, а центы. Поэтому, чтобы получить точное решение, мы должны сосчитать все в центах – мы точно хотим избежать чисел с плавающей точкой. Итак, емкость нашего ранца составляет ($)10000 x 100 центов = ($)1000000, а общий размер нашей задачи N x C = 1000000.

Поскольку целое число занимает 4 байта памяти, мы ожидаем, что алгоритм будет потреблять примерно 400 МБ оперативной памяти. Следовательно, память не будет ограничением. Это время выполнения, о котором мы должны заботиться.

Конечно, все наши реализации дадут то же решение. Для справки, инвестиции (вес решения) составляют 999 930 ($9999,30), а ожидаемая прибыль (значение решения) – 1219 475 ($12 194,75). Список акций для покупки достаточно длинный (80 из 100 позиций). Вы можете получить его, запустив код.

И, пожалуйста, помните об этом это упражнение по программированию, а не совет по инвестициям. К тому времени, когда вы прочитаете эту статью, цены и оценки будут изменяться по сравнению с приведенными здесь в качестве примера.

1*SEihq9zvMPCd8qLZHaUHIg
Авторство: Мартин фон Ротц

Простые старые петли «for».

Простая реализация алгоритма приведена ниже.

Есть две части.

В первой части (строки 3–7 выше) две вложены for Петли используются для построения сетки раствора.

Внешний цикл добавляет элементы в рабочий набор, пока мы не достигнем Н (ценность Н передается в параметре items). Строка значений решения каждого нового рабочего набора инициализируется значениями, вычисленными для предыдущего рабочего набора.

Внутренний цикл для каждого рабочего набора повторяет значение k от веса только что добавленного item к C (ценность C передается в параметре capacity).

Заметьте, что нам не нужно начинать цикл с k=0. Когда k меньше веса itemЗначения решения всегда совпадают с рассчитанными для предыдущего рабочего набора и эти числа уже были скопированы в текущую строку путем инициализации.

Когда циклы завершены, мы имеем сетку решения и значение решения.

Вторая часть (строки 9–17) является одиночной for петля из Н итерации. Он возвращает сетку обратно, чтобы найти, какие предметы были взяты в ранец.

Далее мы сосредоточимся исключительно на первой части алгоритма, как она есть O(N*C) сложность времени и пространства Часть возврата требует только O(N) времени и не тратит никакой дополнительной памяти – ее потребление ресурсов относительно незначительное.

Это занимает 180 секунд для простой реализации решить Nasdaq 100 проблема с ранцем на моем компьютере.

Насколько это плохо? С одной стороны, со скоростями современности мы не привыкли тратить три минуты на ожидание компьютера. С другой стороны, размер проблемы — сто миллионов — выглядит действительно устрашающим, так что, может, три минуты нормально?

Чтобы получить определенный контрольный показатель, давайте запрограммируем тот же алгоритм на другом языке. Для обеспечения скорости вычислений нам нужен компилируемый язык со статическим типом. Нет, не C. Это не изысканно. Мы будем придерживаться моды и писать в Go:

Как видите, код Go очень похож на код в Python. Я даже скопировал одну строку, самую длинную, как есть.

Какое время? 400 миллисекунд! Иными словами, Python получился в 500 раз медленнее Go Go. Разрыв, вероятно, будет еще больше, если мы попробуем это на C. Это, безусловно, катастрофа для Python.

1*lmi8rlKeei1hcMRkeShzIw
Цитата из книги Дж. К. Роулинг «Гарри Поттер и тайная комната» Источник оригинального изображения здесь.

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

В простом решателе 99,7% времени работы тратится на две строчки. Эти две строки содержат внутренний цикл, выполняемый 98 миллионов раз:

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

Я слышал, что Python for оператор медленный, но, что интересно, большинство времени проводит не в for строка, но в теле цикла.

Мы можем разбить тело цикла на отдельные операции, чтобы увидеть, является ли какая-то конкретная операция слишком медленной:

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

Обратите внимание, как разбиение кода увеличило общее время выполнения. Теперь внутренний цикл занимает 99,9% времени работы. Чем глупее ваш код Python, тем медленнее он становится. Интересно, не правда ли?

Встроенная функция карты

Давайте сделаем код более оптимизированным и заменим внутренний for петля с встрой map() функция:

Время выполнения этого кода равно 102 секунды, что на 78 секунд отстает от оценки простой реализации действительно, map() работает заметно, но не сильно, резвее.

Понимание списка

Возможно, вы заметили, что каждый запуск внутреннего цикла создает список (прилагаемый к сетке решения как новая строка). Способ создания списков на Pythonic – это, конечно, понимание списка. Давайте вместо этого попробуем map().

Это закончилось в 81 секунда. Мы добились еще одного улучшения и сократили время работы вдвое по сравнению с простой реализацией (180 секунд). Вне контекста это можно было бы оценить как значительный прогресс. К сожалению, мы еще на световые годы от нашего образца на 0,4 сек.

Массивы NumPy

Наконец-то мы исчерпали встроенные инструменты Python. Да, я слышу рев публики, скандирующей «NumPy! NumPy!» Но, чтобы оценить эффективность NumPy, нам следовало попытаться ввести его в контекст for, map() и преждевременное понимание списка.

Ладно, теперь пришло время NumPy. Итак, мы отказываемся от списков и помещаем наши данные в массивы numpy:

Вдруг результат обнадеживающий. Этот код работает в 1,5 раза медленнее, чем развязатель ванильного списка (123 сек по сравнению с 81 секундой). Как это может быть?

Рассмотрим профили линий для обоих решателей.

Инициализация grid[0] поскольку массив numpy (строка 274) втрое быстрее, чем когда это список Python (строка 245). Внутри внешнего цикла инициализация grid[item+1] это в 4,5 раза быстрее для массива NumPy (строка 276), чем для списка (строка 248). Всё идет нормально.

Однако выполнение строки 279 в 1,5 раза медленнее, чем его аналог в строке 252 без numpy. Проблема состоит в том, что понимание списка создает список значений, но мы сохраняем эти значения в a Массив NumPy который находится в левой части выражения. Следовательно, эта строка неявно добавляет накладные расходы по преобразованию списка в массив NumPy. Поскольку на строку 279 приходится 99,9% времени исполнения, все ранее отмеченные преимущества numpy становятся незначительными.

Но нам все равно нужные средства повторять через массивы, чтобы выполнить вычисление. Мы уже узнали, что понимание списка – самый быстрый инструмент итерации. (Кстати, если вы попытаетесь построить массивы NumPy в обычном старом for Избегая преобразования списка в массив NumPy, вы получите колоссальные 295 секунд.) Итак, мы застряли и не годен ли NumPy? Конечно, нет.

1*0yrZox6O3EEEKregnri0Vw
Авторство: Тарас Макаренко

Правильное использование NumPy

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

Например, есть функция where() который принимает три массива в качестве параметров: condition, xи yи возвращает массив, созданный путем выбора элементов любого из x или от y. Первый параметр, condition, является массивом логических. Он указывает, из чего выбрать: если элемент condition оценивается до Trueподходящий элемент x посылается на выход, иначе элемент from y берется.

Обратите внимание, что функция NumPy делает это за один вызов. Циклирование по массивам убрано под капот.

Вот как мы используем where() как заменитель внутреннего for цикл в первом решателе или, соответственно, осмысление списка последних:

Есть три интересных фрагмента кода: строка 8, строка 9 и строки 10–13, пронумерованные выше. Вместе они заменяют внутренний цикл, который берет на себя все возможные размеры ранцев, чтобы найти значение решения.

Пока емкость ранца не достигнет веса предмета, только что добавленного к рабочему комплекту (this_weight), мы должны проигнорировать этот элемент и установить значение решения на значение предыдущего рабочего набора. Это достаточно просто (строка 8):

grid[item+1, :this_weight] = grid[item, :this_weight]

Затем строим вспомогательный массив temp (строка 9):

temp = grid[item, :-this_weight] + this_value

Этот код аналогичен, но гораздо быстрее, чем:

[grid[item, k — this_weight] + this_value  for k in range(this_weight, capacity+1)]

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

Обратите внимание, какtemp массив строится путем добавления a скалярный к массиву. Это еще одна мощная функция NumPy, которая называется трансляция. Когда NumPy видит операнда с разными размерами, он пытается расширить (т.е. «транслировать») малоразмерный операнд, чтобы он соответствовал размерам другого. В нашем случае скаляр разворачивается к массиву такого же размера, как grid[item, :-this_weight] и эти два массива прилагаются вместе. В результате значение this_value добавляется к каждому элементу grid[item, :-this_weight]— петля не нужна.

В следующем фрагменте (строки 10–13) мы используем функцию where() выполняющий именно то, что требует алгоритм: он сравнивает два потенциальных значения решения для каждого размера ранца и выбирает большее.

grid[item + 1, this_weight:] =                 np.where(temp > grid[item, this_weight:],             temp,             grid[item, this_weight:])

Сравнение производится с помощью condition параметр, который рассчитывается как temp > grid[item, this_weight:]. Это поэлементная операция, создающая массив логических значений по одному для каждого размера вспомогательного ранца. A TрЗначение ue означает, что подходящий предмет нужно упаковать в ранец. Следовательно, значение решения, полученное из массива, является вторым аргументом функции.n, temp. В противном случае элемент нужно пропустить, а значение решения будет скопировано из предыдущей строки сетки – третьего аргумента the where()функция .

Наконец варп-привод включен! Этот решатель выполняется в 0,55 сек. Это в 145 раз быстрее, чем решатель на основе понимания списка, и в 329 раз быстрее, чем использующий кодfor петля. Хотя мы не опередили развязчик, написанный на Go (0,4 секунды), мы подошли к нему достаточно близко.

Некоторые петли должны остаться

Подождите, а как насчет внешнего for петля?

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

Можем ли мы переписать внешний цикл с помощью функции NumPy, подобно тому, что мы сделали с внутренним циклом? Ответ – нет.

Несмотря на то, что оба есть for петли, наружные и внутренние петли очень отличаются по своей задаче.

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

Внешний цикл создает 2D-массив из 1D-массивов, элементами которых являются нет известно, когда начинается цикл. Более того, эти массивы компонентов вычисляются по рекурсивному алгоритму: мы можем найти элементы (i+1)и массив только после того, как мы найдем яth.

Предположим, что внешний цикл можно представить как функцию:
grid = g(row0, row1, … rowN)
Все параметры функции должны быть оценены перед вызовом функции, но только row0 известно заранее. Поскольку вычисление (i+1)и ряд зависит от наличия яth, нам нужен цикл, идущий от 1 к N вычислить все row параметры Итак, чтобы заменить внешний цикл функцией, нам нужен другой цикл, оценивающий параметры этой функции. Этот другой цикл — это тот цикл, который мы пытаемся заменить.

Другой способ избежать внешнего for цикл состоит в использовании рекурсии. Можно легко написать рекурсивную функцию calculate(i) что производит яи ряд сетки. Чтобы выполнить работу, функция должна знать (i-1)th строке, поэтому он называет себя как calculate(i-1) а затем вычисляет яной строки, используя функции NumPy, как мы делали раньше. Затем можно заменить всю внешнюю петлю calculate(N). Чтобы сделать картину полной, рекурсивный решатель ранца можно найти в исходном коде, сопровождающем статью на GitHub.

Однако рекурсивный подход очевидно не масштабируется. Python не оптимизирован для хвоста. Глубина стека рекурсии по умолчанию ограничена порядком тысячи. Это ограничение, несомненно, консервативно, но когда нам нужна глубина в миллионы, переполнение стека очень вероятно. Более того, эксперимент показывает, что рекурсия даже не дает преимущества в производительности над разрешителем на основе NumPy с внешним. for петля.

Здесь у нас закончились инструменты, предоставленные Python и его библиотеками (насколько мне известно). Если вам абсолютно нужно ускорить цикл, реализующий рекурсивный алгоритм, вам придется прибегнуть к Cython, либо к скомпилированной JIT версии Python, либо к другому языку.

Еда на вынос

1*YvnvnzC2wMwZ_EF3qFHBcg
Время работы средств решения проблем с рюкзаками
  • Выполняйте многочисленные вычисления с помощью функций NumPy. Они на два порядка быстрее, чем встроенные Python инструменты.
  • С встроенных инструментов Python понимание списка быстрее, чем map() что гораздо быстрее, чем for.
  • Для глубоко рекурсивных алгоритмов циклы более эффективны, чем рекурсивные вызовы функций.
  • Вы не можете заменить рекурсивные циклы на map()понимание списка или функция NumPy.
  • «Типый» код (разбит на элементарные операции) медленный. Используйте встроенные функции и инструменты.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *