Un ejemplo canónico de la utilidad de los tipos de datos algebraicos recursivos y la evaluación diferida es un algoritmo de juego, p. como se muestra en el famoso documento WhyFP de John Hughes (Comp. J., Vol. 32, No. 2, 1989).Scala Streams Performance
Implementar con Scala, y el uso de pereza evaluado Stream[Tree[A]] para cada subárbol de un juego lleva a trait Tree[A] con una definición:
sealed trait Tree[A]
case class Branch[A](ts: Stream[Tree[A]]) extends Tree[A]
case class Leaf[A](a: A) extends Tree[A]
Ahora, un perezoso evaluado, posiblemente infinita, juego puede ser presentada como:
gameTree(b: Board): Tree[Board] =
if (b.isAtEndPos) Leaf(b)
else Branch(b.emptySlots.toStream.map((pos: Int) => gameTree(b addTic pos)))
y se puede aplicar una poda, la puntuación y la estrategia de paralelización a la el algoritmo real, es decir, por ejemplo, Minimax, que hace el trabajo, y evalúa las partes del árbol que son necesarios:
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
Sin embargo, el flujo infinito introduce una penalización de rendimiento significativa, y resolver árbol de juego idéntico utilizando la lista ansiosos (ts: List[Tree[A]]) es 25 veces más eficiente.
¿Hay alguna manera de utilizar Streams o estructuras perezosas en Scala de forma efectiva en situaciones similares?
Editar: añadido algunos resultados de rendimiento, y el código real: En link es la versión perezosa.
versión Lazy (Scala 2.9.1): Time for gametree creation: 0.031s and for finding the solution 133.216s.
No hay conversiones en la creación de árbol, es decir el mapeo sobre conjuntos en minimax Time for gametree creation: 4.791s and for finding the solution 6.088s.
la conversión a la lista en la creación GameTree Time for gametree creation: 4.438s and for finding the solution 5.601s.
"es 25 veces más eficiente": ¿desea publicar un proyecto con ambas variaciones y la plataforma de evaluación comparativa? – retronym
No se puede reproducir en mi máquina. Obtengo, para creación/solución: 'Stream's: 0.024s/6.568s,' List's: 4.189s/5.382s. Entonces 'Stream's son más rápidos para mí (cuando sumas ambas veces). – Philippe
Obtengo resultados muy similares a Philippe; Corriente: 0.23s/6.12s vs Lista: 4.07s/5.16s. Parece que Streams funciona mejor en este caso. También estoy usando Scala 2.9.1, por lo que las únicas diferencias en las que puedo pensar son una JVM diferente, configuraciones de JVM diferentes o algunos problemas extraños que dependen del hardware. – nomad