建议在多个值上优化简单的Scala foldLeft?
我正在重新实现一些从
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 你会好起来的. (可以随意使用非数学符号,但由于你基本上是概率乘法,乘法符号似乎更可能给出一个直观的想法,而不是包含概率或某些东西.) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |