Защо е необходим комбинатор за метод за намаляване, който преобразува тип в java 8

Имам проблеми с пълното разбиране на ролята, която combiner изпълнява в метода Streams reduce.

Например следният код не се компилира:

int length = asList("str1", "str2").stream()
            .reduce(0, (accumulatedInt, str) -> accumulatedInt + str.length());

Грешка при компилиране гласи: (несъответствие на аргумент; int не може да се преобразува в java.lang.String)

но този код се компилира:

int length = asList("str1", "str2").stream()  
    .reduce(0, (accumulatedInt, str ) -> accumulatedInt + str.length(), 
                (accumulatedInt, accumulatedInt2) -> accumulatedInt + accumulatedInt2);

Разбирам, че методът на комбиниране се използва в паралелни потоци - така че в моя пример той събира две междинни натрупани int.

Но не разбирам защо първият пример не се компилира без комбинатора или как комбинаторът решава преобразуването на низ в int, тъй като просто събира две int.

Може ли някой да хвърли светлина върху това?


person Louise Miller    schedule 19.06.2014    source източник
comment
Свързан въпрос: stackoverflow.com/questions/24202473/   -  person nosid    schedule 19.06.2014
comment
аха, това е за паралелни потоци... аз наричам leaky абстракция!   -  person Andy    schedule 22.04.2017
comment
Сблъсках се с подобен проблем. Исках да направя map-reduce. Исках методът за намаляване на Stream да има претоварена версия, която позволява картографиране към различен тип от входния тип, но не ме принуждава да напиша комбинатор. Доколкото знам Java няма такъв метод. Тъй като някои хора, като мен, очакват да го намерят, но го няма, това създава объркване. Забележка: Не исках да напиша комбинатор, защото изходът беше сложен обект, за който комбинаторът не беше реалистичен.   -  person user2367418    schedule 17.05.2021


Отговори (4)


Версиите с два и три аргумента на reduce, които се опитахте да използвате, не приемат същия тип за accumulator.

Двата аргумента reduce са дефиниран като :

T reduce(T identity,
         BinaryOperator<T> accumulator)

Във вашия случай T е String, така че BinaryOperator<T> трябва да приеме два аргумента String и да върне String. Но му предавате int и String, което води до грешката при компилиране, която сте получили - argument mismatch; int cannot be converted to java.lang.String. Всъщност мисля, че предаването на 0 като стойност за идентичност също е грешно тук, тъй като се очаква низ (T).

Също така имайте предвид, че тази версия на reduce обработва поток от Ts и връща T, така че не можете да я използвате, за да намалите поток от String до int.

Трите аргумента reduce са дефиниран като :

<U> U reduce(U identity,
             BiFunction<U,? super T,U> accumulator,
             BinaryOperator<U> combiner)

Във вашия случай U е цяло число, а T е низ, така че този метод ще намали поток от низ до цяло число.

За акумулатора BiFunction<U,? super T,U> можете да подадете параметри от два различни типа (U и? super T), които във вашия случай са Integer и String. В допълнение, стойността за идентичност U приема цяло число във вашия случай, така че предаването му на 0 е добре.

Друг начин да постигнете това, което искате:

int length = asList("str1", "str2").stream().mapToInt (s -> s.length())
            .reduce(0, (accumulatedInt, len) -> accumulatedInt + len);

Тук типът на потока съвпада с върнатия тип на reduce, така че можете да използвате версията с два параметъра на reduce.

Разбира се, изобщо не е нужно да използвате reduce:

int length = asList("str1", "str2").stream().mapToInt (s -> s.length())
            .sum();
person Eran    schedule 19.06.2014
comment
Като втора опция в последния си код можете също да използвате mapToInt(String::length) над mapToInt(s -> s.length()), не съм сигурен дали едното би било по-добро от другото, но предпочитам първото за четимост. - person skiwi; 19.06.2014
comment
Мнозина ще намерят този отговор, тъй като не разбират защо е необходим combiner, защо не е достатъчно accumulator. В този случай: Комбинаторът е необходим само за паралелни потоци, за да комбинира натрупаните резултати от нишките. - person ddekany; 24.11.2017
comment
Не намирам отговора ти за особено полезен - защото изобщо не обясняваш какво трябва да прави комбинаторът и как мога да работя без него! В моя случай искам да редуцирам тип T до U, но няма начин това изобщо да може да се направи паралелно. Просто не е възможно. Как казвате на системата, че не искам/имам нужда от паралелизъм и по този начин пропускам комбинатора? - person Zordid; 28.08.2018
comment
@Zordid API за потоци не включва опция за намаляване на тип T до U без преминаване на комбинатор. - person Eran; 28.08.2018
comment
Този отговор изобщо не обяснява комбинатора, а само защо OP се нуждае от вариантите без комбинатор. - person Benny Bottema; 25.09.2020

Отговорът на Еран описва разликите между версиите с два и три аргумента на reduce в това, че първата редуцира Stream<T> до T, докато последният редуцира Stream<T> до U. Въпреки това, това всъщност не обяснява необходимостта от допълнителната функция за комбиниране при намаляване на Stream<T> до U.

Един от принципите на проектиране на API за потоци е, че API не трябва да се различава между последователни и паралелни потоци, или казано по друг начин, определен API не трябва да пречи на потока да работи правилно нито последователно, нито паралелно. Ако вашите ламбда имат правилните свойства (асоциативни, неинтерфериращи и т.н.), потокът, изпълняван последователно или паралелно, трябва да даде същите резултати.

Нека първо да разгледаме версията на редукция с два аргумента:

T reduce(I, (T, T) -> T)

Последователното внедряване е лесно. Идентификационната стойност I се "натрупва" с елемента на нулевия поток, за да даде резултат. Този резултат се натрупва с първия елемент на потока, за да даде друг резултат, който от своя страна се натрупва с втория елемент на потока и т.н. След натрупването на последния елемент се връща крайният резултат.

Паралелното внедряване започва с разделяне на потока на сегменти. Всеки сегмент се обработва от собствена нишка по последователния начин, който описах по-горе. Сега, ако имаме N нишки, имаме N междинни резултата. Те трябва да бъдат сведени до един резултат. Тъй като всеки междинен резултат е от тип T и имаме няколко, можем да използваме една и съща акумулираща функция, за да намалим тези N междинни резултата до един резултат.

Сега нека разгледаме хипотетична операция за намаляване на два аргумента, която редуцира Stream<T> до U. На други езици това се нарича "сгъване" или "сгъване- наляво", така че така ще го нарека тук. Имайте предвид, че това не съществува в Java.

U foldLeft(I, (U, T) -> U)

(Обърнете внимание, че стойността на идентичност I е от тип U.)

Последователната версия на foldLeft е точно като последователната версия на reduce с изключение на това, че междинните стойности са от тип U вместо от тип T. Но иначе е същото. (Хипотетична операция foldRight би била подобна, с изключение на това, че операциите ще се извършват отдясно наляво вместо отляво надясно.)

Сега разгледайте паралелната версия на foldLeft. Нека започнем, като разделим потока на сегменти. След това можем да накараме всяка от N нишките да намали стойностите T в своя сегмент в N междинни стойности от тип U. Сега какво? Как да стигнем от N стойности от тип U до един резултат от тип U?

Това, което липсва, е друга функция, която комбинира множеството междинни резултати от тип U в един резултат от тип U. Ако имаме функция, която комбинира две U стойности в една, това е достатъчно, за да намали произволен брой стойности до едно -- точно като първоначалното намаление по-горе. По този начин операцията за намаляване, която дава резултат от различен тип, се нуждае от две функции:

U reduce(I, (U, T) -> U, (U, U) -> U)

Или, използвайки синтаксиса на Java:

<U> U reduce(U identity, BiFunction<U,? super T,U> accumulator, BinaryOperator<U> combiner)

В обобщение, за да направим паралелно редуциране до различен тип резултат, имаме нужда от две функции: една, която натрупва T елементи до междинни U стойности, и втора, която комбинира междинните U стойности в един U резултат. Ако не превключваме типовете, се оказва, че акумулаторната функция е същата като комбиниращата функция. Ето защо редуцирането до същия тип има само акумулираща функция, а редуцирането до различен тип изисква отделни акумулаторни и комбиниращи функции.

И накрая, Java не предоставя foldLeft и foldRight операции, защото те предполагат конкретно подреждане на операциите, което по своята същност е последователно. Това се сблъсква с посочения по-горе принцип на проектиране за предоставяне на API, които поддържат еднакво последователна и паралелна работа.

person Stuart Marks    schedule 19.06.2014
comment
И така, какво можете да направите, ако имате нужда от foldLeft, защото изчислението зависи от предишния резултат и не може да бъде успоредно? - person amoebe; 09.05.2015
comment
@amoebe Можете да приложите свой собствен foldLeft, като използвате forEachOrdered. Междинното състояние обаче трябва да се запази в уловена променлива. - person Stuart Marks; 10.05.2015
comment
@StuartMarks благодаря, накрая използвах jOOλ. Те имат чист изпълнение на foldLeft. - person amoebe; 10.05.2015
comment
Обичам този отговор! Поправете ме, ако греша: това обяснява защо изпълняваният пример на OP (вторият) никога няма да извика комбинатора, когато се изпълнява, тъй като е последователен поток. - person Luigi Cortese; 25.11.2015
comment
Обяснява почти всичко... освен: защо това трябва да изключва последователно базирано намаляване. В моя случай е НЕВЪЗМОЖНО да го направя паралелно, тъй като моето намаление редуцира списък от функции в U, като извиква всяка функция на междинния резултат от резултата на нейните предшественици. Това изобщо не може да се направи паралелно и няма как да се опише комбинатор. Какъв метод мога да използвам, за да постигна това? - person Zordid; 28.08.2018
comment
@Zordid имате стария тъжен for цикъл или можете да използвате forEach с външна променлива като акумулатор. Тъжно е и аз съм във вашето положение, така че имате моето съчувствие - person Rick77; 07.06.2019
comment
Отлично. Страхотно вникване в Java потоците намалява api - person sigirisetti; 13.07.2019
comment
@Zordid звучи така, сякаш се опитвате да използвате намаляването на потока за нещо, за което не е предназначено. Намаляването трябва да е без гражданство, звучи сякаш вашето не е. Какво означава резултат от предшественици? Изглежда, че това може да е вашият проблем. - person Frans; 22.11.2019
comment
@Frans Въпросът тук не е държавността. Проблемът е, че API за поток на Java изисква акумулаторните функции да бъдат асоциативни (за да поддържат паралелно изпълнение), а акумулаторът, който Zordid описва, не е асоциативен. Разрешаването на паралелно изпълнение не е възможно едновременно с разрешаването на неасоциативни акумулиращи функции. - person Silwing; 03.09.2020
comment
@Silwing Не съм сигурен какво имате предвид под асоциативен; можеш ли да обясниш? Мисля, че казваме едно и също нещо, само с различни термини. - person Frans; 13.09.2020
comment
@Frans associative е свойство, което една операция може да притежава. Което означава, че ако свържете няколко от тези операции заедно, няма значение в кой ред се изпълняват: (a op b) op c = a op (b op c) Следователно всичко, което се нуждае от специфичен ред на изпълнение, не е асоциативно. Това, което имам предвид, може да бъде без състояние, без да е асоциативно. - person Silwing; 14.09.2020
comment
Не разбирам как този API удовлетворява това, което казахте за това как паралелният и последователният трябва да работят по един и същи начин. Прилагам същата логика (комбиниране на натрупани резултати с текущия елемент срещу комбиниране на натрупани резултати) на две места: акумулатор и комбинатор. Ако направите грешка в една от тези функции, резултатът се различава в зависимост от начина, по който изпълнявате потока. - person endertunc; 13.10.2020
comment
Страхотен отговор, но ненужно теоретичен. Ако го прочетох/разбрах преди, нямаше да публикувам този: stackoverflow.com/questions/64403813/ - person igobivo; 17.10.2020
comment
Страхотно обяснение, някои от тези факти трябва да са в reduce Javadoc, особено тези относно последователния/паралелен поток и комбинатора. - person Gerard Bosch; 25.10.2020

Тъй като харесвам драскулки и стрелки за изясняване на концепции... да започваме!

От низ към низ (последователен поток)

Да предположим, че имате 4 низа: вашата цел е да свържете такива низове в един. По принцип започвате с тип и завършвате със същия тип.

Можете да постигнете това с

String res = Arrays.asList("one", "two","three","four")
        .stream()
        .reduce("",
                (accumulatedStr, str) -> accumulatedStr + str);  //accumulator

и това ви помага да визуализирате какво се случва:

въведете описание на изображението тук

Акумулаторната функция преобразува, стъпка по стъпка, елементите във вашия (червен) поток до крайната намалена (зелена) стойност. Функцията акумулатор просто трансформира String обект в друг String.

От низ към int (паралелен поток)

Да предположим, че имате същите 4 низа: вашата нова цел е да сумирате дължините им и искате да паралелизирате потока си.

Това, от което се нуждаете, е нещо подобно:

int length = Arrays.asList("one", "two","three","four")
        .parallelStream()
        .reduce(0,
                (accumulatedInt, str) -> accumulatedInt + str.length(),                 //accumulator
                (accumulatedInt, accumulatedInt2) -> accumulatedInt + accumulatedInt2); //combiner

и това е схема на случващото се

въведете описание на изображението тук

Тук акумулаторната функция (a BiFunction) ви позволява да трансформирате вашите String данни в int данни. Тъй като потокът е паралелен, той е разделен на две (червени) части, всяка от които се разработва независимо една от друга и дава също толкова частични (оранжеви) резултати. Дефинирането на комбинатор е необходимо, за да се осигури правило за обединяване на частични int резултати в крайния (зелен) int.

От низ към int (последователен поток)

Ами ако не искате да паралелизирате потока си? Е, така или иначе трябва да се предостави комбинатор, но той никога няма да бъде извикан, като се има предвид, че няма да се получат частични резултати.

person Luigi Cortese    schedule 28.11.2015
comment
Благодаря за това. Дори нямах нужда да чета. Иска ми се просто да бяха добавили шибана функция за сгъване. - person Lodewijk Bogaards; 04.03.2016
comment
@LodewijkBogaards радвам се, че помогна! JavaDoc тук наистина е доста загадъчен - person Luigi Cortese; 04.03.2016
comment
@LuigiCortese В паралелния поток винаги ли разделя елементите на двойки? - person TheLogicGuy; 18.05.2017
comment
Оценявам вашия ясен и полезен отговор. Искам да повторя малко от това, което казахте: Е, така или иначе трябва да се предостави комбинатор, но той никога няма да бъде извикан. Това е част от Прекрасния нов свят на функционалното програмиране на Java, което, както съм се уверявал безброй пъти, прави кода ви по-сбит и по-лесен за четене. Да се ​​надяваме, че примери за (кавички с пръсти) сбита яснота като този остават малко и рядко. - person dnuttle; 23.05.2019
comment
Ще бъде МНОГО по-добре да илюстрирам намаление с осем струни ... - person Ekaterina Ivanova iceja.net; 02.06.2020
comment
Това е най-добрият отговор. Ръцете надолу. - person Mingtao Sun; 15.12.2020

Няма версия за намаляване, която приема два различни типа без комбинатор, тъй като не може да се изпълнява паралелно (не знам защо това е изискване). Фактът, че акумулатор трябва да е асоциативен, прави този интерфейс почти безполезен, тъй като:

list.stream().reduce(identity,
                     accumulator,
                     combiner);

Дава същите резултати като:

list.stream().map(i -> accumulator(identity, i))
             .reduce(identity,
                     combiner);
person quiz123    schedule 04.09.2015
comment
Такъв map трик в зависимост от конкретни accumulator и combiner може доста да забави нещата. - person Tagir Valeev; 04.09.2015
comment
Или го ускорете значително, тъй като сега можете да опростите accumulator, като изпуснете първия параметър. - person quiz123; 04.09.2015
comment
Възможно е паралелно намаляване, зависи от вашето изчисление. Във вашия случай трябва да сте наясно със сложността на комбинатора, но също и на акумулатора на идентичност спрямо други случаи. - person LoganMzz; 27.06.2017