Scala Streams性能

发布时间：2020-12-16 09:11:17 所属栏目：安全来源：网络整理

导读：递归代数数据类型和懒惰评估的有用性的典型例子是游戏算法,例如,如John Hughes着名的WhyFP论文(Comp.J.,Vol.32,No.2,1989)所示. 使用Scala实现,并为游戏的每个子树使用懒惰评估的Stream [Tree [A]],导致具有定义的特征Tree [A] sealed trait Tree[A]case cla

递归代数数据类型和懒惰评估的有用性的典型例子是游戏算法,例如,如John Hughes着名的WhyFP论文(Comp.J.,Vol.32,No.2,1989)所示.

使用Scala实现,并为游戏的每个子树使用懒惰评估的Stream [Tree [A]],导致具有定义的特征Tree [A]

sealed trait Tree[A]
case class Branch[A](ts: Stream[Tree[A]]) extends Tree[A]
case class Leaf[A](a: A) extends Tree[A]

现在一个懒惰的评估,可能无限的游戏可以表现为：

gameTree(b: Board): Tree[Board] = 
  if (b.isAtEndPos) Leaf(b) 
  else Branch(b.emptySlots.toStream.map((pos: Int) => gameTree(b addTic pos)))

您可以实施修剪,评分和并行化策略
实际的算法,例如作业的最小值,以及
评估需要的树的部分：

def maximize(tree: Tree[Board]): Int = tree match {
  case Leaf(board) => board.score
  case Branch(subgames) => 
     subgames.map((tree: Tree[Board]) => minimize(tree)).max
} ...
def minimize // symmetrically

然而,无限流引入了显着的性能损失,并且使用热切列表(ts：List [Tree [A]])来解决相同的游戏树的效率是25倍.

在类似的情况下,有没有办法在Scala中有效地使用Streams或懒惰结构？

编辑：添加一些性能结果和实际代码：
在link是懒惰的版本.

懒惰版(scala 2.9.1)：
创建创建时间：0.031s,并找到解决方案133.216s.

在树创建中没有转换,即以最小值映射集合
创建时间：4.791s和查找解决方案6.088s.

转换到游戏中的列表创建
创建时间：4.438s和查找解决方案5.601s.

解决方法

如果你想快速粗略地了解时间的过去,你可以尝试运行：

JAVA_OPTS="-Xprof" scala TicTacToe

如在评论中所说,我不能重现你的经验.

（编辑：李大同）

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