Производительность в Python. Легкий путь
Всегда знал, что одно из достоинств Python — возможность переписать самые тормозные куски кода на Си и увеличить быстродействие программы до недостижимых интерпретируемым языкам высот. Но сам ни разу не пробовал, т.к. считал что это слишком сложно. После прочтения этой статьи больше так не считаю.
Программисты знакомые с ctypes врядли найдут тут что-то интересное, новичков же прошу под кат.
Ctypes — механизм Python для импорта функций из внешних библиотек.
%timeit — magic-функция оболочки IPython, измеряющая время выполнения выражения на Python
Ctypes — это прекрасно! Давайте начнем с небольшого банального примера: суммирование чисел в определенном диапазоне.
Вот реализация этой функции на Python
def sumrange(arg): return sum(xrange(arg)) Отлично! Но что если мы попробуем суммировать действительно большой диапазон чисел, например от 0 до 10**8 (т.е. 100,000,000)
In [2]: %timeit sumrange(10**2) 1000000 loops, best of 3: 1.53 us per loop In [3]: %timeit sumrange(10**8) 1 loops, best of 3: 9.77 s per loop In [4]: %timeit sumrange(10**9) 1 loops, best of 3: 97.8 s per loop Уже не так весело. Попробуем кое-что другое:
def sumrange2(arg): x = i = 0 while i < arg: x += i i += 1 return x Что из этого получится?
In [10]: %timeit sumrange2(10**2) 100000 loops, best of 3: 10.5 us per loop In [11]: %timeit sumrange2(10**8) 1 loops, best of 3: 18.5 s per loop Вот это да… Так еще хуже… В этот раз даже не буду пробовать 10**9.
Так как же нам ускорить выполнение? Только не предлагайте математические оптимизации… мы же в новом мире компьютеров! (в оригинале: don't suggest math tricks… this is the the new world of computing!)
Да, я знаю, что сложность алгоритма — постоянная величина и не зависит о величины аргумента, n*(n+1)/2. Но статья посвящена не этому.
Как насчет ctypes?
#include unsigned long long sumrange(unsigned long long arg) < unsigned long long i, x; x = 0; for (i = 0; i < arg; i++) < x = x + i; >return x; >Сохраним с именем sumrange.c и скомпилируем (не будем использовать оптимизации для чистоты эксперимента):
$ gcc -shared -Wl,-install_name,sumrange.so -o sumrange.so -fPIC sumrange.c
Импортируем в Python то что получилось:
import ctypes sumrange_ctypes = ctypes.CDLL('./sumrange.so').sumrange sumrange_ctypes.restype = ctypes.c_ulonglong sumrange_ctypes.argtypes = ctypes.c_ulonglong, И Оскар получает…
In [15]: %timeit sumrange_ctypes(10**2) 1000000 loops, best of 3: 1.28 us per loop In [16]: %timeit sumrange_ctypes(10**8) 1 loops, best of 3: 381 ms per loop In [17]: %timeit sumrange_ctypes(10**9) 1 loops, best of 3: 3.79 s per loop In [18]: %timeit sumrange_ctypes(10**10) 1 loops, best of 3: 37.8 s per loop Итоговая сводка:
| 10**2 | 10**8 | 10**9 | 10**10 | |
|---|---|---|---|---|
| Чистый Python, способ №1 | 1.53 мкс | 9.77 с | 97.8 с | - |
| Чистый Python, способ №2 | 10.5 мкс | 18.5 с | - | - |
| ctypes | 1.28 мкс | 381 мс | 3.79 с | 37.8 с |
Адский прирост производительности!
Для Node.js хакеров, есть эквивалент ctypes — FFI (Foreign Function Interface): github.com/rbranson/node-ffi
Сколько операций в секунду выполняет python
МЕРОПРИЯТИЯ
YADRO X MOSCOW USER GROUP C++ MEETUP
Комментарии
Популярные По порядку
Не удалось загрузить комментарии.
ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ
ООП на Python: концепции, принципы и примеры реализации
Программирование на Python допускает различные методологии, но в его основе лежит объектный подход, поэтому работать в стиле ООП на Python очень просто.
3 самых важных сферы применения Python: возможности языка
Существует множество областей применения Python, но в некоторых он особенно хорош. Разбираемся, что же можно делать на этом ЯП.
Программирование на Python: от новичка до профессионала
Пошаговая инструкция для всех, кто хочет изучить программирование на Python (или программирование вообще), но не знает, куда сделать первый шаг.
Сколько операций в секунду выполняет python
Hepic_Antony_Skarlatos → How old are you ?
n0sk1ll → Codeforces Round #910 (Div. 2)
molney → Разбор Codeforces Round 909 (Div. 3)
MahaRathi → What's wrong in my solution?
Medeali → Finally Pupil
n0sk1ll → Editorial for Codeforces Round #910 (Div. 2)
Little_Sheep_Yawn → Help Needed for this Pypy Issue!
IanDeHaan → Invitation to the Alberta Collegiate Programming Contest 2023 (Open Division)
killmeray → VK — огромная проблема олимпиад
glebustim → CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)
k o_osaga → T1 is the 2023 World Champion
ICPCNews → ICPC 2023 Online Challenge powered by Huawei
pritishn → Share your big brain moments from back when you were low rated.
av.dk → Div3 round 909
atcoder_official → Sky Inc, Programming Contest 2023 (AtCoder Beginner Contest 329) Announcement
T LE → Finally, semantic search for competitive programming problems
pingvvin → I need IZHO 2011 Editorial
MikeMirzayanov → Изменение правил об использовании стороннего кода в соревнованиях Codeforces
m aroonrk → ALGO ARTIS Programming Contest 2023 Autumn（AtCoder Regular Contest 168) Announcement
zwezdinv → Codeforces Round #909 (Div. 3)
Rahat_Khan_Pathan → Solve UVa 11235 — Frequent values using Segment Tree
Mahmyt → IZHO age limit
AcidWrongGod → Открытая Командная Олимпиада КФУ 2023
libnguyen2 → [Discussion]: Solutions for IOI 2023 tasks + My solution to IOI23 Day1 P1 — Closing Time
sg0310461 → Why this solution is giving TLE?
Насколько С++ быстрее Python
Есть миллион причин любить Python (особенно специалистам по данным). Но сильно ли он отличается от более профессиональных низкоуровневых языков программирования, таких как С или С++? Скорее всего, многие дата-специалисты или пользователи Python задавались этим вопросом или однажды задумаются об этом. Python и такие языки, как С++, во многом отличаются друг от друга. И в этой статья мы посмотрим, насколько С++ быстрее Python на очень простом примере.
Я не стал брать выдуманное задание, а решил показать их различия на простой и практичной задаче. Заключается она в том, чтобы сгенерировать все возможные k-меры последовательности ДНК при указанном значении k (для тех, кто не знает, что такое k-мер ДНК, объясню простым языком в следующем разделе). Я выбрал этот пример, потому что многие задачи по обработке и анализу геномных данных (напр. генерация k-меры) требуют множество вычислительных работ. Именно поэтому многих специалистов по данным в биоинформатике привлекает С++ (в дополнение к Python).
ВАЖНОЕ ПРИМЕЧАНИЕ: В этой статье не сравнивается С++ и Python в их самом эффективном использовании. Оба кода можно написать гораздо лучшем способом, применяя более продуманные подходы. Единственная цель статьи — сравнить два языка при использовании абсолютно одинаковых инструкций и одного алгоритма.
Кратко о k-мер ДНК
ДНК — это длинная цепь блоков, называемых нуклеотидами. В состав ДНК входит 4 типа нуклеотидов, которые обозначаются буквами A, C, G и T. Человек (а точнее Homo Sapiens) содержит 3 миллиарда нуклеотидных пар. Например, маленькая часть человеческого ДНК может выглядеть вот так:
Если вы возьмёте из этой строки любую последовательность из 4 нуклеотидов (т.е. букв), то получите k-мер с длинною 4 (называемая 4-мер). Вот несколько примеров 4-мер, образованных из этой части ДНК.
ACTA , CTAG , TAGG , AGGG , GGGA и т.д.
Задача
В этой статье мы сгенерируем все возможные 13-мер. С точки зрения математики, здесь нужно применить метод подстановки. Следовательно, получаем ⁴¹³ (=67,108,864) возможных 13-меров. Чтобы сгенерировать результаты в С++ и Python, я воспользуюсь простым алгоритмом. Посмотрим решения и сравним их.
Сравнение решений
Чтобы было проще сравнить С++ и Python в этой конкретной задаче, я взял совершенно одинаковый алгоритм для обоих языков и намерено написал простые и похожие коды. Я не стал использовать сложные структуры данных и сторонние пакеты или библиотеки. Первый код написан в Python.
def convert(c): if (c == 'A'): return 'C' if (c == 'C'): return 'G' if (c == 'G'): return 'T' if (c == 'T'): return 'A' print("Start") opt = "ACGT" s = "" s_last = "" len_str = 13 for i in range(len_str): s += opt[0] pos = 0 counter = 1 while (s != s_last): counter += 1 # Чтобы вывести все k-меры, уберите комментарий со следующей строки. # print(s) change_next = True for i in range(len_str): if (change_next): if (s[i] == opt[-1]): s = s[:i] + convert(s[i]) + s[i+1:] change_next = True else: s = s[:i] + convert(s[i]) + s[i+1:] break # Чтобы вывести все k-меры, уберите комментарий со следующей строки. # print(s) print("Number of generated k-mers: <>".format(counter)) print("Finish!")Код на Python сгенерировал все 67 миллионов 13-меров за 61,23 секунд. Справедливости ради, я закомментировал строчки, которые выводили k-меры (строчки 25 и 37). Если же вы хотите видеть все k-меры во время генерации, уберите комментарий с этих двух строчек.
Примечание. Для вывода всех k-мер потребуется много времени. При необходимости, воспользуйтесь CTRL+C для прекращения выполнения кода.
Теперь посмотрим на тот же алгоритм в С++.
#include #include using namespace std; char convert(char c) < if (c == 'A') return 'C'; if (c == 'C') return 'G'; if (c == 'G') return 'T'; if (c == 'T') return 'A'; return ' '; >int main() < cout for (int i=0; i int pos = 0; int counter = 1; while (s != s_last) < counter ++; // Чтобы вывести все k-меры, уберите комментарий со следующей строки. // cout else < s[i] = convert(s[i]); break; >> > > // Чтобы вывести все k-меры, уберите комментарий со следующей строки. // cout
После компиляции код сгенерировал все 67 миллионов 13-меров за 2,42 секунд. То есть, С++ выполняет один и тот же код в 25 раз быстрее, чем Python. Я повторил эксперимент с 14-мером и 15-мером (нужно изменить строчку 12 в Python и 22 в С++). Результаты приведены в Таблице 1.
Мы видим, что С++ выполняет одни и те же инструкции и алгоритм намного быстрее, чем Python. И для многих программистов и специалистов по данным это неудивительно, но этот эксперимент показывает, что разница в скорости колоссальна.
Ещё раз повторю, оба кода написаны самым простым способом (и возможно, самым неэффективным). В Python существует множество других подходов, улучшающих производительность кода, и вам стоит их опробовать.
from itertools import product for i in product(['A', 'C', 'G'], repeat=10): print(''.join(i))Кроме того, в этом эксперименте не использовалось распараллеливание центрального (CPU) и графического (GPU) процессов, необходимое в подобных задачах (задачи чрезвычайной параллельности). Также мы почти не нагружали память. Если фиксировать результаты (для какой-либо цели), то процесс управления памяти приведёт к ещё большему “отрыву” между С++ и Python.
Этот пример и многие другие задачи говорят о том, что даже специалистам по данным нужно знать такие языки, как С++, если они работают с огромным объемом данных или с теми, что растут в геометрической прогрессией.
- 4 совета по работе с потоками и мьютексами в C++
- Распознаём 50 видов текста на C++ с Plywood
- 9 Уровней применения функции zip в Python