加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 综合聚焦 > 服务器 > 安全 > 正文

建议在多个值上优化简单的Scala foldLeft?

发布时间:2020-12-16 18:38:31 所属栏目:安全 来源:网络整理
导读:我正在重新实现一些从 Java到Scala的代码(一种简单的贝叶斯推理算法,但这并不重要).我希望以尽可能最高效的方式实现它,同时通过尽可能避免可变性来保持代码的清洁和功能. 以下是Java代码的片段: // initialize double lP = Math.log(prior); double lPC = M
我正在重新实现一些从 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和map方法.由于我有两个值,我正在积累,累加器是一个元组:

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

不幸的是,这段代码的执行速度比Java快5倍(使用简单且不精确的度量标准;只需在循环中调用代码10000次).一个缺点很明显;我们遍历列表两次,一次是在map中调用,另一次是在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
    })

这个更好!它的执行速度比Java代码差3倍.我的下一个预感是,在折叠的每个步骤中创建所有新元组可能需要花费一些成本.所以我决定尝试两次遍历列表的版本,但不创建元组.

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

这与先前版本大致相同(比Java版本慢3倍).并不奇怪,但我很有希望.

所以我的问题是,是否有更快的方法在Scala中实现这个Java代码段,同时保持Scala代码干净,避免不必要的可变性并遵循Scala惯用法?我确实希望最终在并发环境中使用此代码,因此保持不变性的价值可能会超过单个线程中较慢的性能.

解决方法

首先,您的一些惩罚可能来自您正在使用的收集类型.但是大部分可能是通过运行循环两次实际上无法避免的对象创建,因为数字必须被加框.

相反,您可以创建一个可变类来为您累积值:

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

你会好起来的.

(可以随意使用非数学符号,但由于你基本上是概率乘法,乘法符号似乎更可能给出一个直观的想法,而不是包含概率或某些东西.)

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读