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

Question

Я перепрограммирую некоторый код (простой байесовский алгоритм вывода, но это не очень важно) от Java до Scala. Я хотел бы реализовать его наиболее эффективным образом, сохраняя при этом код чистым и функциональным, избегая, насколько возможно, изменчивости.

Вот фрагмент кода Java:

// initialize 
    double lP = Math.log(prior); 
    double lPC = Math.log(1-prior); 

    // accumulate probabilities from each annotation object into lP and lPC 
    for (Annotation annotation : annotations) { 
     float prob = annotation.getProbability(); 
     if (isValidProbability(prob)) { 
      lP += logProb(prob); 
      lPC += logProb(1 - prob); 
     } 
    } 

Довольно просто, не так ли? Поэтому я решил использовать Scala foldLeft и методы карты для моей первой попытки. Поскольку у меня есть два значения я накапливался в течение, аккумулятор является кортежем:

val initial = (math.log(prior), math.log(1-prior)) 
    val probs = annotations map (_.getProbability) 
    val (lP,lPC) = probs.foldLeft(initial) ((r,p) => { 
     if(isValidProbability(p)) (r._1 + logProb(p), r._2 + logProb(1-p)) else r 
    }) 

К сожалению, этот код работает примерно в 5 раз медленнее, чем Java (с использованием простого и неточной метрики, просто называется код 10000 раз петля). Один недостаток довольно ясен; мы перебираем списки дважды, один раз в вызове карты, а другой - в foldLeft. Итак, вот версия, которая перемещается по списку один раз.

val (lP,lPC) = annotations.foldLeft(initial) ((r,annotation) => { 
     val p = annotation.getProbability 
     if(isValidProbability(p)) (r._1 + logProb(p), r._2 + logProb(1-p)) else r 
    }) 

Это лучше! Он работает примерно в 3 раза хуже, чем Java-код. Моя следующая догадка заключалась в том, что, вероятно, некоторые затраты связаны с созданием всех новых кортежей на каждом этапе складки. Поэтому я решил попробовать версию, которая пересекает список дважды, но без создания кортежей.

val lP = annotations.foldLeft(math.log(prior)) ((r,annotation) => { 
     val p = annotation.getProbability 
     if(isValidProbability(p)) r + logProb(p) else r 
    }) 
    val lPC = annotations.foldLeft(math.log(1-prior)) ((r,annotation) => { 
     val p = annotation.getProbability 
     if(isValidProbability(p)) r + logProb(1-p) else r 
    }) 

Выполняется примерно так же, как и предыдущая версия (в 3 раза медленнее, чем версия Java). Не удивительно, но я надеялся.

Итак, мой вопрос в том, есть ли более быстрый способ реализовать этот фрагмент Java в Scala, сохраняя при этом код Scala чистым, избегая ненужной изменчивости и следящих за иконами Scala? Я ожидаю использовать этот код в конечном итоге в параллельной среде, поэтому значение сохранения неизменяемости может перевесить более медленную производительность в одном потоке.

Answer 1

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

Answer 2

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

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

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 

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

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

Answer 3

Как своего рода примечание стороны: вы можете избежать обхода списка в два раза больше идиоматический с помощью view:

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)) 
} 

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

Answer 4

Во-первых, давайте обратимся к проблеме с производительностью: не существует способа реализовать ее так же быстро, как 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, как это было предложено Rex.

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

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

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

или

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

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

Answer 5

Вы можете реализовать метод tail-recursive, который будет преобразован в цикл 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 на многоядерной машине (см другие ответы).