Функциональное программирование на Python. Часть 6. Ленивость. Пакет itertools

Автор: | 18.06.2020

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

Немного теории

Нормальный и аппликативный порядок вычисления

Для начала обратимся к теории языков программирования, а именно к теме стратегий вычисления. Начнем с простого примера, рассмотрим функцию:

\( f(x,y) = (x+y)^2\) 

Перепишем ее определение следующим образом:

\(sq(x) = x*x\) 

\(f(x,y) = sq(x+y)\) 

Значение функции на аргументах 3 и 2 можно вычислить двумя способами.

Первый:

\(f(3, 2) = sq(3+2)\) 

\(f(3, 2) = (3+2)*(3+2)\) 

\(f(3, 2) = 5*(3+2)\) 

\(f(3, 2) = 5*5\) 

\(f(3, 2) = 25\) 

Второй:

\(f(3, 2) = sq(3+2)\) 

\(f(3, 2) = sq(5)\) 

\(f(3, 2) = 5*5\) 

\(f(3, 2) = 25\) 

В первом случае, мы сначала применили функцию, и только после того, как дальнейшее применение стало невозможно, начали вычислять аргументы. Во втором – наоборот: мы сначала вычислили аргументы, а потом стали применять функцию. Стратегия вычисления, реализующая первый подход, называется нормальная, она, чаще всего, используется в функциональных языках программирования, например, Haskell. Стратегия, реализующая второй вариант, носит название аппликативная, используется в большинстве языков программирования. Можно также услышать термин “ленивые вычисления“, когда имеют ввиду нормальный порядок, и “энергичные вычисления” если речь идет об аппликативном порядке.

Преимущества и недостатки подходов

Каждый из представленных выше порядков вычислений имеет свои преимущества и недостатки. Сравним их между собой.

Лямбда-исчисление

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

Эффективность в вычислительном плане и по памяти

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

Пример на Haskell:

Prelude> take 5 [1..100]
[1,2,3,4,5]

Функция take извлекает 5 элементов из переданного ей списка. Благодаря ленивости, Haskell не строит предварительно список из 100 элементов для того, чтобы потом воспользоваться только пятью первыми.

В Python можно делать похожие вещи, для этого нужно воспользоваться генератором. Создадим аналог функции take:

import itertools 

take = lambda n, x: list(itertools.islice(x, n))

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

start = time.time()
take(5, [i for i in range(1_000_000)])
end = time.time()

print(end - start)

В результате получим значение примерно равное 0.05 секунд.

Добавим “ленивости” в наш код, превратим классическое списковое включение в генератор:

start = time.time()
take(5, (i for i in range(1_000_000)))
end = time.time()

print(end - start)

Время выполнения: 2.86e-05 секунд.

Если увеличим количество элементов в списке до 10_000_000, то в первом случае время выполнения возрастет до 0.5, во втором не изменится. Все элементы, которые создаются, перед тем как будут переданы в функцию take в первом примере, хранятся в памяти, во втором – элементы, создаются по мере необходимости.

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

\( f(x) = x + x + x + x + x\) 

Если использовать ленивый порядок вычислений, то на аргументе 3+4 получим следующий результат:

\(f(3+4) = (3+4)+(3+4)+(3+4)+(3+4)+(3+4)\) 

\(f(3+4) = 7+(3+4)+(3+4)+(3+4)+(3+4)\) 

\(f(3+4) = 7+7+(3+4)+(3+4)+(3+4)\) 

\(f(3+4) = 7+7+7+7+7\) 

\(f(3+4) = 35\) 

Нам пришлось пять раз вычислить сумму 3+4. Может для данного примера это и не критично, но таких вычислений может понадобиться не пять, а намного больше. Да и аргументом функции может быть не простое арифметическое выражение, а функция, для вычисления которой требуется много временных или вычислительных ресурсов. Например, если в f передать не 3+4, а результат обращения к базе данных: f(get_data_from_db(db_name)), то вместо одного обращения (в случае аппликативного порядка) мы получим пять.

Для аппликативного порядка, вычисление f(3+4) будет выглядеть так:

\(f(3+4) = 7+7+7+7+7\) 

\(f(3+4) = 35\) 

Работа с бесконечными списками

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

Модифицируем наш пример на Haskell:

Prelude> take 5 [1..]
[1,2,3,4,5]

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

def infinit_list():
   i = 0
   while True:
       yield i
       i += 1

Передадим наш “бесконечный список” в функцию take:

>>> take(5, infinit_list())
[0, 1, 2, 3, 4]

Итераторы и генераторы

По теме итераторов и генераторов на нашем сайте есть отдельная статья, с которой рекомендуем вам ознакомиться: Урок 15. Итераторы и генераторы.

Ниже приведена краткая справка по этой теме.

Если какой-то объект может выступать в роли итератора (реализует протокол итератора), то его (итератор) можно получить из данного объекта с помощью функции iter(). Пример:

>>> a = [1,2,3]
>>> ai = iter(a)
>>> ai
<list_iterator object at 0x7f6f36a2a890>

>>> a
[1, 2, 3]

Для извлечения элементов из итератора используется функция next():

>>> next(ai)
1

Если количество элементов в нем ограничено, то будет выброшено исключение StopIteration

>>> next(ai)
1

>>> next(ai)
2

>>> next(ai)
3

>>> next(ai)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Если вы проектируете класс, объекты которого будут итераторами, то в него необходимо добавить методы __iter__(), который возвращает self, и __next__(), который возвращает какие-либо значения.

Пример простого итератора:

class SimpleIterator:
   def __iter__(self):
       return self

   def __init__(self):
       self.tmp = -1

   def __next__(self):
       self.tmp += 1
       return self.tmp

Демонстрация работы с SimpleIterator:

>>> si = SimpleIterator()
>>> next(si)
0

>>> next(si)
1

Генератор – это синтаксический сахар для построения итераторов. Приведем реализацию, аналогичную по функционалу SimpleIterator, с помощью генератора:

def simple_generator():
   tmp = 0
   while True:
       yield tmp
       tmp += 1

Демонстрация работы с simple_generator():

>>> sg = simple_generator()
>>> next(sg)
0

>>> next(sg)
1

Итераторы позволяют строить ленивые вычисления. Например, функции для работы с последовательностями map(), filter(), range(), zip() и т.п. возвращают итератор. Это позволяет не выполнять весь объем вычислений над всем списком, а выдавать результаты по мере необходимости:

>>> a = [1, 2, 3]
>>> a_sq = map(lambda x: x**2, a)
>>> next(a_sq)
1

>>> next(a_sq)
4

>>> next(a_sq)
9

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

Воспользуемся уже знакомой нам функцией take:

take = lambda n, x: list(itertools.islice(x, n))

Пример максимально энергичных вычислений:

start = time.time()
a = [i for i in range(1_000_000)]
take(5, list(map(lambda x: x+100, a)))
end = time.time()

print(end - start)

Время выполнения примерно 0.130 секунд.

Сделаем вычисления как можно более ленивыми:

start = time.time()
a_i = (i for i in range(1_000_000))
take(5, map(lambda x: x+100, a_i))
end = time.time()

print(end - start)

Время выполнения 2.8e-05 секунд.

Идея итераторов в Python нашла свое развитие в пакете itertools, которому посвящен следующий раздел.

Пакет itertools

Функции из пакета itertools делятся на три группы:

  • Бесконечные итераторы.
  • Итераторы с терминацией.
  • Комбинаторные итераторы.

Бесконечные итераторы

Данная группа включает в себя функции, перечисленные в таблице ниже.

Функция Описание
count() Возвращает последовательность чисел, начиная с заданного значения с определенным шагом.
cycle() Возвращает зацикленную бесконечную последовательность.
repeate() Возвращает переданный ей объект бесконечное либо заданное количество раз.

count() 

Функция возвращает последовательность чисел, начиная с заданного значения с определенным шагом:

count() -> 0 1 2 3 4 …

count(5, 5) -> 5 10 15 20 25 …

Прототип функции:

count(start=0, step=1)

Параметры:

  • start
    • Стартовое значение числовой последовательности.
  • step
    • Шаг числовой последовательности.

Примеры:

>>> c = count(0)
>>> next(c)
0

>>> next(c)
1

>>> c2 = count(10, 7)
>>> next(c2)
10

>>> next(c2)
17


>>> list(zip("abc", count(0, 5)))

[('a', 0), ('b', 5), ('c', 10)]

cycle() 

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

cycle([1,2,3]) -> 1 2 3 1 2 3 1 2 3 …

cycle(“abc”) -> a b c a b c …

Прототип функции:

cycle(iterable)

Параметры:

  • iterable
    • Итератор: источник базовой последовательности.

Примеры:

>>> cyc = cycle([1,2,3])
>>> for _ in range(5):
...     print(next(cyc))
... 
1
2
3
1
2

repeate()

Возвращает переданный функции объект бесконечное количество раз, либо заданное, если передан соответствующий аргумент:

repeat(1) -> 1  1 1 1 1 1….

repeat(‘a’, 5) -> a a a a a

Прототип функции:

repeat(object[, times])

Параметры функции:

  • object
    • Объект, генерация которого будет производится.
  • times
    • Количество раз, которые итератор должен выдать переданный объект.

Примеры:

>>> r = repeat(1)
>>> next(r)
1

>>> next(r)
1

>>> next(r)
1

>>> r_lim = repeat('abc', 3)
>>> next(r_lim)
'abc'

>>> next(r_lim)
'abc'

>>> next(r_lim)
'abc'

>>> next(r_lim)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Итераторы с терминацией

Функция Описание
accumulate() Аккумулирует значения переданного итератора.
chain() Выдает последовательно данные из переданных итераторов.
chain.from_iterable() Аналогична функции chain(), только работает не с отдельными итераторами, а с итератором, элементами которого являются другие итераторы.
compress() Фильтрует (сжимает) исходный набор данных.
dropwhile() Отбрасывает элементы итератора до тех пор, пока выполняется предикат.
filterfalse() Функция отбрасывает элементы итератора, для которых выполняется предикат.
groupby() Группирует элементы из переданного ей итератора в соответствии с заданным правилом.
islice() Создает итератор, который возвращает выбранные элементы из исходного итератора.
starmap() Выполняет применение функции к элементам переданного итератора.
takewhile() Извлекает элементы из входного итератора до тех пор пока выполняется предикат.
tee() Создает заданное количество итераторов из исходного.
zip_longest() Создает итератор из элементов исходных итераторов.

accumulate()

Аккумулирует значения переданного итератора. По умолчанию используется операция суммирования:

accumulate([1,2,3]) -> 1 3 6

accumulate([1,2,3], func=sub) -> 1 -1 -4

Прототип функции:

accumulate(iterable[, func, *, initial=None])

Параметры функции:

  • iterable
    • Исходный итератор, с элементами которого будет производиться работа.
  • func
    • Функция, с помощью которой будет выполняться аккумуляция результатов (по умолчанию operator.add).
  • initial
    • Начальное значение выходной последовательности. Если аргумент равен None, то будет использован первый элемент из iterable. Данный параметр доступен в python 3.8.

Примеры:

>>> list(accumulate([1,2,3]) )
[1, 3, 6]

>>> from operator import sub
>>> list(accumulate([1,2,3], func=sub, initial=10) )
[10, 9, 7, 4]

chain()

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

chain([1,2,3], [4,5,6]) -> 1 2 3 4 5 6

Прототип функции:

chain(*iterables)

Параметры функции:

  • *iterables
    • Итераторы.

Примеры:

>>> list(chain([1,2,3], ["a", "b", "c"]))
[1, 2, 3, 'a', 'b', 'c']

chain.from_iterable()

Функция аналогичная рассмотренной выше chain(), только она на вход получает не набор отдельных итераторов, а один итератор, элементами которого являются итераторы:

chain.from_iterable([[1,2,3], “abc”]) -> 1 2 3 a b c

Прототип функции:

chain.from_iterable(iterable)

Параметры функции:

  • iterable
    • Итератор, элементами которого являются итераторы.

Примеры:

>>> cf = chain.from_iterable([[1,2,3], (4,5), "abc"])
>>> list(cf)
[1, 2, 3, 4, 5, 'a', 'b', 'c']

compress()

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

compress(“abcdef”, [1, 0, 1, 1, 0, 1]) -> a c d f

Прототип функции:

compress(data, selectors)

Параметры функции:

  • data
    • Исходный набор данных.
  • selectors
    • Маска – набор элементов, которые будут интерпретированы как bool значения.

Примеры:

>>> list(compress("abcdef", [1, 0, 1, 1, 0, 1]))
['a', 'c', 'd', 'f']

>>> list(compress("abcdef", [i%3 == 0 for i in range(6)]))
['a', 'd']

>>> list(compress("abcdef", [i%3 == 0 for i in range(1, 7)]))
['c', 'f']

dropwhile()

Функция отбрасывает элементы итератора до тех пор, пока выполняется предикат:

dropwhile(lambda x: x < 3, [1,2,3,4,5,6]) -> 3 4 5 6

dropwhile(lambda x: len(x) < 2

Прототип функции:

dropwhile(predicate, iterable)

Параметры функции:

  • predicate
    • Предикат: функция, возвращающая true или false для переданного аргумента.
  • iterable
    • Набор данных (итератор) для обработки.

Примеры:

>>> list(dropwhile(lambda x: x < 3, [1,2,3,4,5,6]))
[3, 4, 5, 6]

>>> list(dropwhile(lambda x: x < 0 , [-1,-2,-3,-4, 5,6]))
[5, 6]

filterfalse()

Функция отбрасывает элементы итератора, для которых выполняется предикат:

filterfalse(lambda x: len(x) > 1, [“a”, “aa”, “aaa”, “aa”, “a”]) ->a a

Прототип функции:

filterfalse(predicate, iterable)

Параметры функции:

  • predicate
    • Предикат: функция, возвращающая true или false для переданного аргумента.
  • iterable
    • Набор данных (итератор) для обработки.

Примеры:

>>> list(filterfalse(lambda x: len(x) > 1, ["a", "aa", "aaa", "aa", "a"]))
['a', 'a']

groupby()

Функция группирует элементы из переданного ей итератора в соответствии с правилом, которое задается в виде функции.

Прототип функции:

groupby(iterable, key=None)

Параметры функции:

  • iterable
    • Набор данных (итератор) для обработки.
  • key
    • Функция группировки, если передано значение None, то используется функция следующего вида: lambda x: x.

Примеры:

>>> a = ["a", "b", "c", "ab", "bc", "ca"]
>>> for k, d in groupby(a, lambda x: len(x)):
...     print("len: {}, data: {}".format(k, list(d)))
...
len: 1, data: ['a', 'b', 'c']
len: 2, data: ['ab', 'bc', 'ca']

islice()

Создает итератор, который возвращает выбранные элементы из исходного итератора:

islice(‘ABC’, 2) -> A B

Прототип функции:

islice(iterable, stop)

islice(iterable, start, stop[, step])

Параметры функции:

  • iterable
    • Набор данных (итератор) для обработки.
  • start
    • Начальный элемент.
  • stop
    • Конечный элемент.
  • step
    • Шаг.

Примеры:

>>> list(islice("abc", 2))
['a', 'b']

>>> list(islice("abcdefgh", 3, 7, 2))
['d', 'f']

starmap()

Выполняет применение функции к элементам переданного итератора:

starmap(min, [(1,2), (1,2,3), (5,0), (6,7,8)]) -> 1 1 0 6

Прототип функции:

starmap(function, iterable)

Параметры функции:

  • function
    • Применяемая функция.
  • iterable
    • Набор данных (итератор) для обработки.

Примеры:

>>> list(starmap(min, [(1,2), (1,2,3), (5,0), (6,7,8)]))
[1, 1, 0, 6]

takewhile()

Извлекает элементы из входного итератора до тех пор пока выполняется предикат:

takewhile([1,2,3,4,5], lambda x: x < 4) -> 1 2 3

Прототип функции:

takewhile(predicate, iterable)

Параметры функции:

  • predicate
    • Предикат: функция, возвращающая true или false для переданного аргумента.
  • iterable
    • Набор данных (итератор) для обработки.

Примеры:

>>> list(takewhile(lambda x: x < 4, [1,2,3,4,5]))
[1, 2, 3]

>>> list(takewhile(lambda x: len(x) < 4, ["a", "ab", "abbbbba", "b"]))
['a', 'ab']

tee()

Создает заданное количество итераторов из исходного.

Прототип функции:

tee(iterable, n=2)

Параметры функции:

  • iterable
    • Набор данных (итератор).
  • n
    • Количество итераторов, которое нужно создать из исходного.

Примеры:

>>> iters = tee([1,2,3], 3)
>>> len(iters)
3

>>> iters
(<itertools._tee object at 0x0000000002304808>, <itertools._tee object at 0x0000000002304908>, <itertools._tee object at 0x0000000002304948>)

>>> for itr in iters:
...     print(list(itr))
...
[1, 2, 3]
[1, 2, 3]
[1, 2, 3]

zip_longest()

Создает итератор из элементов исходных итераторов подобно функции zip.

Прототип функции:

zip_longest(*iterables, fillvalue=None)

Параметры функции:

  • iterables
    • Исходные итераторы.
  • fillvalue
    • Значение, которое будет подставляться вместо элементов итератора, если данные в нем закончатся.

Примеры:

>>> list(zip_longest([1,2,3], "abcde", fillvalue="?"))
[(1, 'a'), (2, 'b'), (3, 'c'), ('?', 'd'), ('?', 'e')]

Комбинаторные итераторы

Функция Описание
product() Декартово произведение множеств.
permutations() Выдает сочетания из элементов исходного набора данных в указанном количестве. Порядок элементов имеет значение.
combinations() Выдает сочетания из элементов исходного набора данных в указанном количестве. Порядок элементов не имеет значения.
combinations_with_replacement() Выдает сочетания из элементов исходного набора данных в указанном количестве с возвратом. Порядок элементов не имеет значения.

product()

Строит декартово произведение множеств:

product(“ab”, [1,2]) -> (‘a’, 1) (‘a’, 2) (‘b’, 1) (‘b’, 2)

Прототип функции:

product(*iterables, repeat=1)

Параметры функции:

  • iterables
    • Наборы данных для объединения.
  • repeat
    • Если необходимо построить декартово произведение набора данных самим с собой, то через этот параметр задается, количество умножений множества самого на себя.

Примеры:

>>> list(product("ab", [1,2]))
[('a', 1), ('a', 2), ('b', 1), ('b', 2)]

>>> list(product("ab", repeat=2))
[('a', 'a'), ('a', 'b'), ('b', 'a'), ('b', 'b')]

permutations()

Выдает сочетания из элементов исходного набора данных в указанном количестве. Порядок элементов имеет значение: ab и ba – это разные наборы данных::

permutations(“abc”, 2) -> ab ac ba …

Прототип функции:

permutations(iterable, r=None)

Параметры функции:

  • iterable
    • Исходный набор данных.
  • r
    • Количество извлекаемых наборов данных.

Примеры:

>>> list(permutations("abc", 2))
[('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]

>>> list(permutations((1,2,3), 3))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

combinations()

Выдает сочетания из элементов исходного набора данных в указанном количестве. Порядок элементов не имеет значения: ab и ba – это одинаковые наборы данных:

combinations(“abc”, 2) -> ab ac bc…

Прототип функции:

combinations(iterable, r)

Параметры функции:

  • iterable
    • Исходный набор данных.
  • r
    • Количество извлекаемых наборов данных.

Примеры:

>>> list(combinations((1,2,3), 3))
[(1, 2, 3)]

>>> list(combinations("abc", 2))
[('a', 'b'), ('a', 'c'), ('b', 'c')]

combinations_with_replacement()

Выдает сочетания из элементов исходного набора данных в указанном количестве с возвратом. Порядок не имеет значение: ab и ba – это одинаковые наборы данных:

combinations_with_replacement(“abc”, 2) -> ab ac bc…

Прототип функции:

combinations_with_replacement(iterable, r)

Параметры функции:

  • iterable
    • Исходный набор данных.
  • r
    • Количество извлекаемых наборов данных.

Примеры:

>>> list(combinations_with_replacement("abc", 2))
[('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'b'), ('b', 'c'), ('c', 'c')]

>>> list(combinations_with_replacement((1,2,3), 3))
[(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 2), (1, 2, 3), (1, 3, 3), (2, 2, 2), (2, 2, 3), (2, 3, 3), (3, 3, 3)]

P.S.

Вводные уроки по “Линейной алгебре на Python” вы можете найти соответствующей странице нашего сайта. Все уроки по этой теме собраны в книге “Линейная алгебра на Python”.
Книга: Линейная алгебра на Python
Если вам интересна тема анализа данных, то мы рекомендуем ознакомиться с библиотекой Pandas.  Для начала вы можете познакомиться с вводными уроками. Все уроки по библиотеке Pandas собраны в книге Pandas. Работа с данными”.
Книга: Pandas. Работа с данными

Поделиться
Share on VK
VK
Tweet about this on Twitter
Twitter
Share on Facebook
Facebook

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

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