Kanonicznym przykładem przydatności rekurencyjnych typów danych algebraicznych i leniwego oceniania jest algorytm gry, np. jak pokazano na słynnym artykule WhyFP autorstwa Johna Hughesa (Comp. J., Vol. 32, No. 2, 1989).Scala Streams Performance
wykonawczych w Scala, a przy użyciu leniwie oceniano Stream[Tree[A]] dla każdego poddrzewa grze prowadzi do trait Tree[A] z definicji:
sealed trait Tree[A]
case class Branch[A](ts: Stream[Tree[A]]) extends Tree[A]
case class Leaf[A](a: A) extends Tree[A]
Teraz leniwie oceniany, być nieskończony, gra może być przedstawiony jako:
gameTree(b: Board): Tree[Board] =
if (b.isAtEndPos) Leaf(b)
else Branch(b.emptySlots.toStream.map((pos: Int) => gameTree(b addTic pos)))
i można wdrożyć przycinanie, strzelając i strategii zrównoleglanie do rzeczywiste algorytm, czyli na przykład minimax, która spełnia swoje zadanie, a ocenia części drzewa, które są konieczne:
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
jednak nieskończony strumień wprowadza znaczące kara wydajność i rozwiązywania identyczną drzewo grę używając chętny listy (ts: List[Tree[A]]) jest 25 razy bardziej wydajny.
Czy istnieje sposób, aby skutecznie używać strumieni lub leniwych struktur w Scala w podobnych sytuacjach?
Edytuj: dodano niektóre wyniki wydajności i rzeczywisty kod: W wersji link jest wersja leniwy.
Lazy wersja (scala 2.9.1): Time for gametree creation: 0.031s and for finding the solution 133.216s.
Brak konwersji w tworzeniu drzewa, czyli mapowanie nad zestawami w minimax Time for gametree creation: 4.791s and for finding the solution 6.088s.
Konwersja do listy w tworzeniu gameTree Time for gametree creation: 4.438s and for finding the solution 5.601s.
"jest 25 razy bardziej efektywny" - czy chcesz opublikować projekt zawierający zarówno wariacje, jak i zestaw do testów porównawczych? – retronym
Nie można odtworzyć na moim komputerze. Dostaję, dla stworzenia/rozwiązania: 'Stream's: 0.024s/6.568s,' List's: 4.189s/5.382s. Więc 'Stream's są dla mnie szybsze (gdy dodasz oba razy). – Philippe
Otrzymuję bardzo podobne wyniki jak Philippe; Strumień: 0,23 s/6,12 s vs Lista: 4,07 s/5,16 s. Wygląda więc na to, że w tym przypadku strumienie faktycznie działają lepiej. Używam również scala 2.9.1, więc jedyne różnice, o których mogę myśleć, to albo inna maszyna JVM, różne ustawienia JVM, albo dziwne, zależne od sprzętu problemy. – nomad