О чем боятся спросить Junior DS. Оптимизация кода

Привет всем! В данной статья я постараюсь ответить на вопросы, связанные с оптимизацией работы кода. Мы затронем различные возможности оптимизации работы кода, которые очевидны опытным специалистам и о них, нередко, даже не задумываются начинающие Data Scientist'ы.

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

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

Зачем надо оптимизировать и кто эта ваша оптимизация?

Прежде чем мы приступим к выяснению ответа на данный вопрос, хотел бы задать еще один риторический вопрос: хотите ли вы работать с бОльшим количеством данных за меньшее время? Если ответ положительный, то вы по нужному адресу!

Для формулировки определения оптимизации прибегнем к определению, взятому из википедии:

Оптимизация - процесс максимизации выгодных характеристик, соотношений, и минимизации расходов.

В нашем случае, мы максимизируем количество полезных операций с данными, минимизируя временный затраты (оптимизация по времени исполнения) и минимизируя использование оперативной и постоянной памяти (оптимизация по памяти).

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

1. Знай тип данных

Как мы знаем, в Python есть изменяемые и неизменяемые типы данных.

К неизменяемым, помимо численных типов (float, int), логических (bool) и строковых (str) относятся также кортежы (tuple). К изменяем типам можно причислить список (list), словарь (dict) и множество (set).

Нередко, знание, какой тип данных лучше применить для данной задачи, приводит к оптимизации.

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

Давайте посмотрим на конкретные примеры:

• Нужно быстро изменять структуру данных и позже обратиться к ним:

Самое быстрое изменение существующего элемента происходит в словаре. Это обусловлено строением словаря, сложность добавления элемента O(1), так как обращение идет по хеш-значению ключа. Лист имеет линейную сложность изменения элемента O(n).

• Нужно быстро избавиться от дубликатов, посмотреть на разницу или объединение уникальных значений двух множест:

Самым быстрым способом является создания множества (set).

Стоит отметить, что множество является неупорядоченным типом данных, т.е. позиция элемента изменяется.

Для поиска разницы или объединения списков достаточно взять множество суммы или разници данных списков. Рассмотрим на примере:

a = [1,2,3,4,5,6,6,1,8,9,3,4,5]
b = [0,7,3,4,5,4,2,1,8,9,3,4,5]
print(a)
print(b)

[1, 2, 3, 4, 5, 6, 6, 1, 8, 9, 3, 4, 5]

[0, 7, 3, 4, 5, 4, 2, 1, 8, 9, 3, 4, 5]

c = set(a)
d = set(b)
print(c)
print(d)
print(f'разница между c и d:{c-d}')
print(f'разница между d и c:{d-c}')
print(f'объединение  c и d: {c.union(d)}')

{1, 2, 3, 4, 5, 6, 8, 9}

{0, 1, 2, 3, 4, 5, 7, 8, 9}

разница между c и d:{6}

разница между d и c:{0, 7}

объединение c и d: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Данные примеры достаточно очевидны, поэтому давайте перейдем к основному совету в данном разделе.

• Нужно хранить какие-то параметры, потом вызвать которым мы позже пробегаем в цикле:

Здесь, для оптимизации как и по памяти, так и по времени рекомендуется параметры хранить в кортеже.

Давайте рассмотрим на примере:

• Инициализируем список и кортеж некоторых параметров типа строки (str), посмотрим на скорость инициализации, объем занимаемой памяти, время пробегания по параметрам в цикле. Для чистоты эксперимента будем использовать magic-функцию %timeit.

%timeit parameters_list = ['1st', '2nd', '3rd', '4th', '5th']

The slowest run took 15.35 times longer than the fastest. This could mean that an intermediate result is being cached.

10000000 loops, best of 5: 74.6 ns per loop

%timeit parameters_tuple = ('1st', '2nd', '3rd', '4th', '5th')

The slowest run took 51.93 times longer than the fastest. This could mean that an intermediate result is being cached.

10000000 loops, best of 5: 20.5 ns per loop

В целом, определение переменной быстрее при использовании кортежей!

• Посмотрим на память, которую занимают переменные, тут нам поможет метод getsizeof библиотеки sys:

from sys import getsizeof
parameters_list = ['1st', '2nd', '3rd', '4th', '5th']
parameters_tuple = ('1st', '2nd', '3rd', '4th', '5th')
print(f'размер объекта списка {getsizeof(parameters_list)} бит')
print(f'размер объекта кортежа {getsizeof(parameters_tuple)} бит')

размер объекта списка 112 бит.

размер объекта кортежа 96 бит.

По памяти тоже видна оптимизация!

• Давайте теперь пройдемся в цикле по двум типам данных:

%%timeit
for param in parameters_list:
	pass

The slowest run took 17.38 times longer than the fastest. This could mean that an intermediate result is being cached.

10000000 loops, best of 5: 142 ns per loop

%%timeit
for param in parameters_tuple:
	pass

The slowest run took 13.72 times longer than the fastest. This could mean that an intermediate result is being cached.

10000000 loops, best of 5: 142 ns per loop

Разница не существенна, однако, для примера взят достаточно маленький набор параметров, так же в самый медленный запуск гораздо быстрее был исполнен именно к кортежах!

Таким образом, если у вас есть набор неизменяемых параметров по которым надо пройти циклом, то использование кортежей крайне рекомендовано для оптимизации по времени и по памяти.

2. Забудь про append!

Если есть возможность, постарайтесь заменить добавление элементов списка через метод append на конструкцию генератора списка. Это обусловлено тем, что при добавлении элемента в список, памяти, выделенной под данный список может не хватить на новый элемент и под него снова придется выделять место в памяти, тем самым появляется необходимость в дополнительных ненужных операциях. Кроме того, данный подход избавляет нас от процесса фильтрации уже созданного списка на этапе генерации списка (List comprehension). Давайте посмотрим на примере:

%%timeit
a = list()
for i in range(100):
  a.append(i)

100000 loops, best of 5: 7.68 µs per loop

%timeit a = [i for i in range(100)]

100000 loops, best of 5: 3.98 µs per loop

В некоторых случаях ускорение создания списка может доходить до двух раз!

Давайте также сравним генератор с условиями (List comprehension) с аналогичной конструкцией в цикле. Для этого построим список четных чисел от 0 до 100:

• в цикле:

%%timeit
a = []
for i in range(102):
	if i%2==0:
  	a.append(i)

100000 loops, best of 5: 9.82 µs per loop

• c помощью List comprehension:

%timeit a = [i for i in range(102) if i%2==0]

100000 loops, best of 5: 7.78 µs per loop

Как и говорилось ранее, фильрация на уровне генерации списка отрабатывает быстрее!

3. + в карму, - к скорости

При работе со строками нередко требуется "склеить" две и более строчки в одну.

Самым простым, но не оптимальным решением является использование суммирования строчек через плюс.

Объясню на примере:

1. У нас есть строчки "I", "WILL", "NOT", "SLEEP", "THROUGH", "MY", "EDUCATION".

2. финальный результат мы будем определять как сумму исходных строчек.

3. При использовании, суммирования, мы должны будем использовать 6 операций суммирования с выделением памяти под каждое из них.

Выглядит не оптимально, посмотрим результат исполнения:

input = ['I', 'WILL', 'NOT', 'SLEEP', 'THROUGH', 'MY', 'EDUCATION']
%%timeit 
out = ''
for word in input:
	out += word

The slowest run took 4.22 times longer than the fastest. This could mean that an intermediate result is being cached.

1000000 loops, best of 5: 557 ns per loop

При использовании встроенного метода join мы сразу определяем итоговый размер строки после применения метода и сразу выделяем под него память. Таким образом, один процесс выделения памяти выигрывает у 6 маленьких.

%timeit out = ' '.join(input)

The slowest run took 18.70 times longer than the fastest. This could mean that an intermediate result is being cached.

10000000 loops, best of 5: 181 ns per loop

Как видим, процесс оптимальнее по времени, когда мы используем метод join!

4. Даже импорт библиотек можно оптимизировать!

Рассмотрим простой пример импорта и использования логарифма из библиотеки math:

• В первом случае импортируем библиотеку:

import math 
%timeit math.log(2022)

The slowest run took 46.74 times longer than the fastest. This could mean that an intermediate result is being cached.

10000000 loops, best of 5: 150 ns per loop

from math import log
%timeit log(2022)

The slowest run took 49.43 times longer than the fastest. This could mean that an intermediate result is being cached.

10000000 loops, best of 5: 123 ns per loop

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

На самом деле, все просто: при использовании конструкции math.log() перед вызовом самой функции мы дополнительно вызываем метод __getattribute()__ или __getattr()__, который ищет в библиотеке math данный модуль, тем самым разница вызвана этой операцией.

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

5. Векторизируй!

5.1 Numpy

Здесь стоит упомянуть, что языки C/C++ быстрее, чем Python, поэтому выбор библиотек в вашей реализации кода должен быть предопределен языком реализации операций библиотеки. Так, вычисления в библиотеке numpy реализованы практически полностью на C++, что делает ее приоритетной в работе с векторами и матрицами.

• Самым простым примером является умножение массива на число:

a = [i for i in range(50)]
b = np.array([i for i in range(50)])

%%timeit
for i in range(len(a)):
	a[i] *= 5

10000 loops, best of 5: 71.4 µs per loop

%timeit c = b*5

The slowest run took 37.82 times longer than the fastest. This could mean that an intermediate result is being cached.

1000000 loops, best of 5: 845 ns per loop

В применении функции ко всем вектору и заключается принцип векторизации.

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

Так, мы можем применить косинус не к каждому элементу отдельно, а ко всему вектору:

from numpy import zeros, float64, cos, arange
n = 100000

• не векторизованная версия:

%%timeit
a = zeros([n], float64)
for i in range(n):
	a[i] = cos(i)

10 loops, best of 5: 130 ms per loop

• тот же функционал, но уже векторизованный:

%%timeit
val = arange(0, n)
a = cos(val)

100 loops, best of 5: 2.47 ms per loop

Оптимизация очевидна!

5.2 Pandas

Принцип векторизации применим так же в библиотеке pandas, он реализован в следующих методах:

• apply, когда вы хотите применить функцию к DataFrame построчно или по столбцу;

• map, когда вы хотите применить функцию к столбцу (Series);

• applymap, когда вы хотите применить функцию к каждому элементу DataFrame.

Рассмотрим на примере:

Создадим простой датафрейм:

col1 = [1, 2, 3, 4]
col2 = [5, 6, 7, 8]
d = {'one':col1, 'two':col2}
df = pd.DataFrame(d)

Применим расчет дисперсии по столбцам,

df.apply(np.std)

one 1.118034

two 1.118034

dtype: float64

возведем поэлементно в квадрат наши значения:

Главное правило - никаких циклов!

df.applymap(lambda x: x2)

Отдельно для колонки:

df['one'].map(lambda x: x2)

0 1

1 4

2 9

3 16

Name: one, dtype: int64

Векторизация очень сильный инструмент для оптимизации вашего кода!

6. Параллелизация

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

from multiprocessing import Pool
def f(x):
	return x*x
if name == 'main':
with Pool(5) as p:
	print(p.map(f, [1, 2, 3, 4, 5]))

вывод:

[1, 4, 9, 16, 25]

7. Сторонние библиотеки

Для оптимизации казалось бы очевидных процессов полезно использовать сторонние библиотеки.

7.1 Modin

Настоятельно рекомендую использование библиотек оберток, таких как Modin. Данная библиотека является оберткой над pandas для параллелизации выполнения операций.

Изменяя одну строчку импорта:

вместо стандартного импорта

import pandas as pd

используем Modin

import modin.pandas as pd

Который помогает распараллелить процессы pandas.

Так, создатели библиотеки заявляют, что даже на простом 4-х ядерном ноутбуке файл в формате csv размером 700 Mb загружается с помощью метода read_csv в 4 раза быстрее.

Помимо Modin, хочется еще добавить информацию о библиотеках, ускоряющих работу, таких как cython и numba. Как говорилось ранее, вставки и операции исполняемые на C/С++ существенно оптимизируют вычисления на python!

В cython используется код-суперпозиция C/C++ и python, а в numba используется другая компиляция кода, разгоняя стандартные функции.

7.2 Numba

Основной трюк ускорения с numba заключается в разгоне стандартных функций с помощью компиляции кода на llvm. Разгон заключается в использовании декоратора Материал и код подготовил: Андрей Дзись, канал в ТГ @dzis_science.@jit(nopython=True)@jit перед использованием функции.

Важный момент заключается в том, что не все функции из класического питона разгоняются numba, список стандартных функций питона доступен по ссылке. Так же numba может оптимизировать некоторые функции из numpy, список по ссылке.

Т.е ускорение производится с помощью двух строчек:

from numda import jit
@jit(nopython=True)
#ваша функция

Параметр nopython позволяет не использовать python интерпретатор при компилировании кода, что дает максимальный прирост скорости, однако, не все функции могут быть скомпилированы таким образом! В случае ошибки nopython режим автоматически перейдет в object режим, который будет кусками оптимизировать код, что невозможно оптимизировать, будет отправляться на интерпретатор python.

7.3 Cython

Вставки кода cython представляют собой уникальную смесь python и С++.

Рассмотрим на примере:

• чистый код функции на python:

def sum(x):
  out = 0
  for i in range(x):
    out += i
  return out

• тот же код, но уже на cython:

cpdef sum(x):
  cdef int out = 0
  cdef int i
  for i in range(x):
  	out += i
  return out

Таким образом, очевидны различия:

1. Для использования функции интерпретатором из C и из python необходимо класическое def заменить на cpdef.

2. Для ускорения кода необходима строгая (прямо как в C) типизация с использованием cdef.

Далее, код функии cython превратить для ускорения в код C. Тут необходимо сохранить нашу исходную функцию в файл расширения .pyx и с помощью метода cythonize из Cython.Build и метода setup из distutils.core сделать файл setup.py, который мы далее скомпилируем и будем использовать в наших вычислениях. Примерный код:

from distutils.core import setup
from Cython.Build import cythonize
setup(ext_modules = cythonize('your_function_name.pyx'))
#скомпилируем
python setup.py build_ext --inplace

Теперь можем смело импортировать наш скомпилированный файл и наслаждаться ускорением кода:

import your_function_name

Итоги

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

Надеюсь данный материал был полезен.

Work! Optimize!

Материал и код подготовил: Андрей Дзись, канал в ТГ @dzis_science.