Агрегация (reduce) — Python: Функции

• Как думать о редьюсе
• Реализация

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

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

users = [
  { 'name': 'Igor', 'amount': 19 },
  { 'name': 'Danil', 'amount': 1 },
  { 'name': 'Ivan', 'amount': 4 },
  { 'name': 'Matvey', 'amount': 16 },
]

sum = 0
for user in users:
  sum += user['amount']

print(sum) # => 40

Основное отличие агрегации от отображения и фильтрации в том, что результатом агрегации может быть любой тип данных — как примитивный, так и составной, например, список. Кроме того, агрегация нередко подразумевает инициализацию начальным значением, которое принято называть аккумулятором. В примере выше она выполняется на строчке sum = 0. Здесь переменная sum "аккумулирует" результат внутри себя.

Посмотрим еще один пример агрегации — группировку имён пользователей по возрасту:

users = [
  { 'name': 'Petr', 'age': 4 },
  { 'name': 'Igor', 'age': 19 },
  { 'name': 'Ivan', 'age': 4 },
  { 'name': 'Matvey', 'age': 16 },
]

users_by_age = {}
for user in users:
    age = user['age']
    name = user['name']
    # Проверяем, добавлен ли уже ключ age в результирующий словарь или нет
    if age not in users_by_age:
        users_by_age[age] = []
    users_by_age[age].append(name)

print(users_by_age)
# => { 4: [ 'Petr', 'Ivan' ], 16: [ 'Matvey' ], 19: [ 'Igor' ] }

В этом примере результатом агрегации становится словарь, в значениях которого записаны списки. Этот результат в самом начале инициируется пустым словарем, а затем постепенно, на каждой итерации, "наполняется" нужными данными. Значение, которое накапливает результат агрегации, принято называть словом "аккумулятор". В примерах выше это sum и users_by_age.

Реализуем первый пример, используя reduce():

# reduce не поставляется в стандартной библиотеке и его нужно импортировать из functools
from functools import reduce


users = [
  { 'name': 'Igor', 'amount': 19 },
  { 'name': 'Danil', 'amount': 1 },
  { 'name': 'Ivan', 'amount': 4 },
  { 'name': 'Matvey', 'amount': 16 },
]

total = reduce(lambda acc, user: acc + user['amount'], users, 0)

# Распишем
# user: Igor, acc = 0, return value 0 + 19
# user: Danil, acc = 19, return value 19 + 1
# user: Ivan, acc = 20, return value 20 + 4
# user: Matvey, acc = 24, return value 24 + 16
print(total) # => 40

Функция reduce() принимает на вход три параметра — функцию-обработчик, коллекцию и начальное значение аккумулятора. Этот же аккумулятор возвращается наружу в качестве результата всей операции. В отличие от map() и filter(), которые используют ленивые вычисления, reduce() сразу возвращает результат.

Функция, передаваемая в reduce() — самая важная часть и ключ к пониманию работы всего механизма агрегации. Она принимает на вход два значения. Первое — текущее значение аккумулятора, второе — текущий обрабатываемый элемент. Задача функции — вернуть новое значение аккумулятора. reduce() никак не анализирует содержимое аккумулятора. Всё, что она делает, передаёт его в каждый новый вызов до тех пор, пока не будет обработана вся коллекция, и в конце концов вернёт его наружу. Подчеркну, что возвращать аккумулятор надо всегда, даже если он не изменился.

Второй пример с использованием reduce() выглядит так:

from functools import reduce

users = [
    { 'name': 'Petr', 'age': 4 },
    { 'name': 'Igor', 'age': 19 },
    { 'name': 'Ivan', 'age': 4 },
    { 'name': 'Matvey', 'age': 16 },
]

# Предварительно подготовим функцию-обработчик
def cb(acc, user):
    if user['age'] not in acc:
        acc[user['age']] = []
    acc[user['age']].append(user['name'])
    return acc  # обязательно вернуть!

# Начальное значение аккумулятора – пустой словарь
users_by_age = reduce(cb, users, {})

print(users_by_age)

Разберем пошагово работу функции reduce(). В функцию передается колбек, который принимает два параметра acc и user. Чтобы лучше понять работу, нужно проследить чему равны значения этих параметров на каждой итерации:

1. На первой итерации acc равен пустому словарю, это начальное значение аккумулятора задается последний параметром reduce(cb, users, {}) — здесь передается пустой словарь. Параметр user равен первому элементу списка, то есть { 'name': 'Petr', age: 4 }. В пустом словаре создается список под ключом user['age'] и в этот список добавляется текущее имя пользователя. В итоге acc становится равен словарю { 4: ['Petr'] }. Из функции возвращается acc — это значение будет аккумулятором на следующей итерации
2. На второй итерации acc равен значению, которое вернулось из предыдущей итерации, это словарь { 4: ['Petr'] }. Параметр user равен второму элементу списка { 'name': 'Igor', age: 19 }. В аккумуляторе acc нет ключа с возрастом текущего пользователя, поэтому добавляется новый ключ и список. После заполнения acc равен { 4: ['Petr'], 19: ['Igor'] }, этот словарь возвращается из функции
3. На этой итерации acc равен словарю, вернувшемуся из прошлой итерации { 4: ['Petr'], 19: ['Igor'] }. Параметр user равен { 'name': 'Ivan', age: 4 }. Значение user['age'] равно 4 — этот ключ уже имеется в аккумуляторе, поэтому новый ключ не создается, а текущий пользователь добавляется в существующий список. В итоге аккумулятор равен словарю { 4: ['Petr', 'Ivan'], 19: ['Igor'] } и он возвращается из функции
4. Последняя итерация. Параметр acc равен { 4: ['Petr', 'Ivan'], 19: ['Igor'] }, а user равен { 'name': 'Matvey', age: 16 }. Ключа 16 в аккумуляторе нет, поэтому добавляется новый список в ключ 16, в этот список добавляется текущий пользователь. В итоге acc будет равен { 4: ['Petr', 'Ivan'], 16: ['Matvey'], 19: ['Igor'] }, этот словарь возвращается и в итоге будет результатом работы всего редьюса, так как это последняя итерация

reduce() — очень мощная функция. Формально, можно работать, используя только ее, так как она может заменить и отображение, и фильтрацию. Но делать так не стоит. Агрегация управляет состоянием (аккумулятором) явно. Такой код всегда сложнее и требует больше действий. Поэтому, если задачу возможно решить отображением или фильтрацией, то так и нужно делать.

Как думать о редьюсе

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

# Упрощенная структура, чтобы не перегружать
# В реальности тут была бы куча дополнительных данных о курсе и об уроках
courses = [
  {
    'name': 'Arrays',
    'lessons': [{ 'name': 'One' }, { 'name': 'Two' } ]
  },
  {
    'name': 'Objects',
    'lessons': [{ 'name': 'Lala' }, { 'name': 'One' }, { 'name': 'Two' } ]
  }
]

Здесь мы видим два курса, в которых суммарно 5 уроков. Попробуем теперь высчитать это число программно. Первый вопрос, на который надо ответить, является ли данная операция агрегацией? Ответ - Да, так как мы сводим исходные данные, к какому-то вычисляемому результату. Дальше смотрим, чем является результат операции. В нашем случае это число, которое вычисляется как сумма уроков в каждом курсе. Значит начальным значением аккумулятора будет 0.

Теперь примерный алгоритм:

1. Инициализируем накапливаемый результат нулем
2. Обходим коллекцию курсов по одному
   • Прибавляем к аккумулятору количество уроков в текущем курсе

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

# Вариант с циклом for
result = 0
for course in courses:
    result += len(course['lessons'])
print(result)  # => 5

# Вариант с reduce
from functools import reduce

result = reduce(lambda acc, course: acc + len(course['lessons']), courses, 0)
print(result)  # => 5

Реализация

Напишем свою собственную функцию my_reduce(), работающую аналогично библиотечному reduce():

def my_reduce(callback, collection, init):
  acc = init # инициализация аккумулятора
  for item in collection:
    acc = callback(acc, item) # Заменяем старый аккумулятор новым
  return acc

users = [
  { 'name': 'Petr', 'age': 4 },
  { 'name': 'Igor', 'age': 19 },
  { 'name': 'Ivan', 'age': 4 },
  { 'name': 'Matvey', 'age': 16 },
]

oldest = my_reduce(
  lambda acc, user: user if user['age'] > acc['age'] else acc,
  users,
  users[0],
)
print(oldest) # => { 'name': 'Igor', age: 19 }

Дополнительные материалы

1. Функция reduce

---

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

• Статья «Как учиться и справляться с негативными мыслями»
• Статья «Ловушки обучения»
• Статья «Сложные простые задачи по программированию»
• Вебинар «Как самостоятельно учиться»