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

Представим себе совершенно стандартную ситуацию: с помощью input() мы получаем строку, состоящую из чисел, записанных через пробел:

0 1 2 3 4 5 6 7 8 9 10

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

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

###Подготовка

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

Надо учитывать, что строка, которую нам придется обрабатывать, может быть очень длинной, например, содержать в себе 1000 чисел Фибоначчи:

def fib(n):
  x, y = 0, 1
  while n:
    yield x
    x, y = y, x + y
    n -= 1

def fib_string():
  fib_str = ''
  for i in fib(1000):
    fib_str = '%s %s' % (fib_str, str(i)) if fib_str else str(i)
  return fib_str

print(fib_string())

Полученную строку мы и будем использовать в дальнейших примерах.

###Варианты

Самый первый, который приходит на ум – это с использованием map().

Данная встроенная функция основана на применении итерационного протокола. Она представляет собой инструмент, вызывающий заданную функцию для каждого элемента итерируемого объекта, а возвращает итерируемый объект, вместо того, чтобы воспроизводить сразу весь список с результатами. По нему можно пройтись, например, элементарным for, но это получится только один раз, для последующего прохода нужно будет снова создавать итератор. Проще говоря, поведение map() ориентировано на экономию существенных объемов оперативной памяти, что нам и пригодится.

def mk(fib_str):
  return map(int, fib_str.split())

Данная функция возвращает объект-генератор, который мы смело скормим list(). Что нам может здесь не понравится, так это fib_str.split(), создастся новый список из строк, забьется память.

import sys
sum(sys.getsizeof(x) for x in fib_str.split()) # 153542

Вспомним, что для контейнерных объектов, таких как списки, кортежи и словари, sys.getsizeof() возвращает размер памяти в байтах, занимаемый самим контейнером, а не суммарный объем памяти, занимаемой всеми элементами контейнера. Именно поэтому мы использовали sum().

В следующем варианте – используем выражение-генератор:

def fk(fib_str):
  return (int(i) for i in fib_str.split())

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

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

def gk(fib_str):
  return [int(i) for i in fib_str.split()]

Генератор списков – это способ построить новый список, применяя выражение к каждому элементу последовательности. Более того, генераторы списков могут выполняться значительно быстрее, чем инструкции циклов for, потому что итерации выполняются со скоростью языка C, а не со скоростью программного кода на языке Python. В отличие от выражений-генераторов, генераторы списков создают списки, содержащие результаты вычислений, а не воспроизводят данные по требованию.

В итоге к нам придет готовый список, а это значит, что память забьется:

import sys
sum(sys.getsizeof(x) for x in gk(fib_str)) # 72088

Последний вариант – все очень хорошо, если бы split() создавал объект-генератор, но он этого не делает, поэтому напишем свою функцию-генератор:

def inum(fib_str):
  num = ''
  for index, i in enumerate(fib_str):
    num = num + i
    if i == ' ' or index == len(fib_str)-1:
      yield int(num)
      num = ''

Единственное их отличие от обычных функций – они автоматически поддерживают протокол итераций и могут использоваться в контексте итераций (yield вместо return).

###Сравнение

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

Итак, сейчас посмотрим на время создания объекта-генератора:

%timeit mk(fib_str)
1000 loops, best of 3: 367 µs per loop

%timeit fk(fib_str)
1000 loops, best of 3: 370 µs per loop

%timeit inum(fib_str)
1000000 loops, best of 3: 558 ns per loop

Проще говоря, inum() - 0.558 µs, mk() - 367 µs, а fk() - 370 µs. Понятное дело, драгоценное время тратит split(), от которого мы избавились в inum(). gk() сразу создаст список, поэтому сейчас он нас не интересует.

Наконец, создадим список, состоящий из целых чисел:

mk_list = list(mk(fib_str))
fk_list = list(fk(fib_str))
gk_list = gk(fib_str)
inum_list = list(inum(fib_str))

Результаты:

%timeit list(mk(fib_str))
1000 loops, best of 3: 1.74 ms per loop

%timeit list(fk(fib_str))
1000 loops, best of 3: 1.93 ms per loop

%timeit gk(fib_str)
1000 loops, best of 3: 1.86 ms per loop

%timeit list(inum(fib_str))
10 loops, best of 3: 70 ms per loop

Вдруг inum() показывает совершенно другой результат. Поздравляю, если вы в самом начале догадались, почему, а если нет, то посмотрим на общее число вызовов, общее время, потраченное на выполнение функций. Запустим cProfile:

python3 -m cProfile -s cumtime test.py 
         107556 function calls in 0.114 seconds

   Ordered by: cumulative time

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.000    0.000    0.114    0.114 {built-in method exec}
     1    0.002    0.002    0.114    0.114 test.py:1(<module>)
  1001    0.079    0.000    0.093    0.000 test.py:23(inum)
104542    0.014    0.000    0.014    0.000 {built-in method len}
     1    0.010    0.010    0.011    0.011 test.py:8(fib_string)
     3    0.003    0.001    0.003    0.001 {method 'split' of 'str' objects}
  1001    0.003    0.000    0.003    0.000 test.py:18(<genexpr>)
     1    0.000    0.000    0.002    0.002 test.py:17(fk)
     1    0.000    0.000    0.002    0.002 test.py:20(gk)
     1    0.002    0.002    0.002    0.002 test.py:21(<listcomp>)
  1001    0.001    0.000    0.001    0.000 test.py:1(fib)
     1    0.000    0.000    0.000    0.000 test.py:14(mk)
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Как мы видим, inum() вызывается столько же раз, сколько и return в fk(), только выполняется значительно дольше, чего нельзя сказать о mk().

###Вывод

Что по этому поводу пишет нам Лутц:

Современная реализация map() выполняется быстрее, чем любой цикл for, и обладает более высокой производительностью, чем генераторы списков. Выражения-генераторы в первую очередь оптимизируют использование памяти – они не требуют создания в памяти полного списка с результатами. Кроме того, на практике они могут работать несколько медленнее, поэтому их лучше использовать, только когда объем результатов очень велик.

Однако, Бизли так не считает:

Вместо функции map() практически всегда лучше использовать выражения-генераторы или генераторы списков (которые обладают более высокой производительностью).

Прежде чем использовать тот или иной вариант, проведите хронометраж кода на своем компьютере, со своей версией Python. В моем случае выиграл достаточно лаконичный и простой вариант с map().

###Список используемой литературы

  • Марк Лутц “Изучаем Python”, стр. 257, 426, 429, 435, 555-556, 568, 573-574, 590
  • Дэвид Бизли “Python. Подробный справочник”, стр. 150, 250, 267