Ví dụ kinh điển về tính hữu dụng của các loại dữ liệu đại số đệ quy và đánh giá lười biếng là thuật toán trò chơi, ví dụ: như thể hiện trong bài báo WhyFP nổi tiếng của John Hughes (Phần J., Tập 32, Số 2, 1989).Hiệu suất luồng Scala
Thực hiện nó với Scala, và sử dụng một cách lười biếng đánh giá Stream[Tree[A]] cho mỗi cây con của một trò chơi dẫn đến trait Tree[A] với một định nghĩ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]
Bây giờ một uể oải đánh giá, có thể là vô hạn, trò chơi có thể được trình bày như:
gameTree(b: Board): Tree[Board] =
if (b.isAtEndPos) Leaf(b)
else Branch(b.emptySlots.toStream.map((pos: Int) => gameTree(b addTic pos)))
và bạn có thể thực hiện chiến lược cắt tỉa, ghi điểm và song song với thuật toán thực tế, ví dụ: minimax mà không được công việc, và đánh giá các bộ phận của cây đó là cần thiết:
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
Tuy nhiên, các dòng vô hạn giới thiệu một hình phạt hiệu suất đáng kể, và giải quyết các cây trò chơi giống hệt nhau sử dụng danh sách háo hức (ts: List[Tree[A]]) được 25 lần hiệu quả hơn.
Có cách nào để sử dụng Luồng hoặc cấu trúc lười biếng trong Scala có hiệu quả trong các tình huống tương tự không?
Chỉnh sửa: thêm một số kết quả hiệu suất và mã thực tế: Trong link là phiên bản lười.
Lazy phiên bản (scala 2.9.1): Time for gametree creation: 0.031s and for finding the solution 133.216s.
Không có chuyển đổi trong việc tạo ra cây, tức là lập bản đồ trên bộ trong minimax Time for gametree creation: 4.791s and for finding the solution 6.088s.
Chuyển đổi niêm yết trong việc tạo ra gameTree Time for gametree creation: 4.438s and for finding the solution 5.601s.
"hiệu quả gấp 25 lần" - chăm sóc để đăng dự án có cả hai biến thể và giàn khoan đo điểm chuẩn? – retronym
Không thể sao chép trên máy của tôi. Tôi nhận được, để tạo/giải pháp: 'Stream's: 0.024s/6.568s,' List's: 4.189s/5.382s. Vì vậy, 'Stream' là nhanh hơn cho tôi (khi bạn thêm lên cả hai lần). – Philippe
Tôi nhận được kết quả rất giống với Philippe; Luồng: 0.23s/6.12s so với Danh sách: 4.07s/5.16s. Vì vậy, có vẻ như các luồng thực sự hoạt động tốt hơn trong trường hợp này. Tôi cũng đang sử dụng scala 2.9.1, do đó, những khác biệt duy nhất tôi có thể nghĩ đến là JVM khác nhau, các cài đặt JVM khác nhau hoặc một số vấn đề phụ thuộc phần cứng lạ. – nomad