Comments 33
Идея довольно простая, на самом деле. Но с моноидом внутри, действительно, получается красиво.
Можно посчитать сумму параллельно, а потом, получив её на финальном узле, за O(1) -- max.
Пример последовательности: 1 -2 3. Если считать правильно то получится: relu(1-2)+3=3; а если наивно: 2.
Легко понять что порядок важен: если переставить 3 в начало то переносов при сложении не возникнет, и результат совпадет, в то время как подход "сложить все" - теряет информацию о порядке.
Ясно, max применяется на каждом шаге, а не ко всей сумме.
Забавно :) Но не понятна область применения.
Пример последовательности: 1 -2 3
Если это как-то относится к остаткам на складе или состоянию счета, то на этапе -2 нужно генерировать exception. Банкомат, например, либо выдает заказанную сумму, либо не выдает ничего.
Очень правильный вопрос. Подобрать подходящий инструмент под задачу и наоборот — полдела к успеху в любом начинании. Могу предложить варианты для grosum:
Кладовщик ограничен максимальной пропускной способностью — на входе потенциальный расход, а не фактический, который меньше.
Банкомат выдаёт максимум, сколько может.
Глязные данные, которые нужно почистить online или offline.
Запоздалые транзакции оформлены задним числом. Нужно быстро инкрементально за O(ln n) пересчитать хвост журнала.
О, кстати про исключения. Я только что понял, что случай "суммы с исключениями", во-первых, точно так же не является ассоциативным, а во-вторых вычисляется тем же самым алгоритмом, только с проверкой fall на последнем шаге:
static long grosumEx(LongStream changes) {
Gro x = changes.collect(Gro::new, Example::accumulator, Example::combiner);
if (x.fall > 0)
throw …;
return x.grow;
}Но это только для случая, когда любое исключение ломает процесс. Если рассматривать модель банкомата, который при исключении продолжает работу с неизменным остатком (a+b<0? a: a+b) — то пара ⊕a ⊖b из моего комментария ниже перестанет редуцироваться до ⊖(b — a) и вся конструкция рассыпается.
В статье показана магия, но явно не хватает объяснений. И группа Гротендика тут ничего не объясняет, а лишь усложняет, потому что, к примеру, сложение в группе Гротендика отличается от операции combine.
Поэтому попробую раскрыть магию подробнее. Вот у нас есть операция ⊕, которая "неудобна" из-за отсутствия ассоциативности. Сопоставим теперь каждому числу a функцию fa(x) = x ⊕ a, эта функция выражает наше "намерение" прибавить a. Обозначим такую функцию (⊕a).
Теперь рассмотрим пару чисел a и b, и функцию-"намерение" для этой пары: ga, b(x) = (x ⊕ a) ⊕ b. Эта функция является композицией функций ⊕a и ⊕b: ga, b = (⊕b) ∘ (⊕a). Кстати, обозначим для простоты в дальнейшем такую функцию как ⊕a ⊕b. Теперь вспомним что композиция функций всегда ассоциативна, и мы получаем, что любую операцию можно "сделать" ассоциативной если перейти от исходного множества и операции к множеству функций-"намерений" над первым и композиции функций.
Кстати, по-научному "намерения" называются эндоморфизмами, а построенный нами моноид так и называется — моноид эндоморфизмов.
К сожалению, операция композиции функций ничего не вычисляет, а лишь откладывает вычисление, поэтому "в лоб" всё перечисленное выше не применить. Нужно найти какой-то способ упрощения сложных композиций, чтобы закодировать эндоморфизмы пригодным для вычислений способом.
Теперь переходим к самой "магии". Для начала, разделим все эндоморфизмы по знаку: здесь и далее,
⊕a означает функцию fa(x) = x ⊕ a, где a ≥ 0
⊖a означает функцию fa(x) = x ⊕ -a, где a ≥ 0
Заметим, что намерения одного знака друг с другом складываются:
⊕a ⊕b = ⊕(a+b)
⊖a ⊖b = ⊖(a+b)
Также заметим, что операции ⊕ и ⊖ могут компенсировать друг друга, но только если идут именно в этом порядке:
⊕a ⊖b = ⊕(a — b), если a ≥ b
⊕a ⊖b = ⊖(b — a), если a ≤ b
(случай a=b тут разобран два раза, но это не ошибка, потому что ⊕0 и ⊖0 — одна и та же операция, и нет разницы как считать)
А вот последовательность операций ⊖a ⊕b никак не упрощается, поэтому в общем случае любая последовательность операций упростится до этой формы. Ну так давайте именно такую форму и выберем в качестве конструктивного представления "намерения"!
И так, любой интересующий нас эндоморфизм мы будем представлять в виде пары чисел (a, b): f(x) = (x ⊕ -a) ⊕ b, где a и b ≥ 0.
Теперь можно наконец-то выразить операцию композиции намерений:
(a, b) ⊕ (c, d) = ⊖a ⊕b ⊖c ⊕d = ⊖a ⊕(b-c) ⊕d = ⊖a ⊕(b-c+d) = (a, b-c+d), если b ≥ c
(a, b) ⊕ (c, d) = ⊖a ⊕b ⊖c ⊕d = ⊖a ⊖(c-b) ⊕d = ⊖(a-b+c) ⊕d = (a-b+c, d), если b ≤ c
Проверяйте, эта формула соответствует функции combiner из поста. Функцию accumulator можно получить, если подставить в эту формулу формулу перехода от числе к намерениям. Ну а финальное получение поля grow в функции grosum — это ни что иное как подстановка x=0 в формулу эндоморфизма:
(a, b)(0) = (0 ⊕ -a) ⊕ b = 0 ⊕ b = b.
А вот применять неотрицательную сумму к складу я бы поостерёгся: отрицательный остаток на складе — явно исключительная ситуация, и молча исправлять такие ситуации в ноль — не совсем то, что ожидается от надёжной системы.
Опять-таки, если из пустого склада увезли 16 единиц продукта, а потом эту операцию сторнировали (что было отражено в журнале как +16 единиц продукта) — в итоге остаток должен быть 0, а не 16.
Зависит от целей, а не от того, что это склад. У нас, например, оптимизационная NP задача составления расписаний сотрудников, в том числе на складе. А быстрый инкрементальный пересчёт позволил считать на ноутбуке, а не на кластере.
Абстракция отличается от реальности и выбирать нужно подходящую под действия. grosum ничем не лучше и не хуже sum — ещё один кирпичик конструктора приложений.
Кстати, в поле fall накопится сумма, которую нужно сторнировать, чтобы баланс сошёлся. Тоже может быть кому-нибудь полезно.
Большое спасибо за статью. Порекомендуйте пожалуйста литературу по функциональному программированию. У меня каша в голове от всех возможностей которые даёт фп. Хотелось бы привести это всё в порядок, но достойной книги где бы это всё хорошо разжёвывалось я пока не нашел. Заранее большое спасибо за любые ссылки или любую информацию.
https://en.m.wikibooks.org/wiki/Haskell
Привожу в порядок этим, там и примеры (с ответами)
ФП не так далеко от ООП, как принято считать. Хотя одни и те же вещи называют разными именами.
К сожалению "имена" не добавляют ясности и понятности.
Я раз пять прочитал Ваше "определение" Вариантности......ни чего не понял. Думаю что и после 50 прочтения тоже ничего не пойму..... Мне кажется дело не во мне, а в "определении" ))))) Возможно я ошибаюсь. (
Хотя Вариантность достаточно простая и понятная штука. Если конечно её просто и понятно объяснять.
Может есть смысл улучшить Ваше "определение" Вариантности?
Возможно пример того, как Вариантность можно использовать в реальном проекте, сделает Ваше "определение" Вариантности более понятным.
К сожалению, только читать бесполезно, хоть 5, хоть 1000 раз. В том посте ошибка — "определение" надо переназывать "понятиями" — сам только недавно научился различать. Прочитав множество имён снега, вы не научитесь ими пользоваться. Попробуйте написать для детей простой туториал езды на велосипеде. Мы можем понять друг друга только в деятельности.
Человеку вот понравилось описание функторов и монад, но думаю только потому, что он уже достаточно попрактиковался, наработал понятие и прочувствовал несколько примеров монад, чтобы их сравнить и найти между ними что-то общее.
Напишу понятнее. Я знаю что такое Covariance and Сontravariance. Ваше "определение" "Вариантности" сложное и запутывает читателя. Когда читаешь Ваше "определение" возникает впечатление, что автор сам плохо понимает то о чем пишет.
IMHO Ваше определение "Вариантности" можно значительно улучшить.
Возможно есть смысл не использовать слово "Вариантность". А использовать Covariance and Сontravariance.
return changes.reduce(0, (a, b) -> Math.max(0, a + b));приводит к тому, что для списка (a,b,c,d...) мы считаем на самом деле 0 ⊕ a ⊕ b ⊕ c ⊕ d +… (вместо a ⊕ b ⊕ c ⊕ d + ...). Благодаря этому функция ⊕ у нас применяется всегда для неотрицательного первого числа, отсюда например и
⊕a ⊕b = ⊕(a+b)хотя в общем случае x ⊕ 1 ⊕ 2 != x ⊕ 3
Да, если разрешить начальному значению быть отрицательным — то ⊕a ⊕b перестаёт редуцироваться до ⊕(a+b) и всё рассыпается.
Но решение тут простое — надо разделить исходный список на "голову" и "хвост":
S ⊕ a ⊕ b ⊕ c ⊕ d +… = (S ⊕ a) ⊕ b ⊕ c ⊕ d +…
Здесь S ⊕ a всегда неотрицательное, а значит для хвоста можно использовать обсуждаемый алгоритм.
Точно так же решается задача и для случая, когда у нас вообще нет никакого аккумулятора, только теперь придётся выделить уже два элемента из головы списка:
a ⊕ b ⊕ c ⊕ d +… = (a ⊕ b) ⊕ c ⊕ d +…
Возможно, @mayorovp меня поправит, что он имел в виду. Я за круглым плюсом ⊕ вижу 2 смысла. Чтобы их не путать, введём квадратный плюс ⊞.
⊖fall отрицательный морфизм;
⊕grow положительный морфизм;
a ⊞ b = max(0, a + b) = relu(a + b), неудобная неассоциативная бинарная операция;кусок истории ((((x ⊞ a) ⊞ b) ⊞ c) ⊞ …) представим смесью морфизмов, парой
(⊖fall, ⊕grow).
Да, считаем (((0 ⊞ a) ⊞ b) ⊞ c) ⊞ …, как будто начинаем с пустого склада. Не забываем про неявные скобочки левой свёртки.
В общем случае верны оба:
(x ⊞ 1) ⊞ 2 = x ⊞ 3. Но неассоциативно.(⊕1)∘(⊕2) = (⊕3). Ассоциативно и в длинных скобки можно выражениях скобки можно опускать⊕a∘⊕b∘⊕c = ⊕(a+b+c). Но представление не полно, нужны ещё отрицательные морфизмы⊖, для записи произвольной истории нужна пара(⊖fall, ⊕grow).
Фух! Сложно объяснить простой код :(
Вам говорят, что (x ⊞ 1) ⊞ 2 не всегда равно x ⊞ 3. К примеру, (-2 ⊞ 1) ⊞ 2 = 2, в то время как -2 ⊞ 3 = 1.
Если начинать с пустого или хотя бы валидного склада — это не играет роли, но если начать со склада в невалидном состоянии — алгоритм отработает некорректно. Является ли это ошибкой — другой вопрос. Для случая со складом — наверное, нет. В общем случае — наверное, да.
Пример с x=-2 понятен, действительно, в этом случае будут проблемы, но не у grosum. Дальше зависит от договорённостей, что такое общий случай :) Я предполагаю fall и grow неотрицательными, как у Гротендика, соответственно, x не может быть -2. В посте я ухожу даже от плавающей точки, чтобы не касаться неассоциативности при округлении. Опущены даже вопросы переполнения long. Множество других вопросов остаются на совести разработчика приложения.
Но алгоритм из поста, grosum [-2, 1, 2] = 3 = grosum [1, 2] = grosum [3]. Алгоритм, который вернёт 2 или 1 — это некий другой, модифицированный алгоритм. Прежде чем рассуждать о нём, сначала необходимо зафиксировать его код.
Вам же с самого начала написали:
А если считать действительно сумму, без инициализации аккумулятора нулем?
Разумеется, grosum, считающая что в аккумуляторе настолько ноль, что его даже нет в алгоритме, для этого случая напрямую не подходит.
Вот вам обсуждаемая задача, если до сих пор не понятно:
changes.reduce((a, b) -> Math.max(0, a + b));А если считать действительно сумму, без инициализации аккумулятора нулем?
Без примера кода точный смысл этого высказывания мне не ясен: инициализировать его чем-то другим, чтобы что сделать? Какой тезис обсуждаем?
Знаю только, что в неотрицательной сумме нет отрицательных чисел ни в начальном балансе S, ни в промежуточном балансе (в том числе в S⊞a), ни даже в названии :) А из ложной посылки (S отрицательно) можно вывести всё, что угодно, так что заранее согласен.
Вот вам пример:
changes.reduce((a, b) -> Math.max(0, a + b));Что тут непонятно-то? Как распаралелить этот код?
Этот код не полон. Перед тем, как параллелить, сначала типы поправьте: результат должен быть числом, что делать с OptionalLong, почему и зачем?
Был код, который решал задачу, вы его сломали и спрашиваете как починить? Не знаю, что может быть лучше, чем откатить коммит :) Вы хорошо разбираетесь в вопросе — ваш первый комментарий это показал. Уверен, вы правы, только я не понимаю постановку задачи, которую вы решаете — она у вас в голове. Ветка дискуссии разрослась, поэтому прошу в личку.
Спасибо, было интересно, но почему работает – не понимал, пока не вывел алгоритм сам. Привычней всё-таки идти по старинке, не от монад, а от инвариантов цикла.
«Невозможный» параллельный алгоритм неотрицательной суммы