Пример агрегатной функции Scala

Ответ 1

Агрегатная функция этого не делает (за исключением того, что это очень общая функция, и ее можно использовать для этого). Вы хотите groupBy. Ближе к минимуму. Когда вы начинаете с Seq[(String, String)] и группируете, беря первый элемент в кортеже (то есть (String, String) => String), он возвращает Map[String, Seq[(String, String)]). Затем вам нужно отбросить первый параметр в значениях Seq [String, String)].

Так

list.groupBy(_._1).mapValues(_.map(_._2))

Там вы получите Map[String, Seq[(String, String)]. Если вы хотите использовать Seq вместо Map, вызовите toSeq для результата. Я не думаю, что у вас есть гарантия на заказ в результате Seq, хотя

Агрегат является более сложной функцией.

Сначала рассмотрим ReduLeft и ReduRight. Пусть as будет непустой последовательностью as = Seq(a1,... an) элементов типа A, а f: (A,A) => A это способ объединить два элемента типа A в один. Я отмечу это как бинарный оператор @, a1 @a2 а не f(a1, a2). as.reduceLeft(@) будет вычислять (((a1 @a2) @a3)... @an). reduceRight поставит круглые скобки в другую сторону (a1 @(a2 @... @an)))). Если @ оказывается ассоциативным, то все равно, какие круглые скобки. Можно было бы вычислить это как (a1 @... @ap) @(ap+1 @[email protected]) (внутри 2 больших парантезов тоже могут быть парантезы, но об этом не стоит беспокоиться). Тогда можно было бы выполнить две части параллельно, в то время как вложенный брекетинг в reduLeft или reduRight заставляет полностью выполнять последовательные вычисления. Но параллельные вычисления возможны только тогда, когда известно, что @ является ассоциативным, а метод reduLeft не может этого знать.

Тем не менее, может быть метод reduce, вызывающий вызов которого будет отвечать за то, чтобы операция была ассоциативной. Затем reduce упорядочит вызовы так, как считает нужным, возможно, делая их параллельно. Действительно, такой метод есть.

Однако существует ограничение на различные методы сокращения. Элементы Seq могут быть объединены только в результат того же типа: @ должно быть (A,A) => A Но может возникнуть более общая проблема объединения их в B Каждый начинается со значения b типа B и объединяет его с каждым элементом последовательности. Оператор @ имеет вид (B,A) => B, и вычисляется один (((b @a1) @a2)... @an). foldLeft делает это. foldRight делает то же самое, но начиная с. an Там у @ операции нет шансов быть ассоциативной. Когда кто-то пишет b @a1 @a2, это должно означать (b @a1) @a2, так как (a1 @a2) будет неправильно напечатано. Так что foldLeft и foldRight должны быть последовательными.

Предположим, однако, что каждый A можно превратить в B, давайте напишем это с помощью ! a! имеет тип B Кроме того, предположим, что существует операция + (B,B) => B и что @ таково, что b @a на самом деле b + a! , Вместо того, чтобы комбинировать элементы с @, можно сначала преобразовать их все в B с помощью ! , затем объедините их с +. Это было бы как as.map(!).reduceLeft(+). И если + является ассоциативным, то это можно сделать с помощью Reduce, а не быть последовательным: as.map(!). Reduce (+). Может быть гипотетический метод as.associativeFold(b,!, +).

Агрегат очень близок к этому. Однако может оказаться, что существует более эффективный способ реализации [email protected] чем b+a! Например, если тип B равен List[A], а b @a - a :: b, то a! будет a::Nil, а b1 + b2 будет b2: b1. a :: b намного лучше, чем (a :: Nil): b. Чтобы извлечь выгоду из ассоциативности, но все еще использовать @, сначала нужно разделить b + a1! +... + an! b + a1! +... + an! , в (b + a1! + ap!) + (ap+1! +..+ an!), затем вернитесь к использованию @ с (b @a1 @an) + (ap+1! @@an). Еще нужно! на ap + 1, потому что нужно начинать с некоторого b. И + все еще необходим, появляясь между парантезами. Для этого as.associativeFold(!, +) можно изменить на as.optimizedAssociativeFold(b, !, @, +).

Вернуться к +. + является ассоциативным или, что то же самое, (B, +) является полугруппой. На практике большинство полугрупп, используемых в программировании, тоже являются моноидами, то есть они содержат нейтральный элемент z (для нуля) в B, так что для каждого b z + b= b + z= b. В этом случае ! Операция, которая имеет смысл, скорее всего, будет a! = z @a a! = z @a. Более того, поскольку z - нейтральный элемент b @[email protected] = (b + z) @a1 @an который является b + (z + a1 @an). Так что всегда можно начать агрегацию с z. Если вместо этого требуется b, вы делаете b + result в конце. Со всеми этими гипотезами мы можем сделать s.aggregate(z, @, +). Это то, что делает aggregate. @ является аргументом seqop (применяется в последовательности z @a1 @a2 @ap), а + является combop (применяется к уже частично объединенным результатам, как в (z + [email protected]@ap) + (z + [email protected]@an)).

Подводя итог, as.aggregate(z)(seqop, combop) вычисляет то же самое, что и as.foldLeft(z)( seqop) при условии, что

• (B, combop, z) является моноидом
• seqop(b,a) = combop(b, seqop(z,a))

Агрегированная реализация может использовать ассоциативность combop для группировки вычислений по своему усмотрению (однако, не обмениваясь элементами, + не должен быть коммутативным,: - нет). Это может запустить их параллельно.

Наконец, решение начальной проблемы с использованием aggregate оставлено читателю в качестве упражнения. Подсказка: реализуйте с использованием foldLeft, затем найдите z и combo которые будут удовлетворять условиям, указанным выше.

Ответ 2

Посмотрим, не помогает ли какое-либо искусство ascii. Рассмотрим сигнатуру типа aggregate:

def aggregate [B] (z: B)(seqop: (B, A) ⇒ B, combop: (B, B) ⇒ B): B

Также обратите внимание, что A относится к типу коллекции. Итак, скажем, у нас есть 4 элемента в этой коллекции, тогда aggregate может работать следующим образом:

z   A   z   A   z   A   z   A
 \ /     \ /seqop\ /     \ /    
  B       B       B       B
    \   /  combop   \   /
      B _           _ B
         \ combop  /
              B

Посмотрим на практический пример этого. Скажем, у меня есть GenSeq("This", "is", "an", "example"), и я хочу знать, сколько там персонажей. Я могу написать следующее:

Обратите внимание на использование par в следующем фрагменте кода. Вторая функция, переданная в агрегат, - это то, что вызывается после вычисления отдельных последовательностей. Scala может делать это только для множеств, которые могут быть распараллелены.

import scala.collection.GenSeq
val seq = GenSeq("This", "is", "an", "example")
val chars = seq.par.aggregate(0)(_ + _.length, _ + _)

Итак, сначала он вычислил бы это:

0 + "This".length     // 4
0 + "is".length       // 2
0 + "an".length       // 2
0 + "example".length  // 7

То, что он делает дальше, не может быть предсказано (существует более одного способа комбинирования результатов), но он может это сделать (например, в вышеизложенном ascii):

4 + 2 // 6
2 + 7 // 9

В какой момент он заканчивается с помощью

6 + 9 // 15

что дает конечный результат. Теперь это немного похоже на структуру foldLeft, но у него есть дополнительная функция (B, B) => B, которая не имеет. Однако эта функция позволяет работать параллельно!

Рассмотрим, например, что каждое из четырех вычислений начальных вычислений не зависит друг от друга и может выполняться параллельно. Следующие два (результат 6 и 9) можно запустить, как только их вычисления, от которых они зависят, закончены, но эти два могут также выполняться параллельно.

В 7 вычислениях, распараллеленных, как описано выше, может потребоваться всего лишь 3 последовательных вычисления.

Собственно, с такой небольшой коллекцией стоимость синхронного вычисления будет достаточно большой, чтобы уничтожить любые выгоды. Кроме того, если вы сложите это, это займет всего 4 вычисления. Однако, когда ваши коллекции становятся больше, вы начинаете видеть некоторые реальные выгоды.

Рассмотрим, с другой стороны, foldLeft. Поскольку он не имеет дополнительной функции, он не может распараллелить любые вычисления:

(((0 + "This".length) + "is".length) + "an".length) + "example".length

Каждая внутренняя скобка должна быть вычислена до того, как внешний может продолжить.

Ответ 3

Подпись для коллекции с элементами типа A:

def aggregate [B] (z: B)(seqop: (B, A) ⇒ B, combop: (B, B) ⇒ B): B 

• z - объект типа В, действующий как нейтральный элемент. Если вы хотите что-то подсчитать, вы можете использовать 0, если хотите создать список, начать с пустого списка и т.д.
• segop аналогичен функции, которую вы передаете методам fold. Он принимает два аргумента, первый из них тот же тип, что и нейтральный элемент, который вы передали, и представляете материал, который уже был агрегирован на предыдущей итерации, второй - следующий элемент вашей коллекции. Результат должен также иметь тип B.
• combop: это функция, объединяющая два результата в одном.

В большинстве коллекций агрегат реализован в TraversableOnce как:

  def aggregate[B](z: B)(seqop: (B, A) => B, combop: (B, B) => B): B 
    = foldLeft(z)(seqop)

Таким образом, combop игнорируется. Однако для параллельных коллекций имеет смысл , потому что seqop будет сначала применяться локально параллельно, а затем combop вызывается для завершения агрегации.

Итак, для вашего примера вы можете сначала попробовать:

val seqOp = 
  (map:Map[String,Set[String]],tuple: (String,String)) => 
    map + ( tuple._1 -> ( map.getOrElse( tuple._1, Set[String]() ) + tuple._2 ) )


list.foldLeft( Map[String,Set[String]]() )( seqOp )
// returns: Map(one -> Set(i, 1), two -> Set(2, ii), four -> Set(iv))

Затем вам нужно найти способ свернуть два мультимадра:

val combOp = (map1: Map[String,Set[String]], map2: Map[String,Set[String]]) =>
       (map1.keySet ++ map2.keySet).foldLeft( Map[String,Set[String]]() ) { 
         (result,k) => 
           result + ( k -> ( map1.getOrElse(k,Set[String]() ) ++ map2.getOrElse(k,Set[String]() ) ) ) 
       } 

Теперь вы можете использовать агрегат параллельно:

list.par.aggregate( Map[String,Set[String]]() )( seqOp, combOp )
//Returns: Map(one -> Set(i, 1), two -> Set(2, ii), four -> Set(iv))

Применяя метод "par" к списку, используя, таким образом, параллельный набор (scala.collection.parallel.immutable.ParSeq) списка, чтобы действительно использовать преимущества многоядерных процессоров. Без "par" не будет никакого увеличения производительности, поскольку агрегат не будет выполнен в параллельной коллекции.

Ответ 4

aggregate похож на foldLeft, но может выполняться параллельно.

Как missingfactor говорит, линейная версия aggregate(z)(seqop, combop) эквивалентна foldleft(z)(seqop). Это, однако, нецелесообразно в параллельном случае, когда нам нужно будет объединить не только следующий элемент с предыдущим результатом (как в обычной сложенной форме), но мы хотим разбить итерабельность на под-итерации, по которым мы называем совокупность, и необходимо объедините их снова. (В порядке слева направо, но не ассоциативно, поскольку мы могли бы объединить последние части перед кулачными частями итерации.) Это пересоединение вообще нетривиально, и поэтому требуется метод (S, S) => S to выполните это.

Определение в ParIterableLike:

def aggregate[S](z: S)(seqop: (S, T) => S, combop: (S, S) => S): S = {
  executeAndWaitResult(new Aggregate(z, seqop, combop, splitter))
}

который действительно использует combop.

Для справки aggregate определяется как:

protected[this] class Aggregate[S](z: S, seqop: (S, T) => S, combop: (S, S) => S, protected[this] val pit: IterableSplitter[T])
  extends Accessor[S, Aggregate[S]] {
    @volatile var result: S = null.asInstanceOf[S]
    def leaf(prevr: Option[S]) = result = pit.foldLeft(z)(seqop)
    protected[this] def newSubtask(p: IterableSplitter[T]) = new Aggregate(z, seqop, combop, p)
    override def merge(that: Aggregate[S]) = result = combop(result, that.result)
}

Важной частью является merge, где combop применяется с двумя субрезультатами.

Ответ 5

Вот блог о том, как агрегировать производительность на многоядерном процессоре со скамье. http://markusjais.com/scalas-parallel-collections-and-the-aggregate-method/

Вот видео на "Scala параллельных коллекциях", из "Scala Days 2011". http://days2011.scala-lang.org/node/138/272

Описание на видео

Scala Параллельные коллекции

Александер Прокопек

Абстракции параллельного программирования становятся все более важными по мере роста количества процессорных ядер. Модель программирования на высоком уровне позволяет программисту больше сосредоточиться на программе и меньше на деталях низкого уровня, таких как синхронизация и балансировка нагрузки. Scala параллельные коллекции расширяют модель программирования фреймворка Scala, обеспечивая параллельные операции над наборами данных. В обсуждении будет описана архитектура параллельной структуры коллекций, объясняющая их выполнение и проектные решения. Будут описаны реализации бетонных сборников, такие как параллельные хэш-карты и параллельные попытки хеширования. Наконец, будут показаны несколько примеров приложений, демонстрирующих на практике модель программирования.

Ответ 6

Определение источника aggregate в TraversableOnce:

def aggregate[B](z: B)(seqop: (B, A) => B, combop: (B, B) => B): B = 
  foldLeft(z)(seqop)

который не отличается от простого foldLeft. combop, кажется, нигде не используется. Я сам смущен тем, какова цель этого метода.

Ответ 7

Чтобы разъяснить объяснения тех, кто передо мной, теоретически идея такова: агрегат должен работать следующим образом (я изменил имена параметров, чтобы сделать их более ясными):

Seq(1,2,3,4).aggragate(0)(
     addToPrev = (prev,curr) => prev + curr, 
     combineSums = (sumA,sumB) => sumA + sumB)

Должен логически перевести на

Seq(1,2,3,4)
    .grouped(2) // split into groups of 2 members each
    .map(prevAndCurrList => prevAndCurrList(0) + prevAndCurrList(1))
    .foldLeft(0)(sumA,sumB => sumA + sumB)

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