Scala Streams性能

Question

递归代数数据类型的有用性和惰性计算的典型的例子是一种游戏算法,例如,如示于由John休斯著名WhyFP纸(对比例J.,第32卷,第2号,1989年).

使用Scala实现它,并使用延迟评估Stream[Tree[A]]游戏的每个子树导致trait 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)))

并且您可以对实际算法实施修剪,评分和并行化策略,例如执行作业的minimax,并评估树的必要部分:

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 

然而,无限流引入了显着的性能损失,并且使用eager list(ts: List[Tree[A]])解决相同的游戏树的效率提高了25倍.

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

编辑:添加了一些性能结果和实际代码:在链接中是懒惰版本.

懒惰版(scala 2.9.1): Time for gametree creation: 0.031s and for finding the solution 133.216s.

树创建中没有转换,即在minimax中映射集 Time for gametree creation: 4.791s and for finding the solution 6.088s.

转换为gameTree创建中的列表 Time for gametree creation: 4.438s and for finding the solution 5.601s.

Answer 1

如果您想快速粗略地了解时间的去向，可以尝试运行：

JAVA_OPTS="-Xprof" scala TicTacToe

正如评论中所述，我无法重现您的经历。