Un esempio canonico dell'utilità dei tipi di dati algebrici ricorsivi e della valutazione lazy è un algoritmo di gioco, ad es. come mostrato nel famoso documento WhyFP di John Hughes (Comp. J., Vol. 32, No. 2, 1989).Scala Streaming Performance
Implementazione con Scala, e l'utilizzo di pigramente valutato Stream[Tree[A]] per ogni sottostruttura di un gioco porta a trait Tree[A] con una definizione:
sealed trait Tree[A]
case class Branch[A](ts: Stream[Tree[A]]) extends Tree[A]
case class Leaf[A](a: A) extends Tree[A]
Ora un pigramente valutato, possibilmente infinita, gioco può essere presentato come:
gameTree(b: Board): Tree[Board] =
if (b.isAtEndPos) Leaf(b)
else Branch(b.emptySlots.toStream.map((pos: Int) => gameTree(b addTic pos)))
ed è possibile implementare una potatura, punteggio e la strategia di parallelizzazione al l'algoritmo vero e proprio, cioè ad esempio minimax, che fa il lavoro, e valuta le parti della pianta che sono necessarie:
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
Tuttavia, il flusso infinito introduce una sanzione significativa le prestazioni e risolvere albero di gioco identico utilizzando lista ansiosi (ts: List[Tree[A]]) è 25 volte più efficiente.
Esiste un modo per utilizzare efficacemente flussi o strutture pigri in Scala in situazioni simili?
Modifica: aggiunto alcuni risultati delle prestazioni e codice effettivo: In link è la versione lenta.
versione pigro (scala 2.9.1): Time for gametree creation: 0.031s and for finding the solution 133.216s.
Nessuna conversione nella creazione albero, cioè la mappatura su insiemi in Minimax Time for gametree creation: 4.791s and for finding the solution 6.088s.
Conversione di elencare nella creazione gameTree Time for gametree creation: 4.438s and for finding the solution 5.601s.
"è 25 volte più efficiente" - cura di pubblicare un progetto con entrambe le varianti e l'impianto di benchmarking? – retronym
Impossibile riprodurre sul mio computer. Ottengo, per creazione/soluzione: 'Stream's: 0.024s/6.568s,' List's: 4.189s/5.382s. Quindi 'Stream's sono più veloci per me (quando si sommano entrambe le volte). – Philippe
Ottengo risultati molto simili a quelli di Philippe; Stream: 0.23s/6.12s vs List: 4.07s/5.16s. Quindi sembra che gli Stream stiano effettivamente meglio in questo caso. Sto anche usando la scala 2.9.1, quindi le uniche differenze a cui posso pensare sono una JVM diversa, diverse impostazioni JVM o alcuni strani problemi legati all'hardware. – nomad