В рамках данной статьи рассмотрим нормальный и аппликативный порядки вычисления, их преимущества и недостатки. Обзорно коснемся темы итераторов и генераторов и подробно разберем пакет 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”.
Если вам интересна тема анализа данных, то мы рекомендуем ознакомиться с библиотекой Pandas. Для начала вы можете познакомиться с вводными уроками. Все уроки по библиотеке Pandas собраны в книге “Pandas. Работа с данными”.
