Reduce

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

По Пайтону соскучился — он мне нравится, а я всерьёз не программировал на нём несколько лет. С удовольствием смотрю что наворотили в третьей версии, которую я почти не трогал. Бо́льшая часть языка легко и почти сразу вспоминается, но долгое отсутствие практики всё же сказывается.

Решали сегодня задачки из «Проекта Эйлер», в частности 67-ю задачу. Суть её такова, вкратце. Дан треугольник чисел, нужно найти в нём максимальную сумму, из всех, что получаются, если двигаться сверху по соседям ниже. Посмотрите задачу, там картинка есть, всё понятно.

from functools import reduce

def read():
    with open('p067_triangle.txt') as f:
        for line in f.readlines()[::-1]:
            yield tuple(int(x) for x in line.strip().split(' '))

reduce(lambda cur, prv: [max(cur[pos:pos+2])+v for pos, v in enumerate(prv)], read())

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

Результат мозговых усилий выше. Код сократился до одной строки (функция над ней — просто чтение данных).

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

На закуску вот вам фолдинг на «Баше», взятый из комментария со «Стека Оверфлоу»:

foldl() {
    echo $(($(</dev/stdin)$2))
} < <(tr '\n' "$1" <$3)

# Sum 20 random ints from 0-999
foldl + 0 <(while ((n=RANDOM%999,x++<20)); do echo $n; done)

Тут суммируются двадцать псевдослучайных чисел из диапазона 0—999.

Поделиться
Отправить
5 комментариев
PastorGL

Хотел было съязвить про «добро пожаловать в 2019, и как там у вас в 2009», но вовремя понял, что и сам-то не юзал функции высшего порядка вплоть до позапрошлого года, пока мне не пришлось начать писать всякое на Spark :)

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

Евгений Степанищев

Саму концепцию-то MapReduce я понимаю и конечно постоянно использую при агрегациях (например, подсчёт суммы — это тот же reduce), но никогда именно ф-ю reduce не использовал, всегда какие-то функции поверх.

PastorGL

Не приходилось разве с монгой (или другими NoSQL) работать? Там для подсчёта суммы редьюс-функцию приходится писать в очень явном и классическом виде.

Евгений Степанищев

Во многих NoSQL есть более высокоуровневые вещи.

Ivan

Reduce это мощнейщая абстракция, через нее делается map, filter, take, while и примерно еще сотня других функций. В питоне reduce не популярен, потому что создатель языка сделал ставку на императивную обработку коллекций. Красивей всего ведут себя коллекции в Clojure, посмотрите, не пожалеете. В этом языке поощрается обработка коллекций без дополнительных переменных, и reduce хорошо заходит.

Популярное