Предложения по оптимизации простого Scala foldLeft по нескольким значениям?

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

Вместо этого вы можете создать изменяемый класс, который накапливает для вас значения:

class LogOdds(var lp: Double = 0, var lpc: Double = 0) {
  def *=(p: Double) = {
    if (isValidProbability(p)) {
      lp += logProb(p)
      lpc += logProb(1-p)
    }
    this  // Pass self on so we can fold over the operation
  }
  def toTuple = (lp, lpc)
}

Теперь, хотя вы можете использовать это небезопасно, в этом нет необходимости. Фактически, вы можете просто сложить его.

annotations.foldLeft(new LogOdds()) { (r,ann) => r *= ann.getProbability } toTuple

Если вы используете этот паттерн, вся изменчивая небезопасность скрывается внутри складки; он никогда не ускользнет.

Теперь вы не можете выполнить параллельное сгибание, но вы можете выполнить агрегирование, которое похоже на складывание с дополнительной операцией по объединению частей. Итак, вы добавляете метод

def **(lo: LogOdds) = new LogOdds(lp + lo.lp, lpc + lo.lpc)

в LogOdds, а затем

annotations.aggregate(new LogOdds())(
  (r,ann) => r *= ann.getProbability,
  (l,r) => l**r
).toTuple

и тебе будет хорошо идти.

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

Вы можете реализовать хвостовой рекурсивный метод, который будет преобразован компилятором в цикл while, следовательно, должен быть таким же быстрым, как версия Java. Или вы можете просто использовать цикл - против него нет закона, если он просто использует локальные переменные в методе (см., Например, обширное использование в исходном коде коллекций Scala).

def calc(lst: List[Annotation], lP: Double = 0, lPC: Double = 0): (Double, Double) = {
  if (lst.isEmpty) (lP, lPC)
  else {
    val prob = lst.head.getProbability
    if (isValidProbability(prob)) 
      calc(lst.tail, lP + logProb(prob), lPC + logProb(1 - prob))
    else 
      calc(lst.tail, lP, lPC)
  }
}

Преимущество сворачивания заключается в том, что его можно распараллеливать, что может привести к тому, что он будет быстрее, чем версия Java на многоядерной машине (см. Другие ответы).

В качестве побочного примечания: вы можете избежать двойного идиоматического обхода списка, используя _ 1_:

val probs = annotations.view.map(_.getProbability).filter(isValidProbability)

val (lP, lPC) = ((logProb(prior), logProb(1 - prior)) /: probs) {
   case ((pa, ca), p) => (pa + logProb(p), ca + logProb(1 - p))
}

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

Во-первых, давайте рассмотрим проблему производительности: нет способа реализовать его так же быстро, как Java, кроме как с помощью циклов while. По сути, JVM не может оптимизировать цикл Scala в той степени, в которой он оптимизирует цикл Java. Причины этого вызывают беспокойство даже среди людей, занимающихся JVM, потому что они также мешают параллельной работе с библиотеками.

Теперь, возвращаясь к производительности Scala, вы также можете использовать .view, чтобы избежать создания новой коллекции на этапе map, но я думаю, что этап map всегда приведет к снижению производительности. Дело в том, что вы конвертируете коллекцию в одну, параметризованную на Double, которую нужно упаковывать и распаковывать.

Однако есть один возможный способ его оптимизации: сделать его параллельным. Если вы вызываете .par на annotations, чтобы сделать его параллельной коллекцией, вы можете затем использовать fold:

val parAnnot = annotations.par
val lP = parAnnot.map(_.getProbability).fold(math.log(prior)) ((r,p) => {
   if(isValidProbability(p)) r + logProb(p) else r
})
val lPC = parAnnot.map(_.getProbability).fold(math.log(1-prior)) ((r,p) => {
  if(isValidProbability(p)) r + logProb(1-p) else r
})

Чтобы избежать отдельного map шага, используйте aggregate вместо fold, как предлагает Рекс.

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

В параллельных коллекциях это может сначала filter окупиться за действительные аннотации. Или, может быть, collect.

val parAnnot = annottions.par.view map (_.getProbability) filter (isValidProbability(_)) force;

or

val parAnnot = annotations.par collect { case annot if isValidProbability(annot.getProbability) => annot.getProbability }

Во всяком случае, эталон.

В настоящее время невозможно взаимодействовать с библиотекой коллекций scala без бокса. Итак, что такое примитивные double в Java, будет постоянно упаковываться и распаковываться в операции fold, даже если вы не упаковываете их в Tuple2 (который является специализированным, но, конечно, вы уже платите накладные расходы на создание новых объектов каждый раз).