Соблюдает ли агрегат порядок при параллельном сборе?

в scala у меня есть параллельный Iterable элементов, и я хочу перебирать их и каким-то образом агрегировать результаты, но по порядку. я упрощу свой вариант использования и скажу, что мы начинаем с Iterable целых чисел и хотим объединить строковое представление их параллельно, с результатом в порядке.

возможно ли это с помощью сгиба или агрегата? из документации неясно, какие методы работают параллельно, но поддерживают порядок.


scala parallel-collections
person Heinrich Schmetterling    schedule 10.06.2011    source источник

Ответы (3)


arrow_upward
4
arrow_downward

Да, порядок гарантированно сохраняется для операций сворачивания/объединения/уменьшения в параллельных коллекциях. Это не очень хорошо задокументировано. Хитрость заключается в том, что операция, которую нужно свернуть, должна быть ассоциативной (и, следовательно, допускающей произвольное разделение и рекомбинацию), но не обязана быть коммутативной (и поэтому не может быть безопасно переупорядочена). Конкатенация строк — прекрасный пример ассоциативной некоммутативной операции, поэтому свертку можно выполнять параллельно.

val concat = myParallelList.map(_.toString).reduce(_+_)
person Dave Griffith    schedule 10.06.2011
comment
Есть ли что-нибудь, что могло бы применить дополнительные оптимизации в случае ассоциативной и коммутативной операции, такой как + или *? - person Erik Kaplun; 31.03.2014

arrow_upward
1
arrow_downward

Для сгибов: foldRight и foldLeft нельзя обрабатывать параллельно, вам нужно будет использовать новый метод fold (дополнительная информация здесь).

Как и fold, aggregate может выполнять свою работу параллельно: он «последовательно обходит элементы в разных разделах» (Scaladoc), хотя похоже, что вы не имеете прямого влияния на выбор разделов.

person Jean-Philippe Pellet    schedule 10.06.2011
comment
Филипп, спасибо, я понимаю, что нужно использовать фолд или агрегат - в документации фолда указано, что порядок не гарантируется. я не могу найти эту информацию для агрегата. - person Heinrich Schmetterling; 10.06.2011
comment
Когда порядок гарантирован, это было бы не очень параллельно, не так ли? - person Jens Schauder; 10.06.2011
comment
@Jens Представьте список (a, b, c, d) и объедините его вместе, сначала выполняя a + b и c + d параллельно, и, наконец, выполняя ab + cd. Вы можете выполнять работу параллельно и сохранять порядок коллекции. - person ziggystar; 10.06.2011
comment
Теперь я понимаю, что вы имеете в виду под порядком. Я думал, что добавление c+d перед добавлением b+c будет нарушением порядка. Что, в свою очередь, должно было бы произойти после a+b, что привело бы к последовательному процессу. - person Jens Schauder; 10.06.2011

arrow_upward
0
arrow_downward

Я ДУМАЮ, что сохранение «порядка» в смысле комментария к ответу Жана-Филиппа Пелле гарантировано из-за того, как реализованы параллельные коллекции в соответствии с публикацией Одерского (http://infoscience.epfl.ch/record/150220 /files/pc.pdf) Если часть, которая разбивает вашу коллекцию, ведет себя хорошо в отношении порядка.

т. е. если у вас есть элементы a ‹ b ‹ c, а a и c попадают в один раздел, из этого следует, что b также находится в том же разделе.

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

person Jens Schauder    schedule 10.06.2011