Как уменьшить время работы программы на питоне

Время на прочтение
8 мин

Количество просмотров 19K

Введение

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

Хотелось бы поделиться несколькими методами, которые помогают в реальных задачах. Я пользуюсь win10 x64.

Экономим память силами Python

В качестве примера рассмотрим вполне реальный пример. Пусть у нас имеется некоторый магазин в котором есть список товаров. Вот нам понадобилось поработать с этими товарами. Самый хороший вариант, когда все товары хранятся в БД, но вдруг что-то пошло не так, и мы решили загрузить все товары в память, дабы обработать их. И тут встает резонный вопрос, а хватит ли нам памяти для работы с таким количеством товаров?

Давайте первым делом создадим некий класс, отвечающий за наш магазин. У него будет лишь 2 поля: name и listGoods, которые отвечают за название магазина и список товаров соответственно.

class ShopClass:
    def __init__(self, name=""):
        self.name = name
        self.listGoods = []

Теперь мы хотим наполнить магазин товарами (а именно заполнить поле listGoods). Для этого создадим класс, отвечающий за информацию об одном товаре (я использую dataclass’ы для таких примеров).

# если ругается на dataclass, то делайте 
# pip install dataclasses
# затем в коде вызывайте импорт
# from dataclasses import dataclass 
@dataclass
class DataGoods:
    name:str
    price:int
    unit:str

Далее необходимо заполнить наш магазин товарами. Для чистоты эксперимента я создам по 200 одинаковых товаров в 3х категориях:

shop = ShopClass("MyShop")
for _ in range(200):
    shop.listGoods.extend([
        DataGoods("телефон", 20000, "RUB"),
        DataGoods("телевизор", 45000, "RUB"),
        DataGoods("тостер", 2000, "RUB")
    ])

Теперь пришло время измерить память, которую занимает наш магазин в оперативке (для измерения памяти я использую модуль pympler):

from pympler import asizeof
print("Размер магазина:", asizeof.asizeof(shop))
>>> Размер магазина: 106648

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

Теперь перейдем к решению данной проблемы. Python создает новый объект таким образом, что под него выделяется очень много информации, о которой мы даже не догадываемся. Надо понимать, что python создает объект __dict__ внутри класса для того, чтобы можно было добавлять новые атрибуты и удалять уже имеющиеся без особых усилий и последствий. Посмотрим, как можно динамически добавлять новые атрибуты в класс.

shop = ShopClass("MyShop")
print(shop.__dict__)  
>>> {'name': 'MyShop', 'listGoods': []}

shop.city = "Москва"
print(shop.__dict__) 
>>> {'name': 'MyShop', 'listGoods': [], 'city': 'Москва'}

Однако в нашем примере это абсолютно не играет никакой роли. Мы уже заранее знаем, какие атрибуты должны быть у нас. В python’e есть магический атрибут __slots__, который позволяет отказаться от __dict__. Отказ от __dict__ приведет к тому, что для новых классов не будет создаваться словарь со всеми атрибутами и хранимым в них данными, по итогу объем занимаемой памяти должен будет уменьшиться. Изменим немного наши классы:

class ShopClass:
    __slots__ = ("name", "listGoods")
    def __init__(self, name=""):
        self.name = name
        self.listGoods = []
@dataclass
class DataGoods:
    __slots__ = ("name", "price", "unit")
    name:str
    price:int
    unit:str

И протестируем по памяти наш магазин.

from pympler import asizeof
print("Размер магазина:", asizeof.asizeof(shop))
>>> Размер магазина: 43904

Как видно, объем, занимаемый магазином, уменьшился почти в 2.4 раза (значение может варьироваться в зависимости от операционной системы, версии Python, значений и других факторов). У нас получилось оптимизировать занимаемый объем памяти, добавив всего пару строчек кода. Но у такого подхода есть и минусы, например, если вы захотите добавить новый атрибут, вы получите ошибку:

shop = ShopClass("MyShop")
shop.city = "Москва"
>>> AttributeError: 'ShopClass' object has no attribute 'city'

На этом преимущества использования слотов не заканчиваются, из-за того, что мы избавились от атрибута __dict__ теперь ptyhon’у нет необходимости заполнять словарь каждого класса, что влияет и на скорость работы алгоритма. Протестируем наш код при помощи модуля timeit, первый раз протестируем наш код на отключенных __slots__ (включенном__dict__):

import timeit
code = """
class ShopClass:
    #__slots__ = ("name", "listGoods")
    def __init__(self, name=""):
        self.name = name
        self.listGoods = []
@dataclass
class DataGoods:
    #__slots__ = ("name", "price", "unit")
    name:str
    price:int
    unit:str
shop = ShopClass("MyShop")
for _ in range(200):
    shop.listGoods.extend([
        DataGoods("телефон", 20000, "RUB"),
        DataGoods("телевизор", 45000, "RUB"),
        DataGoods("тостер", 2000, "RUB")
])
"""
print(timeit.timeit(code, number=60000))
>>> 33.4812513

Теперь включим __slots__ (#__slots__ = («name», «price», «unit») -> __slots__ = («name», «price», «unit») и # __slots__ = («name», «listGoods») -> __slots__ = («name», «listGoods»)):

# включили __slots__ в коде выше
print(timeit.timeit(code, number=60000))
>>> 28.535005599999998

Результат оказался более чем удовлетворительным, получилось ускорить код примерно на 15% (тестирование проводилось несколько раз, результат был всегда примерно одинаковый).

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

Пытаемся ускорить код

Способов ускорить python существует несколько, начиная от использования встроенных фишек язык (например, описанных в прошлой главе), заканчивая написанием расширений на C/C++ и других языках.

Я расскажу лишь о тех способах, которые не займут у вас много времени на изучение и позволят в короткий срок начать пользоваться этим функционалом.

Cython

На мой взгляд Cython является отличным решением, если вы хотите писать код на Python, но при этом вам важна скорость выполнения кода. Реализуем код для подсчета сумм стоимости всех телевизоров, телефонов и тостеров на чистом Python и рассчитаем время, которое было затрачено (будем создавать 20.000.000 товаров):

import time
class ShopClass:
   __slots__ = ("name", "listGoods")
   def __init__(self, name=""):
      self.name = name
      self.listGoods = []
@dataclass
class DataGoods:
   __slots__ = ("name", "price", "unit")
   name: str
   price: int
   unit: str
shop = ShopClass("MyShop")
t = time.time()
for _ in range(200*100000):
   shop.listGoods.extend([
      DataGoods("телефон", 20000, "RUB"),
      DataGoods("телевизор", 45000, "RUB"),
      DataGoods("тостер", 2000, "RUB")
   ])
print("СОЗДАЕМ ТОВАРЫ НА PYTHON:", time.time()-t)
>>> СОЗДАЕМ ТОВАРЫ НА PYTHON: 44.49887752532959
telephoneSum, televizorSum, tosterSum = 0, 0, 0
t = time.time()
for goods in shop.listGoods:
   if goods.name == "телефон":
      telephoneSum += goods.price
   elif goods.name == "телевизор":
      televizorSum += goods.price
   elif goods.name == "тостер":
      tosterSum += goods.price
print("ВРЕМЯ НА ПОДСЧЁТ СУММ PYTHON:", time.time() - t)
>>> ВРЕМЯ НА ПОДСЧЁТ СУММ PYTHON: 13.135360717773438

Как мы видим, время обработки весьма неутешительно. Теперь приступим к использованию cython. Для начала ставим библиотеку cython_npm (см. официальный гитхаб): pip install cython-npm. Теперь создадим новую папку в нашем проекте, назовем её cython_code и в ней создадим файл cython_data.pyx (программы cython пишутся с расширением .pyx).

Перепишем класс магазина под cython:

cdef class CythonShopClass:
   cdef str name
   cdef list listGoods

   def __init__(self, str name):
       self.name = name
       self.listGoods = []

В cython необходимо строго типизировать каждую переменную, которую вы используете в коде (это не обязательно, но если этого не делать, то уменьшения по времени не будет). Для этого необходимо писать cdef <тип данных> <название переменной> в каждом классе или методе. Реализуем остальной код на cython. Функцию my_def() реализуем без cdef, а с привычным нам def, так как её мы будем вызывать из основного python файла. Также в начале нашего файла .pyx необходимо прописать версию языка (# cython: language_level=3).

# cython: language_level=3
# на забывает вставить код класса магазина
cdef class CythonDataGoods:
   cdef str name
   cdef int price
   cdef str unit
   def __init__(self, str name, int price, str unit):
       self.name = name
       self.price = price
       self.unit = unit
cdef int c_testFunc():
    cdef CythonShopClass shop
    cdef CythonDataGoods goods
    cdef int i, t, telephoneSum, televizorSum, tosterSum
    size, i, telephoneSum, televizorSum, tosterSum = 0, 0, 0, 0, 0
    shop = CythonShopClass("MyShop")
    t = time.time()
    for i in range(200*100000):
       shop.listGoods.extend([
           CythonDataGoods("телефон", 20000, "RUB"),
           CythonDataGoods("телевизор", 45000, "RUB"),
           CythonDataGoods("тостер", 2000, "RUB")
       ])
    print("СОЗДАЕМ ТОВАРЫ НА CYTHON:", time.time()-t)
    t = time.time()
    for goods in shop.listGoods:
        if goods.name == "телефон":
            telephoneSum += goods.price
        elif goods.name == "телевизор":
            televizorSum += goods.price
        elif goods.name == "тостер":
            tosterSum += goods.price
    print("ВРЕМЯ НА ПОДСЧЁТ СУММ CYTHON:", time.time() - t)
    return 0
def my_def():
    data = c_testFunc()
    return data

Теперь в main.py нашего проекта сделаем вызов cython кода. Для этого делаем сначала импорт всех установленных библиотек:

from cython_npm.cythoncompile import export
from cython_npm.cythoncompile import install
import time

И делаем сразу же компиляцию нашего cython и его импорт в основной python код

export('cython_code/cython_data.pyx')
import cython_code.cython_data as cython_data

Теперь необходимо вызвать код cython

if __name__ == "__main__":
   a = cython_data.my_def()

Запускаем. Обратим внимание, что было выведено в консоли. В cython, где мы делали вывод времени на создание товаров, мы получили:

>>> СОЗДАЕМ ТОВАРЫ НА CYTHON: 4.082242012023926

А там где был вывод после подсчета сумм получили:

>>> ВРЕМЯ НА ПОДСЧЁТ СУММ CYTHON: 1.0513946056365967

Как мы видим, скорость создания товаров сократилась с 44 до 4 секунд, то есть мы ускорили данную часть кода почти в 11 раз. При подсчете сумм время сократилось с 13 секунд до 1 секунды, примерно в 13 раз.

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

Магия Python

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

shop = ShopClass("MyShop")
t = time.time()
getGoods = lambda index: {0: ("телефон", 20000, "RUB"), 
                          1: ("телевизор", 45000, "RUB"), 
                          2:("тостер", 2000, "RUB")}.get(index) 
shop.listGoods = [DataGoods(*getGoods(i%3)) for i in range(200*100000)]
print("СОЗДАЕМ ТОВАРЫ НА PYTHON:", time.time()-t)
>>>  СОЗДАЕМ ТОВАРЫ НА PYTHON: 19.719463109970093

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

PyPy

Бывает так, что нет возможности переписать код на cython или другой язык, потому что уже имеется достаточно большая кодовая база (или по другой причине), а скорость выполнения программы хочется увеличить. Рассмотрим код из прошлого примера, где мы использовали лямбда функции и генератор списков. Тут на помощь может прийти PyPy, это интерпретатор языка python, использующий JIT компилятор. Однако PyPy поддерживает не все сторонние библиотеки, если вы используете в коде таковые, то изучите подробнее документацию. Выполнить python код при помощи PyPy очень легко. 

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

Таким образом, 19 секунд python’овского кода из прошлого примера у нас получилось сократить до 4.5 секунд вообще без переписывания кода, то есть почти в 4 раза.

Вывод

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

Были рассмотрены не все возможные варианты ускорения кода. В некоторых случаях можно использовать Numba, NumPy, Nim или multiprocessing. Все зависит от того, какую задачу вы решаете. Некоторые задачи будет проще решать на других языках, так как python не способен решить всё на этом свете.

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

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

TL;DR Используйте списковые включения (list comprehensions), генераторные выражения (generator expressions) и генераторы везде, где только можно. Это поможет сэкономить память и время выполнения программы.

Антон Сычугов

Ведущий разработчик CoMagic.dev (IT-платформа UIS и CoMagic)

Списковые включения (List comprehensions)

Например у нас есть большой список словарей (объявления контекстной рекламы):

import timeit
import time
import itertools
import random

now = time.time()
ads_list = list({’bid’: random.randint(1, 1000), ’date’: now — i, ’id’: 1000000 — i} for i in range(1000000))

Зададим начальное время выборки и конечное

date_start = now — 60*60*24*7
date_end = now — 60*60*24*3

И попробуем выбрать все объявления, ставка которых выше 600 и дата попадает в выбранный интервал. Затем возьмем первые 1000 элементов полученного списка. Сначала решим задачу «в лоб»:

def many_lists():
    expensive_ads = [a for a in ads_list if a[’bid’] > 600]
    expensive_in_interval = [a for a in expensive_ads if a[’date’] > date_start and a[’date’] < date_end]
    return expensive_in_interval[:1000]


timeit.timeit(many_lists, number=100)
9.126969000000031

Ок, попробуем немного оптимизировать и сделаем проверку даты там же, где и ставки:

def many_lists_improved():
    expensive_ads = [a for a in ads_list if a[’bid’] > 600 and a[’date’] > date_start and a[’date’] < date_end]
    return expensive_ads[:1000]


timeit.timeit(many_lists_improved, number=100)
8.304767416000004

Уже лучше, но не сильно лучше.

Генераторные выражения (generator expressions)

Попробуем использовать генераторные выражения (для получения среза будем использовать функцию islice из itertools, которая возвращает итератор по срезу):

def generators():
    expensive_ads = (a for a in ads_list if a[’bid’] > 600)
    expensive_in_interval = (a for a in expensive_ads if a[’date’] > date_start and a[’date’] < date_end)
    return list(itertools.islice(expensive_in_interval, 0, 1000))


timeit.timeit(generators, number=100)
2.422867124999925

Итог: увеличение производительности более чем в 3 раза.

Генераторные фунции (generator functions)

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

Генераторной фунцией в python называется функция, которая ведет себя как итератор. Для определения генераторной функции нужно использовать ключевое слово yield:

def count_five():
    for i in range(5):
        yield i

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

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

import sys
import time
import random
import psutil
from timeit import timeit

now = time.time()
ads_list = list((1000000 — i, now — i, random.randint(1, 1000)) for i in range(1000000))
date_end = now — 60*60*24*3
date_start = now — 60*60*24*7


def below_3days(ad_list):
    return [a for a in ad_list if a[1] < date_end] def above_7days(ad_list): return [a for a in ad_list if a[1] > date_start]


def tag_bid(ad_list):
    return [(a[0], a[1], a[2] > 500 and ’expensive’ or ’cheap’) for a in ad_list]


def above_7days_gen(ad_list):
    for a in ad_list:
        if a[1] > date_start:
            yield a


def below_3days_gen(ad_list):
    for a in ad_list:
    if a[1] < date_end: yield a def tag_bid_gen(ad_list): for a in ad_list: tag = a[2] > 500 and ’expensive’ or ’cheap’
        yield (a[0], a[1], tag)


list_pipeline = lambda ads: below_3days(above_7days(tag_bid(ads)))
gen_pipeline = lambda ads: below_3days_gen(above_7days_gen(tag_bid_gen(ads)))

pipelines = {
    ’list’: list_pipeline,
    ’gen’: gen_pipeline
}


def run_pipeline(ad_list, pipeline):
    processed = pipeline(ad_list)
    return sorted(processed, key=lambda item: item[0])


if __name__ == ’__main__’:
    try:
        pipeline = pipelines[sys.argv[1]]
    except (IndexError, KeyError):
        print(’invalid arguments, use `list` or `gen` to choose pipeline’)
        sys.exit(1)

    process = psutil.Process()
    mem_before = process.memory_info().rss
    tm = timeit(lambda: run_pipeline(ads_list, pipeline), number=1)
    consumption = process.memory_info().rss — mem_before
    print(’consumption:’, consumption/1024, ’KB, in’, round(tm, 2), ’s’)

Запустим наш скрипт сначала с ключом list:

python run_pipeline.py list
consumption: 15568.0 KB, in 0.25 s

А потом с ключом gen:

python run_pipeline.py gen
consumption: 6112.0 KB, in 0.25 s

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

И напоследок

Не всегда операторы в python ведут себя так, как мы привыкли. Например сложение списков:

def plus():
    list1 = list(range(1000000))
    list2 = list(range(1000000))
    list1 = list1 + list2
    return list1


def plus_eq():
    list1 = list(range(1000000))
    list2 = list(range(1000000))
    list1 += list2
    return list1


timeit.timeit(plus, number=10)
0.4108163330001844

timeit.timeit(plus_eq, number=10)
0.3518642500000624

Посмотрим дизассемблером, что происходит внутри этих функций:

import dis

dis.dis(plus)
2 0 LOAD_GLOBAL 0 (list)
2 LOAD_GLOBAL 1 (range)
4 LOAD_CONST 1 (1000000)
6 CALL_FUNCTION 1
8 CALL_FUNCTION 1
10 STORE_FAST 0 (list1)
12 LOAD_GLOBAL 0 (list)
14 LOAD_GLOBAL 1 (range)
16 LOAD_CONST 1 (1000000)
18 CALL_FUNCTION 1
20 CALL_FUNCTION 1
22 STORE_FAST 1 (list2)
24 LOAD_FAST 0 (list1)
26 LOAD_FAST 1 (list2)
28 BINARY_ADD
30 STORE_FAST 0 (list1)
32 LOAD_FAST 0 (list1)
34 RETURN_VALUE


dis.dis(plus_eq)
2 0 LOAD_GLOBAL 0 (list)
2 LOAD_GLOBAL 1 (range)
4 LOAD_CONST 1 (1000000)
6 CALL_FUNCTION 1
8 CALL_FUNCTION 1
10 STORE_FAST 0 (list1)
12 LOAD_GLOBAL 0 (list)
14 LOAD_GLOBAL 1 (range)
16 LOAD_CONST 1 (1000000)
18 CALL_FUNCTION 1
20 CALL_FUNCTION 1
22 STORE_FAST 1 (list2)
24 LOAD_FAST 0 (list1)
26 LOAD_FAST 1 (list2)
28 INPLACE_ADD
30 STORE_FAST 0 (list1)
32 LOAD_FAST 0 (list1)
34 RETURN_VALUE

Как видно, инструкция 28 в случае `+` простое сложение, а в случае `+=` — сложение на месте, которое не приводит к созданию нового списка. += в данном случае сопоставим по производительности с list.extend:

def extend():
    list1 = list(range(1000000))
    list2 = list(range(1000000))
    list1.extend(list2)
    return list1

timeit.timeit(extend, number=10)
0.3511457080001037

Заключение

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

Выводы

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

«Питон – медленный». Наверняка вы не раз сталкивались с этим утверждением, особенно от людей, пришедших в Python из C, C++ или Java. Во многих случаях это верно. Циклы или сортировка массивов, списков или словарей иногда действительно работают медленно. В конце концов, главная миссия Python – сделать программирование приятным и легким. Ради лаконичности и удобочитаемости пришлось отчасти принести в жертву производительность.

Тем не менее, в последние годы предпринято немало усилий для решения проблемы. Теперь мы можем эффективно обрабатывать большие наборы данных с помощью NumPy, SciPy, Pandas и numba, поскольку все эти библиотеки написаны на C/C++. Еще один интересный проект – PyPy ускоряет код Python в 4.4 раза по сравнению с CPython (оригинальная реализация Python).

Недостаток PyPy – нет поддержки некоторых популярных модулей, например, Matplotlib, SciPy.

Но ускорить Python можно и без внешних библиотек. В наших силах разогнать его с помощью полезных трюков, используемых в повседневной практике кодинга.

1. Стандартные функции

В Python много работающих очень быстро реализованных на C встроенных функций. Они покрывают большинство тривиальных вычислительных операций (abs, min, max, len, sum). Хороший разработчик должен их знать, чтобы в подходящем месте не изобретать неуклюжие велосипеды, а брать надёжное стандартное решение. Возьмём в качестве примеров встроенные функции set() и sum(). Сравним их работу с кастомными реализациями того же функционала.

Пример для set():

        import random
random.seed(666)
a_long_list = [random.randint(0, 50) for i in range(1000000)]

# 1. Кастомная реализация set
%%time
unique = []
for n in a_long_list:
  if n not in unique:
    unique.append(n)

# Вывод в консоли:
# CPU times: user 316 ms, sys: 1.36 ms, total: 317 ms
# Wall time: 317 ms

# 2. Встроенная функция set
%%time  
unique = list(set(a_long_list))

# Вывод в консоли:
# CPU times: user 8.74 ms, sys: 110 μs, total: 8.85 ms
# Wall time: 8.79 ms
    

Пример для sum():

        # 1. Кастомная реализация sum
%%time
sum_value = 0
for n in a_long_list:
  sum_value += n
print(sum_value)

# Вывод в консоли:
# 25023368
# CPU times: user 9.91 ms, sys: 2.2 ms, total: 101 ms
# Wall time: 100 ms

# 2. Встроенная функция sum
%%time
sum_value = sum(a_long_list)
print(sum_value)

# Вывод в консоли:
# 25023368
# CPU times: user 4.74 ms, sys: 277 μs, total: 5.02 ms
# Wall time: 4.79 ms
    

Стандартные варианты в 36 (set) и 20 (sum) раз быстрее, чем функции, написанные самим разработчиком.

2. sort() vs sorted()

Если нам просто нужен отсортированный список, при этом неважно, что будет с оригиналом, sort() будет работать немного быстрее, чем sorted(). Это справедливо для базовой сортировки:

        # 1. Дефолтная сортировка с использованием sorted()
%%time
sorted(a_long_list)

# Вывод в консоли:
# CPU times: user 12 ms, sys: 2.51 ms, total: 14.5 ms
# Wall time: 14.2 ms

# 2. Дефолтная сортировка с использованием sort()
%%time
a_long_list.sort()

# Вывод в консоли:
# CPU times: user 8.52 ms, sys: 82 μs, total: 8.6 ms
# Wall time: 10 ms
    

Справедливо и для сортировки с использованием ключа – параметра key, который определяет сортировочную функцию:

        # 1. Сортировка с ключом с использованием sorted()
%%time
str_list1 = "Although both functions can sort list, there are small differences".split()
result = sorted(str_list1, key=str.lower)
print(result)

# Вывод в консоли:
# ['Although', 'are', 'both', 'can', 'differences', 'functions', 'list,', 'small', 
'sort', 'there']
# CPU times: user 29 μs, sys: 0 ns, total: 29 μs
# Wall time: 32.9 μs

# 2. Сортировка с ключом с использованием sort()
%%time
str_list2 = "Although both functions can sort list, there are small differences".split()
str_list2.sort(key=str.lower)
print(str_list2)

# Вывод в консоли:
# ['Although', 'are', 'both', 'can', 'differences', 'functions', 'list,', 'small', 
'sort', 'there']
# CPU times: user 26 μs, sys: 0 ns, total: 26 μs
# Wall time: 29.8 μs

# 3. Сортировка с ключом (лямбда) с использованием sorted()
%%time
str_list1 = "Although both functions can sort list, there are small differences".split()
result = sorted(str_list1, key=lambda str: len(str))
print(result)

# Вывод в консоли:
# ['can', 'are', 'both', 'sort', 'list,', 'there', 'small', 'Although', 'functions', 'differences']
# CPU times: user 61 μs, sys: 3 μs, total: 64 μs
# Wall time: 59.8 μs

# 4. Сортировка с ключом (лямбда) с использованием sort()
%%time
str_list2 = "Although both functions can sort list, there are small differences".split()
str_list2.sort(key=lambda str: len(str))
print(str_list2)

# Вывод в консоли:
# ['can', 'are', 'both', 'sort', 'list,', 'there', 'small', 'Although', 'functions', 'differences']
# CPU times: user 36 μs, sys: 0 ns, total: 36 μs
# Wall time: 38.9 μs
    

Так происходит потому, что метод sort() изменяет список прямо на месте, в то время как sorted() создает новый отсортированный список, сохраняя исходный нетронутым. Другими словами, порядок значений внутри a_long_list фактически уже изменился.

Однако функция sorted() более универсальна. Она может работать с любой итерируемой структурой. Поэтому, если нужно отсортировать, например, словарь (по ключам или по значениям), придется использовать sorted():

        a_dict = {'A': 1, 'B': 3, 'C': 2, 'D': 4, 'E': 5}

# 1. Дефолтная сортировка по ключам
%%time
result = sorted(a_dict) 
print(result)

# Вывод в консоли:
# ['A', 'B', 'C', 'D', 'E']
# CPU times: user 4 μs, sys: 0 ns, total: 4 μs
# Wall time: 6.91 μs

# 2. Cортировка по значениям, результат в виде списка кортежей
%%time
result = sorted(a_dict.items(), key=lambda item: item[1]) 
print(result)

# Вывод в консоли:
# [('A', 1), ('C', 2), ('B', 3), ('D', 4), ('E', 5)]
# CPU times: user 7 μs, sys: 0 ns, total: 7 μs
# Wall time: 8.82 μs

# 3. Сортировка по значениям, результат в виде словаря
%%time
result = {key: value for key, value in sorted(a_dict.items(), key=lambda item: item[1])}
print(result)

# Вывод в консоли:
# {'A': 1, 'C': 2, 'B': 3, 'D': 4, 'E': 5}
# CPU times: user 8 μs, sys: 0 ns, total: 8 μs
# Wall time: 11.2 μs
    

3. Литералы вместо функций

Когда нужен пустой словарь или список, вместо dict() или list(), можно напрямую вызвать {} и [] (для пустого множества все еще нужна функция set()). Этот прием не обязательно ускорит ваш код, но сделает его более «pythonic».

        # 1. Создание пустого словаря с помощью dict()
%%time
sorted_dict1 = dict()
for key, value in sorted(a_dict.items(), key=lambda item:item[1]):
  sorted_dict1[key] = value

# Вывод в консоли:
# CPU times: user 10 μs, sys: 0 ns, total: 10 μs
# Wall time: 12.2 μs

# 2. Создание пустого словаря с помощью литерала словаря
%%time
sorted_dict2 = {}
for key, value in sorted(a_dict.items(), key=lambda item:item[1]):
  sorted_dict2[key] = value

# Вывод в консоли:
# CPU times: user 9 μs, sys: 0 ns, total: 9 μs
# Wall time: 11 μs

# 3. Создание пустого списка с помощью list()
%%time
list()

# Вывод в консоли:
# CPU times: user 3 μs, sys: 0 ns, total: 3 μs
# Wall time: 3.81 μs

# 4. Создание пустого списка с помощью литерала списка
%%time
[]

# Вывод в консоли:
# CPU times: user 2 μs, sys: 0 ns, total: 2 μs
# Wall time: 3.1 μs
    

4. Генераторы списков

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

Например, отберём все чётные числа из списка another_long_list:

        even_num = []
for number in another_long_list:
    if number % 2 == 0:
        even_num.append(number)

    

Но есть более лаконичный и элегантный способ сделать то же самое. Код цикла for можно сократить до одной-единственной строки с помощью генератора списка, выиграв при этом в скорости почти в два раза:

        import random
random.seed(666)
another_long_list = [random.randint(0,500) for i in range(1000000)]

# 1. Создание нового списка с помощью цикла for
%%time
even_num = []
for number in another_long_list:
  if number % 2 == 0:
    even_num.append(number)

# Вывод в консоли:
# CPU times: user 113 ms, sys: 3.55 ms, total: 117 ms
# Wall time: 117 ms

# 2. Создание нового списка с помощью генератора списка
%%time
even_num = [number for number in another_long_list if number % 2 == 0]

# Вывод в консоли:
# CPU times: user 56.6 ms, sys: 3.73 ms, total: 60.3 ms
# Wall time: 64.8 ms
    

Сочетая это правило с Правилом #3 (использование литералов), мы легко можем превратить список в словарь или множество, просто изменив скобки:

        a_dict = {'A': 1, 'B': 3, 'C': 2, 'D': 4, 'E': 5}

sorted_dict3 = {key: value for key, value 
  in sorted(a_dict.items(), key=lambda item: item[1])}
print(sorted_dict3)

# Вывод в консоли:
# {'A': 1, 'C': 2, 'B': 3, 'D': 4, 'E': 5}
    

Разберёмся в коде:

• Выражение sorted(a_dict.items(), key=lambda item: item[1]) возвращает список кортежей [('A', 1), ('C', 2), ('B', 3), ('D', 4), ('E', 5)].
• Далее мы распаковываем кортежи и присваиваем первый элемент каждого кортежа в переменную key, а второй – в переменную value.
• Наконец, сохраняем каждую пару key—value в словаре.

5. enumerate() для значения и индекса

Иногда при переборе списка нужны и значения, и их индексы. Чтобы вдвое ускорить код используйте enumerate() для превращения списка в пары индекс-значение:

        import random
random.seed(666)
a_short_list = [random.randint(0,500) for i in range(5)]

# 1. Получение индексов с помощью использования длины списка
%%time
for i in range(len(a_short_list)):
  print(f'number {i} is {a_short_list[i]}')

# Вывод в консоли:
# number 0 is 233
# number 1 is 462
# number 2 is 193
# number 3 is 222
# number 4 is 145
# CPU times: user 189 μs, sys: 123 μs, total: 312 μs
# Wall time: 214 μs

# 2. Получение индексов с помощью enumerate()
for i, number in enumerate(a_short_list):
  print(f'number {i} is {number}')

# Вывод в консоли:
# number 0 is 233
# number 1 is 462
# number 2 is 193
# number 3 is 222
# number 4 is 145
# CPU times: user 72 μs, sys: 15 μs, total: 87 μs
# Wall time: 90.1 μs


    

6. zip() для перебора нескольких списков

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

        list1 = ['a', 'b', 'c', 'd', 'e']
list2 = ['1', '2', '3', '4', '5']

pairs_list = [pair for pair in zip(list1, list2)]
print(pairs_list)

# Вывод в консоли:
[('a', '1'), ('b', '2'), ('c', '3'), ('d', '4'), ('e', '5')]
    

Обратите внимание, списки должны быть одинаковой длины, так как функция zip() останавливается, когда заканчивается более короткий список.

И наоборот, чтобы получить доступ к элементам каждого кортежа, мы можем распаковать список кортежей, добавив звездочку (*) и используя множественное присваивание:

        # 1. Распаковка списка кортежей с помощью zip()
%%time
letters1, numbers1 = zip(*pairs_list)
print(letters1, numbers1)

# Вывод в консоли:
('a', 'b', 'c', 'd', 'e') ('1', '2', '3', '4', '5')
# CPU times: user 5 μs, sys: 1e+03 ns, total: 6 μs
# Wall time: 6.91 μs

# 2. Распаковка списка кортежей простым перебором
letters2 = [pair[0] for pair in pairs_list]
numbers2 = [pair[1] for pair in pairs_list]
print(letters2, numbers2)

# Вывод в консоли:
['a', 'b', 'c', 'd', 'e'] ['1', '2', '3', '4', '5']
# CPU times: user 5 μs, sys: 1e+03 ns, total: 6 μs
# Wall time: 7.87 μs
    

7. Комбинация set() и in

Если нужно проверить, содержит ли список некоторое значение, можно написать такую неуклюжую функцию:

        import random
random.seed(666)
another_long_list = [random.randint(0,500) for i in range(1000000)]

def check_membership(n):
    for element in another_long_list:
        if element == n:
            return True
    return False
    

Однако есть более характерный для Python способ сделать это – использовать оператор in:

        # 1. Проверка наличия значения в списке перебором элементов
%%time
check_membership(900)

# Вывод в консоль
# CPU times: user 29.7 ms, sys: 847 μs, total: 30.5 ms
# Wall time: 30.2 ms

# 2. Проверка наличия значения в списке с помощью in
900 in another_long_list

# Вывод в консоль
# CPU times: user 10.2 ms, sys: 79 μs, total: 10.3 ms
# Wall time: 10.3 ms
    

Повысить эффективность можно предварительным удалением из списка дубликатов с помощью set. Таким образом, мы сократим количество элементов для проверки. Кроме того, оператор in очень быстро работает с множествами.

        # Убираем дубликаты
check_list = set(another_long_list)

# Вывод в консоль
# CPU times: user 19.8 ms, sys: 204 μs, total: 20 ms
# Wall time: 20 ms

# Проверяем наличие значения в списке
900 in check_list

# Вывод в консоль
# CPU times: user 2 μs, sys: 0 ns, total: 2 μs
# Wall time: 5.25 μs
    

Преобразование списка в множество заняло 20 мс. Но это одноразовые затраты. Зато сама проверка заняла 5 мкс – то есть в 2 тыс. раз меньше, что становится важным при частых обращениях.

8. Проверка на True

Практически в любой программе необходимо проверять, являются ли переменные/списки/словари/… пустыми. На этих проверках тоже можно немножко сэкономить.

Не следует явно указывать == True или is True в условии if, достаточно указать имя проверяемой переменной. Это экономит ресурсы, которые использует «магическая» функция __eq__ для сравнения значений.

        string_returned_from_function = 'Hello World'

# 1. Явная проверка на равенство
%%time
if string_returned_from_function == True:
  pass

# Вывод в консоль
# CPU times: user 3 μs, sys: 0 ns, total: 3 μs
# Wall time: 5.01 μs

# 2. Явная проверка с использованием оператора is
%%time
if string_returned_from_function is True:
  pass

# Вывод в консоль
# CPU times: user 2 μs, sys: 1 ns, total: 3 μs
# Wall time: 4.05 μs

# 3. Неявное равенство
%%time
if string_returned_from_function:
  pass

# Вывод в консоль
# CPU times: user 3 μs, sys: 0 ns, total: 3 μs
# Wall time: 4.05 μs
    

Аналогично можно проверять обратное условие, добавив оператор not:

        if not string_returned_from_function:
  pass
    

9. Подсчет уникальных значений с Counter()

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

        %%time
num_counts = {}
for num in a_long_list:
    if num in num_counts:
        num_counts[num] += 1
    else:
        num_counts[num] = 1

# Вывод в консоль
# CPU times: user 448 ms, sys: 1.77 ms, total: 450 ms
# Wall time: 450 ms
    

Однако более эффективный способ для решения этой задачи – использование Counter() из модуля collections. Весь код при этом уместится в одной строчке:

        %%time
num_counts2 = Counter(a_long_list)

# Вывод в консоль
# CPU times: user 40.7 ms, sys: 329 μs, total: 41 ms
# Wall time: 41.2 ms
    

Этот фрагмент будет работать примерно в 10 раз быстрее, чем предыдущий.

У Counter также есть удобный метод most_common, позволяющий получить самые часто встречающиеся значения:

        for number, count in num_counts2.most_common(10):
  print(number, count)

# Вывод в консоль
29 19831
47 19811
7 19800
36 19794
14 19761
39 19748
32 19747
16 19737
34 19729
33 19729

    

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

10. Цикл for внутри функции

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

        def compute_cubic1(number):
  return number**3

%%time
new_list_cubic1 = [compute_cubic1(number) for number in a_long_list]

# Вывод в консоль
# CPU times: user 335 ms, sys: 14.3 ms, total: 349 ms
# Wall time: 354 ms
    

Однако правильнее будет перевернуть конструкцию – и поместить цикл внутрь функции.

        def compute_cubic2():
  return [number**3 for number in a_long_list]

%%time
new_list_cubic2 = compute_cubic2()

# Вывод в консоль
# CPU times: user 261 ms, sys: 15.7 ms, total: 277 ms
# Wall time: 277 ms
    

В данном примере для миллиона итераций (длина a_long_list) мы сэкономили около 22% времени.

***

Будем рады, если вы поделитесь в комментариях своими подходами к ускорению кода в Python. Вот ещё несколько статей, которые могут вас заинтересовать:

• Не изобретать велосипед, или Обзор модуля collections в Python
• Назад в будущее: практическое руководство по путешествию во времени с Python
• Как написать код, который полюбят все

As we know, Python programming language is a bit slow and the target is to speed it up without the assistance of more extreme solutions, such as C extensions or a just-in-time (JIT) compiler.
While the first rule of optimization might be to “not do it”, the second rule is almost certainly “don’t optimize the unimportant.” To that end, if the program is running slow, one might start by profiling the code. More often than not, one finds that the program spends its time in a few hotspots, such as inner data processing loops. Once those locations are identified, the no-nonsense techniques can be used to make the program run faster. 
A lot of programmers start using Python as a language for writing simple scripts. When writing scripts, it is easy to fall into a practice of simply writing code with very little structure.
Code #1: Taking this code into consideration. 
 

The speed difference depends heavily on the processing being performed, but the speedups of 15-30% are not uncommon.
 

Selectively eliminate attribute access –

Every use of the dot (.) operator to access attributes comes with a cost. Under the covers, this triggers special methods, such as __getattribute__() and __getattr__(), which often lead to dictionary lookups.
One can often avoid attribute lookups by using the from module import name form of import as well as making selected use of bound methods as shown in the code fragment given below – 
Code #3 : 
 

Output : 
 

This program runs in about 40 seconds when running on the machine.

Code #4 : Change the compute_roots() function 
 

Output : 
 

This program runs in about 29 seconds when running on the machine.

The only difference between the two versions of code is the elimination of attribute access. Instead of using math.sqrt(), the code uses sqrt(). The result.append() method is additionally placed into a local variable re 
sult_append and reused in the inner loop. 
However, it must be emphasized that these changes only make sense in frequently executed code, such as loops. So, this optimization really only makes sense in carefully selected places.
 

Understand locality of variables –

As previously noted, local variables are faster than global variables. For frequently accessed names, speedups can be obtained by making those names as local as possible.
Code #5 : Modified version of the compute_roots() function 
 

In this version, sqrt has been lifted from the math module and placed into a local variable. This code will run about 25 seconds (an improvement over the previous version, which took 29 seconds). That additional speedup is due to a local lookup of sqrt being a bit faster than a global lookup of sqrt. 
Locality arguments also apply when working in classes. In general, looking up a value such as self.name will be considerably slower than accessing a local variable. In inner loops, it might pay to lift commonly accessed attributes into a local variable as shown in the code given below. 
Code #6 : 
 

Dynamic Typing:

The reason Python is slow is because it’s dynamically typed now we’re going to talk about this more in detail but I want to give a comparison to a language like Java. Now in Java, everything is statically typed and this language is actually compiled before it runs, unlike Python that’s compiled at runtime through an interpreter. Now what happens in Java is when you write code, you need to define what type each of your variables is going to be, what type your methods and functions are going to be returning and you pretty much have to define exactly what everything’s going to be throughout your code. Now although this leads to much longer development times and takes a much longer time to write your code but what it does is increase efficiency when you are compiling, now the reason this actually works and the reason it works so much faster than Python code is because if you know the type that a specific variable or object is going to be, you can perform a ton of different optimizations and avoid performing a ton of different checks while you’re actually running the code because these checks are performed at compile time in Java essentially you can’t compile any Java code that hasn’t actual or even just like typed errors while you’re writing that code you are going to try to compile it and it would say like this type isn’t accurate, you can’t do this, you can’t compile it because it knows that when it comes to runtime that’s not going to work so essentially all of these checks that actually needs to be performed in Python when the code is running are performed beforehand and there’s just a ton of optimization done because of this statically typed length. Now one may ask a question like, Why doesn’t Python do this? Answer to this would be Python is dynamically typed which simply means that any variable can change its type and can change it’s value at any point in the program while it’s running which means that we can’t actually compile the entire program beforehand because we can’t do all of these checks at once because we don’t know what type these variables are going to be, they are going to change at runtime, different things are going to happen and because of that we can’t get all these optimization that we might have in a lower level language like Java, C or C++ and that is kind of the fundamental reason the language is slow, this dynamic typing and any fast language is going to have a compiler that’s going to run through, it’s going to make sure that everything is good, it’s going to do all these checks before it actually ends up running the code at runtime where what happens in Python is all of your code is actually compiled and checked at runtime so rather than compiling it before and taking all that time beforehand while you’re running the code , many different checks are happening to make sure that say this object is correct, these types are proper, everything is working the same. 

Concurrency:

Now the next thing to talk about is obviously the lack of concurrency in Python. This is going to be the major kind of factor on speed, if you’re writing an application in Java, C, you can spread everything out throughout multiple threads which allows you to utilize all the cores of your CPU so to break this down in modern-day computing most of us have four core CPUs or higher and that allows us to actually run four tasks at the exact same time concurrently now with Python this isn’t possible. Python says, well for each interpreter we can have at most one thread running at a time and a thread is just some kind of operation that’s happening on the CPU core so that means even if we create many threads in our Python program we can only be using one CPU core while in a Java program or a C program could be using all eight or be using all four which will obviously lead to 4X or 8X increase in speed, now we can get around this in Python by using multiprocessing, but there are some issues with that.

This page is devoted to various tips and tricks that help improve the performance of your Python programs. Wherever the information comes from someone else, I’ve tried to identify the source.

Python has changed in some significant ways since I first wrote my «fast python» page in about 1996, which means that some of the orderings will have changed. I migrated it to the Python wiki in hopes others will help maintain it.

You should always test these tips with your application and the specific version of the Python implementation you intend to use and not just blindly accept that one method is faster than another. See the profiling section for more details.

Also new since this was originally written are packages like Cython, Pyrex, Psyco, Weave, Shed Skin and PyInline, which can dramatically improve your application’s performance by making it easier to push performance-critical code into C or machine language.

Other Versions

• Russian: http://omsk.lug.ru/wacko/PythonHacking/PerfomanceTips

Overview: Optimize what needs optimizing

You can only know what makes your program slow after first getting the program to give correct results, then running it to see if the correct program is slow. When found to be slow, profiling can show what parts of the program are consuming most of the time. A comprehensive but quick-to-run test suite can then ensure that future optimizations don’t change the correctness of your program. In short:

1. Get it right.
2. Test it’s right.
3. Profile if slow.
4. Optimise.
5. Repeat from 2.

Certain optimizations amount to good programming style and so should be learned as you learn the language. An example would be moving the calculation of values that don’t change within a loop, outside of the loop.

Choose the Right Data Structure

TBD.

Sorting

Sorting lists of basic Python objects is generally pretty efficient. The sort method for lists takes an optional comparison function as an argument that can be used to change the sorting behavior. This is quite convenient, though it can significantly slow down your sorts, as the comparison function will be called many times. In Python 2.4, you should use the key argument to the built-in sort instead, which should be the fastest way to sort.

Only if you are using older versions of Python (before 2.4) does the following advice from Guido van Rossum apply:

An alternative way to speed up sorts is to construct a list of tuples whose first element is a sort key that will sort properly using the default comparison, and whose second element is the original list element. This is the so-called Schwartzian Transform, also known as DecorateSortUndecorate (DSU).

Suppose, for example, you have a list of tuples that you want to sort by the n-th field of each tuple. The following function will do that.

def sortby(somelist, n):
    nlist = [(x[n], x) for x in somelist]
    nlist.sort()
    return [val for (key, val) in nlist]

Matching the behavior of the current list sort method (sorting in place) is easily achieved as well:

def sortby_inplace(somelist, n):
    somelist[:] = [(x[n], x) for x in somelist]
    somelist.sort()
    somelist[:] = [val for (key, val) in somelist]
    return

Here’s an example use:

>>> somelist = [(1, 2, 'def'), (2, -4, 'ghi'), (3, 6, 'abc')]
>>> somelist.sort()
>>> somelist
[(1, 2, 'def'), (2, -4, 'ghi'), (3, 6, 'abc')]
>>> nlist = sortby(somelist, 2)
>>> sortby_inplace(somelist, 2)
>>> nlist == somelist
True
>>> nlist = sortby(somelist, 1)
>>> sortby_inplace(somelist, 1)
>>> nlist == somelist
True

From Tim Delaney

From Python 2.3 sort is guaranteed to be stable.

(to be precise, it’s stable in CPython 2.3, and guaranteed to be stable in Python 2.4)

Python 2.4 adds an optional key parameter which makes the transform a lot easier to use:

# E.g. n = 1
n = 1
import operator
nlist.sort(key=operator.itemgetter(n))
# use sorted() if you don't want to sort in-place:
# sortedlist = sorted(nlist, key=operator.itemgetter(n))

Note that the original item is never used for sorting, only the returned key — this is equivalent to doing:

# E.g. n = 1
n = 1
nlist = [(x[n], i, x) for (i, x) in enumerate(nlist)]
nlist.sort()
nlist = [val for (key, index, val) in nlist]

String Concatenation

The accuracy of this section is disputed with respect to later versions of Python. In CPython 2.5, string concatenation is fairly fast, although this may not apply likewise to other Python implementations. See ConcatenationTestCode for a discussion.

Strings in Python are immutable. This fact frequently sneaks up and bites novice Python programmers on the rump. Immutability confers some advantages and disadvantages. In the plus column, strings can be used as keys in dictionaries and individual copies can be shared among multiple variable bindings. (Python automatically shares one- and two-character strings.) In the minus column, you can’t say something like, «change all the ‘a’s to ‘b’s» in any given string. Instead, you have to create a new string with the desired properties. This continual copying can lead to significant inefficiencies in Python programs.

Avoid this:

s = ""
for substring in list:
    s += substring

Use s = «».join(list) instead. The former is a very common and catastrophic mistake when building large strings. Similarly, if you are generating bits of a string sequentially instead of:

s = ""
for x in list:
    s += some_function(x)

use

slist = [some_function(elt) for elt in somelist]
s = "".join(slist)

Avoid:

out = "<html>" + head + prologue + query + tail + "</html>"

Instead, use

out = "<html>%s%s%s%s</html>" % (head, prologue, query, tail)

Even better, for readability (this has nothing to do with efficiency other than yours as a programmer), use dictionary substitution:

out = "<html>%(head)s%(prologue)s%(query)s%(tail)s</html>" % locals()

This last two are going to be much faster, especially when piled up over many CGI script executions, and easier to modify to boot. In addition, the slow way of doing things got slower in Python 2.0 with the addition of rich comparisons to the language. It now takes the Python virtual machine a lot longer to figure out how to concatenate two strings. (Don’t forget that Python does all method lookup at runtime.)

Loops

Python supports a couple of looping constructs. The for statement is most commonly used. It loops over the elements of a sequence, assigning each to the loop variable. If the body of your loop is simple, the interpreter overhead of the for loop itself can be a substantial amount of the overhead. This is where the map function is handy. You can think of map as a for moved into C code. The only restriction is that the «loop body» of map must be a function call. Besides the syntactic benefit of list comprehensions, they are often as fast or faster than equivalent use of map.

Here’s a straightforward example. Instead of looping over a list of words and converting them to upper case:

newlist = []
for word in oldlist:
    newlist.append(word.upper())

you can use map to push the loop from the interpreter into compiled C code:

newlist = map(str.upper, oldlist)

List comprehensions were added to Python in version 2.0 as well. They provide a syntactically more compact and more efficient way of writing the above for loop:

newlist = [s.upper() for s in oldlist]

Generator expressions were added to Python in version 2.4. They function more-or-less like list comprehensions or map but avoid the overhead of generating the entire list at once. Instead, they return a generator object which can be iterated over bit-by-bit:

iterator = (s.upper() for s in oldlist)

Which method is appropriate will depend on what version of Python you’re using and the characteristics of the data you are manipulating.

Guido van Rossum wrote a much more detailed (and succinct) examination of loop optimization that is definitely worth reading.

Avoiding dots…

Suppose you can’t use map or a list comprehension? You may be stuck with the for loop. The for loop example has another inefficiency. Both newlist.append and word.upper are function references that are reevaluated each time through the loop. The original loop can be replaced with:

upper = str.upper
newlist = []
append = newlist.append
for word in oldlist:
    append(upper(word))

This technique should be used with caution. It gets more difficult to maintain if the loop is large. Unless you are intimately familiar with that piece of code you will find yourself scanning up to check the definitions of append and upper.

Local Variables

The final speedup available to us for the non-map version of the for loop is to use local variables wherever possible. If the above loop is cast as a function, append and upper become local variables. Python accesses local variables much more efficiently than global variables.

def func():
    upper = str.upper
    newlist = []
    append = newlist.append
    for word in oldlist:
        append(upper(word))
    return newlist

At the time I originally wrote this I was using a 100MHz Pentium running BSDI. I got the following times for converting the list of words in /usr/share/dict/words (38,470 words at that time) to upper case:

Version Time (seconds)
Basic loop 3.47
Eliminate dots 2.45
Local variable & no dots 1.79
Using map function 0.54

Initializing Dictionary Elements

Suppose you are building a dictionary of word frequencies and you’ve already broken your text up into a list of words. You might execute something like:

wdict = {}
for word in words:
    if word not in wdict:
        wdict[word] = 0
    wdict[word] += 1

Except for the first time, each time a word is seen the if statement’s test fails. If you are counting a large number of words, many will probably occur multiple times. In a situation where the initialization of a value is only going to occur once and the augmentation of that value will occur many times it is cheaper to use a try statement:

wdict = {}
for word in words:
    try:
        wdict[word] += 1
    except KeyError:
        wdict[word] = 1

It’s important to catch the expected KeyError exception, and not have a default except clause to avoid trying to recover from an exception you really can’t handle by the statement(s) in the try clause.

A third alternative became available with the release of Python 2.x. Dictionaries now have a get() method which will return a default value if the desired key isn’t found in the dictionary. This simplifies the loop:

wdict = {}
get = wdict.get
for word in words:
    wdict[word] = get(word, 0) + 1

When I originally wrote this section, there were clear situations where one of the first two approaches was faster. It seems that all three approaches now exhibit similar performance (within about 10% of each other), more or less independent of the properties of the list of words.

Also, if the value stored in the dictionary is an object or a (mutable) list, you could also use the dict.setdefault method, e.g.

   4     wdict.setdefault(key, []).append(new_element)

You might think that this avoids having to look up the key twice. It actually doesn’t (even in python 3.0), but at least the double lookup is performed in C.

Another option is to use the defaultdict class:

from collections import defaultdict

wdict = defaultdict(int)

for word in words:
    wdict[word] += 1

Import Statement Overhead

import statements can be executed just about anywhere. It’s often useful to place them inside functions to restrict their visibility and/or reduce initial startup time. Although Python’s interpreter is optimized to not import the same module multiple times, repeatedly executing an import statement can seriously affect performance in some circumstances.

Consider the following two snippets of code (originally from Greg McFarlane, I believe — I found it unattributed in a comp.lang.python python-list@python.org posting and later attributed to him in another source):

def doit1():
    import string ###### import statement inside function
    string.lower('Python')

for num in range(100000):
    doit1()

or:

import string ###### import statement outside function
def doit2():
    string.lower('Python')

for num in range(100000):
    doit2()

doit2 will run much faster than doit1, even though the reference to the string module is global in doit2. Here’s a Python interpreter session run using Python 2.3 and the new timeit module, which shows how much faster the second is than the first:

>>> def doit1():
... import string
... string.lower('Python')
...
>>> import string
>>> def doit2():
... string.lower('Python')
...
>>> import timeit
>>> t = timeit.Timer(setup='from __main__ import doit1', stmt='doit1()')
>>> t.timeit()
11.479144930839539
>>> t = timeit.Timer(setup='from __main__ import doit2', stmt='doit2()')
>>> t.timeit()
4.6661689281463623

String methods were introduced to the language in Python 2.0. These provide a version that avoids the import completely and runs even faster:

def doit3():
    'Python'.lower()

for num in range(100000):
    doit3()

Here’s the proof from timeit:

>>> def doit3():
... 'Python'.lower()
...
>>> t = timeit.Timer(setup='from __main__ import doit3', stmt='doit3()')
>>> t.timeit()
2.5606080293655396

The above example is obviously a bit contrived, but the general principle holds.

Note that putting an import in a function can speed up the initial loading of the module, especially if the imported module might not be required. This is generally a case of a «lazy» optimization — avoiding work (importing a module, which can be very expensive) until you are sure it is required.

This is only a significant saving in cases where the module wouldn’t have been imported at all (from any module) — if the module is already loaded (as will be the case for many standard modules, like string or re), avoiding an import doesn’t save you anything. To see what modules are loaded in the system look in sys.modules.

A good way to do lazy imports is:

email = None

def parse_email():
    global email
    if email is None:
        import email
    ...

This way the email module will only be imported once, on the first invocation of parse_email().

Data Aggregation

Function call overhead in Python is relatively high, especially compared with the execution speed of a builtin function. This strongly suggests that where appropriate, functions should handle data aggregates. Here’s a contrived example written in Python.

import time
x = 0
def doit1(i):
    global x
    x = x + i

list = range(100000)
t = time.time()
for i in list:
    doit1(i)

print "%.3f" % (time.time()-t)

vs.

import time
x = 0
def doit2(list):
    global x
    for i in list:
        x = x + i

list = range(100000)
t = time.time()
doit2(list)
print "%.3f" % (time.time()-t)

Here’s the proof in the pudding using an interactive session:

>>> t = time.time()
>>> for i in list:
... doit1(i)
...
>>> print "%.3f" % (time.time()-t)
0.758
>>> t = time.time()
>>> doit2(list)
>>> print "%.3f" % (time.time()-t)
0.204

Even written in Python, the second example runs about four times faster than the first. Had doit been written in C the difference would likely have been even greater (exchanging a Python for loop for a C for loop as well as removing most of the function calls).

Doing Stuff Less Often

The Python interpreter performs some periodic checks. In particular, it decides whether or not to let another thread run and whether or not to run a pending call (typically a call established by a signal handler). Most of the time there’s nothing to do, so performing these checks each pass around the interpreter loop can slow things down. There is a function in the sys module, setcheckinterval, which you can call to tell the interpreter how often to perform these periodic checks. Prior to the release of Python 2.3 it defaulted to 10. In 2.3 this was raised to 100. If you aren’t running with threads and you don’t expect to be catching many signals, setting this to a larger value can improve the interpreter’s performance, sometimes substantially.

Python is not C

It is also not Perl, Java, C++ or Haskell. Be careful when transferring your knowledge of how other languages perform to Python. A simple example serves to demonstrate:

% timeit.py -s 'x = 47' 'x * 2'
loops, best of 3: 0.574 usec per loop
% timeit.py -s 'x = 47' 'x << 1'
loops, best of 3: 0.524 usec per loop
% timeit.py -s 'x = 47' 'x + x'
loops, best of 3: 0.382 usec per loop

Now consider the similar C programs (only the add version is shown):

#include <stdio.h>

int main (int argc, char *argv[]) {
 int i = 47;
 int loop;
 for (loop=0; loop<500000000; loop++)
  i + i;
 return 0;
}

and the execution times:

% for prog in mult add shift ; do
< for i in 1 2 3 ; do
< echo -n "$prog: "
< /usr/bin/time ./$prog
< done
< echo
< done
mult: 6.12 real 5.64 user 0.01 sys
mult: 6.08 real 5.50 user 0.04 sys
mult: 6.10 real 5.45 user 0.03 sys

add: 6.07 real 5.54 user 0.00 sys
add: 6.08 real 5.60 user 0.00 sys
add: 6.07 real 5.58 user 0.01 sys

shift: 6.09 real 5.55 user 0.01 sys
shift: 6.10 real 5.62 user 0.01 sys
shift: 6.06 real 5.50 user 0.01 sys

Note that there is a significant advantage in Python to adding a number to itself instead of multiplying it by two or shifting it left by one bit. In C on all modern computer architectures, each of the three arithmetic operations are translated into a single machine instruction which executes in one cycle, so it doesn’t really matter which one you choose.

A common «test» new Python programmers often perform is to translate the common Perl idiom

while (<>) {
    print;
}

into Python code that looks something like

import fileinput

for line in fileinput.input():
    print line,

and use it to conclude that Python must be much slower than Perl. As others have pointed out numerous times, Python is slower than Perl for some things and faster for others. Relative performance also often depends on your experience with the two languages.

Use xrange instead of range

This section no longer applies if you’re using Python 3, where range now provides an iterator over ranges of arbitrary size, and where xrange no longer exists.

Python has two ways to get a range of numbers: range and xrange. Most people know about range, because of its obvious name. xrange, being way down near the end of the alphabet, is much less well-known.

xrange is a generator object, basically equivalent to the following Python 2.3 code:

def xrange(start, stop=None, step=1):
    if stop is None:
        stop = start
        start = 0
    else:
        stop = int(stop)
    start = int(start)
    step = int(step)

    while start < stop:
        yield start
        start += step

Except that it is implemented in pure C.

xrange does have limitations. Specifically, it only works with ints; you cannot use longs or floats (they will be converted to ints, as shown above).

It does, however, save gobs of memory, and unless you store the yielded objects somewhere, only one yielded object will exist at a time. The difference is thus: When you call range, it creates a list containing so many number (int, long, or float) objects. All of those objects are created at once, and all of them exist at the same time. This can be a pain when the number of numbers is large.

xrange, on the other hand, creates no numbers immediately — only the range object itself. Number objects are created only when you pull on the generator, e.g. by looping through it. For example:

xrange(sys.maxint) # No loop, and no call to .next, so no numbers are instantiated

And for this reason, the code runs instantly. If you substitute range there, Python will lock up; it will be too busy allocating sys.maxint number objects (about 2.1 billion on the typical PC) to do anything else. Eventually, it will run out of memory and exit.

In Python versions before 2.2, xrange objects also supported optimizations such as fast membership testing (i in xrange(n)). These features were removed in 2.2 due to lack of use.

Re-map Functions at runtime

Say you have a function

 class Test:
   def check(self,a,b,c):
     if a == 0:
       self.str = b*100
     else:
       self.str = c*100

 a = Test()
 def example():
   for i in xrange(0,100000):
     a.check(i,"b","c")

 import profile
 profile.run("example()")

And suppose this function gets called from somewhere else many times.

Well, your check will have an if statement slowing you down all the time except the first time, so you can do this:

 class Test2:
   def check(self,a,b,c):
     self.str = b*100
     self.check = self.check_post
   def check_post(self,a,b,c):
     self.str = c*100

 a = Test2()
 def example2():
   for i in xrange(0,100000):
     a.check(i,"b","c")

 import profile
 profile.run("example2()")

Well, this example is fairly inadequate, but if the ‘if’ statement is a pretty complicated expression (or something with lots of dots), you can save yourself evaluating it, if you know it will only be true the first time.

Profiling Code

The first step to speeding up your program is learning where the bottlenecks lie. It hardly makes sense to optimize code that is never executed or that already runs fast. I use two modules to help locate the hotspots in my code, profile and trace. In later examples I also use the timeit module, which is new in Python 2.3.

The advice in this section is out of date. See the separate profiling document for alternatives to the approaches given below.

Profiling

There are a number of profiling modules included in the Python distribution. Using one of these to profile the execution of a set of functions is quite easy. Suppose your main function is called main, takes no arguments and you want to execute it under the control of the profile module. In its simplest form you just execute

import profile
profile.run('main()')

When main() returns, the profile module will print a table of function calls and execution times. The output can be tweaked using the Stats class included with the module. From Python 2.4, profile has permitted the time consumed by Python builtins and functions in extension modules to be profiled as well.

A slightly longer description of profiling using the profile and pstats modules can be found here (archived version):

http://web.archive.org/web/20060506162444/http://wingware.com/doc/howtos/performance-profiling-python-code

The cProfile Module

The `cProfile` module is an alternative to profile written in C that generally runs much faster. It uses the same interface.

Trace Module

The trace module is a spin-off of the profile module I wrote originally to perform some crude statement level test coverage. It’s been heavily modified by several other people since I released my initial crude effort. As of Python 2.0 you should find trace.py in the Tools/scripts directory of the Python distribution. Starting with Python 2.3 it’s in the standard library (the Lib directory). You can copy it to your local bin directory and set the execute permission, then execute it directly. It’s easy to run from the command line to trace execution of whole scripts:

% trace.py -t spam.py eggs

In Python 2.4 it’s even easier to run. Just execute python -m trace.

There’s no separate documentation, but you can execute «pydoc trace» to view the inline documentation.

Visualizing Profiling Results

RunSnakeRun is a GUI tool by Mike Fletcher which visualizes profile dumps from cProfile using square maps. Function/method calls may be sorted according to various criteria, and source code may be displayed alongside the visualization and call statistics. Currently (April 2016) RunSnakeRun supports Python 2.x only — thus it cannot load profile data generated by Python 3 programs.

An example usage:

runsnake some_profile_dump.prof

Gprof2Dot is a python based tool that can transform profiling results output into a graph that can be converted into a PNG image or SVG.

A typical profiling session with python 2.5 looks like this (on older platforms you will need to use actual script instead of the -m option):

python -m cProfile -o stat.prof MYSCRIPY.PY [ARGS...]
python -m pbp.scripts.gprof2dot -f pstats -o stat.dot stat.prof
dot -ostat.png -Tpng stat.dot

PyCallGraph pycallgraph is a Python module that creates call graphs for Python programs. It generates a PNG file showing an modules’s function calls and their link to other function calls, the amount of times a function was called and the time spent in that function.

Typical usage:

pycallgraph scriptname.py

PyProf2CallTree is a script to help visualize profiling data collected with the cProfile python module with the kcachegrind graphical calltree analyser.

Typical usage:

python -m cProfile -o stat.prof MYSCRIPY.PY [ARGS...]
python pyprof2calltree.py -i stat.prof -k

ProfileEye is a browser-based frontend to gprof2dot using d3.js for decluttering visual information.

Typical usage:

python -m profile -o output.pstats path/to/your/script arg1 arg2
gprof2dot -f pstats output.pstats | profile_eye --file-colon_line-colon-label-format > profile_output.html

SnakeViz is a browser-based visualizer for profile data.

Typical usage:

python -m profile -o output.pstats path/to/your/script arg1 arg2
snakeviz output.pstats

---

CategoryDocumentation