Производительность потоков Scala

) Каноническим примером полезности рекурсивных алгебраических типов данных и ленивого вычисления является игровой алгоритм, например, как показано в знаменитой статье WhyFP Джона Хьюза ( Comp. J., Vol. 32, No. 2, 1989 ).

Реализация его с помощью Scala и использование лениво оцененного Stream [Дерево [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 в подобных ситуациях?

Изменить: добавлены некоторые результаты производительности и фактический код: В ссылка - это ленивая версия.

Ленивая версия (scala 2.9.1): Время на создание дерева игр: 0,031 с и на поиск решения 133,216 с.

Никаких преобразований при создании дерева, т.е. отображение по множествам в минимакс Время создания игрового дерева: 4.791s и для поиска решения 6.088s.

Преобразование в список при создании GameTree. Время на создание дерева игр: 4,438 с и на поиск решения 5,601 с.