Tạo một O (1) -memory Lặp lại từ một đối tượng ban đầu và một hàm tạo đối tượng tiếp theo, trong Scala

Question

Tôi muốn có một cách thuận tiện để tạo ra một Iterable, cho một đối tượng ban đầu và một hàm để tạo ra đối tượng tiếp theo từ hiện tại, tiêu thụ bộ nhớ O (1) (tức là nó không lưu vào bộ nhớ cache kết quả cũ; nếu bạn muốn lặp lại lần thứ hai, hàm này sẽ được áp dụng lại).

Dường như không có thư viện hỗ trợ cho việc này. Trong Scala 2.8, phương pháp scala.collection.Iterable.iterate có chữ ký

def iterate [A] (start: A, len: Int)(f: (A) ⇒ A) : Iterable[A] 

vì thế nó đòi hỏi bạn phải xác định có bao nhiêu ứng dụng chức năng lặp bạn quan tâm trước thời hạn, và sự hiểu biết của tôi về các tài liệu là Iterable.iterate thực sự tính toán tất cả các giá trị ngay. Mặt khác, phương pháp scala.collection.Iterator.iterate có chữ ký

def iterate [T] (start: T)(f: (T) ⇒ T) : Iterator[T] 

trông tuyệt vời, nhưng chúng tôi chỉ nhận được một Iterator mà không cung cấp tất cả sự tiện lợi của map, filter và bạn bè.

Có phương pháp thư viện thuận tiện để sản xuất những gì tôi muốn không?

và nếu không,

Ai đó có thể đề nghị các Scala mã 'ngôn ngữ giao tiếp' để làm điều này?

Để tóm tắt, được đưa ra một đối tượng ban đầu a: A, và một hàm f: A => A, tôi muốn một TraversableLike (ví dụ, có thể là một Iterable) mà tạo ra a, f(a), f(f(a)), ..., và sử dụng O (1) bộ nhớ, với map, filter vv chức năng mà cũng trả lại cái gì đó là O (1) trong bộ nhớ.

Answer 1

Iterator.iterate bản demo với bộ lọc:

object I { 
    def main(args:Array[String]) { 
    val mb = 1024 * 1024 
    val gen = Iterator.iterate(new Array[Int](10 * mb)){arr => 
     val res = new Array[Int](10 * mb) 
     arr.copyToArray(res) 
     println("allocated 10mb") 
     res(0) = arr(0) + 1 // store iteration count in first elem of new array 
     res 
    } 
    // take 1 out of 100 
    val gen2 = gen filter (arr => arr(0) % 100 == 0) 
    // print first 10 filtered 
    gen2.take(10).foreach { arr => println("filtered " + arr(0)) } 
    } 
} 

(điều này có thể không làm việc trong REPL như là bước PRINT có thể gây chuyện với quản lý bộ nhớ)

JAVA_OPTS="-Xmx128m" scala -cp classes I sẽ cho thấy rằng các công trình lọc và là lười biếng. Nếu nó không được thực hiện trong bộ nhớ liên tục sẽ gây ra một lỗi heap (vì nó phân bổ một cái gì đó như 900 * 10mb).

Sử dụng JAVA_OPTS="-Xmx128m -verbose:gc" scala -cp classes I để xem các sự kiện thu thập rác.

Answer 2

Stream sẽ làm những gì bạn muốn, chỉ cần không giữ các ô; chỉ lặp qua các giá trị.

Đó là một quan niệm sai lầm phổ biến đáng buồn trôi nổi xung quanh luồng đó vốn đã lưu vào bộ nhớ cache mọi giá trị mà chúng tính toán.

Nếu bạn viết này:

val s1: Stream[Thing] = initialValue #:: «expression computing next value» 

sau đó thực sự mỗi giá trị được tạo ra bởi con suối được giữ lại, nhưng điều này là không cần thiết. Nếu bạn viết:

def s2: Stream[Thing] = initialValue #:: «expression computing next value» 

và nếu người gọi chỉ lặp trên giá trị của dòng nhưng không nhớ giá trị Suối bản thân (cụ thể là bất kỳ của các tế bào khuyết điểm của nó), sau đó không duy trì không mong muốn sẽ xảy ra. Tất nhiên, trong công thức này, mọi cuộc gọi tạo ra một Stream mới bắt đầu từ một giá trị ban đầu cố định. Điều đó không cần thiết:

def s3(start: Thing): Stream[Thing] = start #:: «expression computing next value» 

Điều bạn cần chú ý là chuyển một phương thức Stream. Làm như vậy sẽ nắm bắt phần đầu của luồng được truyền trong tham số phương thức. Một cách xung quanh điều này là xử lý luồng bằng mã đệ quy đuôi.

Answer 3

Iterator chính là điều bạn muốn. Và iterator có bản đồ, bộ lọc, takeWhile và nhiều phương thức khác là O (1) trong bộ nhớ. Tôi không nghĩ rằng có một loại bộ sưu tập khác với O (1) trong bộ nhớ.

Answer 4

val it = new Iterable[Int] { 
    def iterator = Iterator.iterate(0)(_+1) 
    override 
    def toString: String = "Infinite iterable" 
} 

Đừng dùng thử REPL (ngoại trừ nhúng nó bên trong một đối tượng hoặc lớp), vì REPL sẽ cố gắng in và không sử dụng toString.