Scala 流性能

Question

递归代数数据类型和惰性求值的有用性的典型示例是游戏算法，例如如约翰·休斯 (John Hughes) 著名的 WhyFP 论文 (Comp. J., Vol. 32, No. 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 或惰性结构？

编辑:添加了一些性能结果和实际代码:
在 link是懒人版。

懒惰版本(scala 2.9.1): Time for gametree creation: 0.031s and for finding the solution 133.216s.
树创建中没有转换，即映射到极小极大中的集合 Time for gametree creation: 4.791s and for finding the solution 6.088s.
在游戏树创建中转换为列表 Time for gametree creation: 4.438s and for finding the solution 5.601s.

Answer 1

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

JAVA_OPTS="-Xprof" scala TicTacToe

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