Scala hiệu suất câu hỏi

Question

Trong article written by Daniel Korzekwa, ông nói rằng hiệu suất của đoạn mã sau:

list.map(e => e*2).filter(e => e>10) 

là tồi tệ hơn nhiều so với các giải pháp lặp đi lặp lại được viết bằng Java.

Mọi người có thể giải thích lý do không? Và giải pháp tốt nhất cho mã như vậy trong Scala (Tôi hy vọng nó không phải là một phiên bản lặp Java là Scala-fied)?

Answer 1

Lý do rằng mã đặc biệt là chậm là bởi vì nó làm việc trên nguyên thủy nhưng nó sử dụng các hoạt động chung, vì vậy nguyên thủy phải được đóng hộp. (Điều này có thể được cải thiện nếu List và tổ tiên của nó là chuyên ngành.) Điều này có thể sẽ làm chậm những thứ xuống bởi một yếu tố của 5 hoặc hơn.

Ngoài ra, về mặt thuật toán, các thao tác này hơi tốn kém, bởi vì bạn tạo toàn bộ danh sách và sau đó tạo danh sách hoàn toàn mới ném một vài thành phần của danh sách trung gian. Nếu bạn đã làm nó trong một swoop, sau đó bạn muốn được tốt hơn. Bạn có thể làm điều gì đó như:

list collect (case e if (e*2>10) => e*2) 

nhưng nếu tính toán e*2 thực sự đắt tiền? Sau đó, bạn có thể

(List[Int]() /: list)((ls,e) => { val x = e*2; if (x>10) x :: ls else ls } 

ngoại trừ việc điều này sẽ xuất hiện ngược. (Bạn có thể đảo ngược nó nếu cần thiết, nhưng điều đó đòi hỏi phải tạo ra một danh sách mới, mà lại không phải là một thuật toán lý tưởng.)

Tất nhiên, bạn có cùng một loại vấn đề về thuật toán trong Java nếu bạn đang sử dụng một cách đơn giản danh sách liên kết - danh sách mới của bạn sẽ kết thúc ngược, hoặc bạn phải tạo ra hai lần, trước tiên là ngược lại và sau đó chuyển tiếp hoặc bạn phải xây dựng nó với đệ quy (không đuôi) (dễ dàng trong Scala, nhưng không thể dùng được cho loại điều này trong cả hai ngôn ngữ kể từ khi bạn sẽ xả stack), hoặc bạn phải tạo một danh sách có thể thay đổi và sau đó giả vờ sau đó rằng nó không thể thay đổi được. (Trong đó, tình cờ, bạn cũng có thể làm ở Scala - xem mutable.LinkedList.)

Answer 2

Về cơ bản, nó duyệt qua danh sách hai lần. Một lần để nhân mỗi phần tử với hai. Và sau đó một thời gian khác để lọc kết quả.

Hãy nghĩ về vòng lặp một trong khi tạo ra một LinkedList với kết quả trung gian. Và sau đó một vòng lặp khác áp dụng bộ lọc để tạo ra kết quả cuối cùng.

này cần được nhanh hơn:

list.view.map(e => e * 2).filter(e => e > 10).force 

Answer 3

Rex Kerr trình bày chính xác vấn đề chính: Hoạt động trên danh sách bất biến, đoạn mã đã tạo tạo danh sách trung gian trong bộ nhớ. Lưu ý rằng điều này không nhất thiết phải chậm hơn mã Java tương đương; bạn chỉ không bao giờ sử dụng cấu trúc không thay đổi trong Java.

Wilfried Springer có một giải pháp tuyệt vời, Scala idomatic. Sử dụng view, không có bản sao (thao tác) nào trong toàn bộ danh sách được tạo.

Lưu ý rằng việc sử dụng chế độ xem có thể không phải lúc nào cũng lý tưởng. Ví dụ: nếu cuộc gọi đầu tiên của bạn là filter dự kiến ​​sẽ loại bỏ hầu hết danh sách, có thể đáng giá để tạo phiên bản ngắn hơn một cách rõ ràng và chỉ sử dụng view sau đó để cải thiện vị trí bộ nhớ cho các lần lặp lại sau.

Answer 4

Phương pháp tiếp cận Scala trừu tượng hơn nhiều và chung chung hơn.Do đó rất khó để tối ưu hóa mọi trường hợp.

Tôi có thể tưởng tượng rằng trình biên dịch HotSpot JIT có thể áp dụng kết hợp luồng và vòng lặp cho mã trong tương lai nếu thấy kết quả ngay lập tức không được sử dụng.

Ngoài ra mã Java còn hoạt động nhiều hơn nữa.

Nếu bạn thực sự chỉ muốn thay đổi cấu trúc dữ liệu, hãy xem xét transform. Có vẻ giống như map nhưng không tạo bộ sưu tập mới, e. G .:

val array = Array(1,2,3,4,5,6,7,8,9,10).transform(_ * 2) 
// array is now WrappedArray(2, 4, 6, 8, 10, 12, 14, 16, 18, 20) 

Tôi thực sự hy vọng thêm một số hoạt động tại chỗ sẽ được bổ sung ion tương lai ...

Answer 5

Để tránh vượt qua danh sách hai lần, tôi nghĩ rằng cú pháp for là một lựa chọn tốt đẹp ở đây:

val list2 = for(v <- list1; e = v * 2; if e > 10) yield e 

Answer 6

Giải pháp nằm chủ yếu với JVM. Mặc dù Scala có một cách giải quyết khác trong hình @specialization, làm tăng kích thước của bất kỳ lớp đặc biệt nào, và chỉ giải quyết được một nửa vấn đề - nửa còn lại là việc tạo ra các đối tượng tạm thời.

JVM thực sự làm tốt công việc tối ưu hóa rất nhiều, hoặc hiệu suất thậm chí còn khủng khiếp hơn, nhưng Java không yêu cầu tối ưu hóa mà Scala làm, do đó JVM không cung cấp chúng. Tôi hy vọng rằng để thay đổi ở một mức độ nào đó với việc giới thiệu SAM không thực sự đóng trong Java.

Nhưng, cuối cùng, nó đi xuống để cân bằng nhu cầu. Cùng một vòng lặp while mà Java và Scala làm nhanh hơn nhiều so với hàm tương đương của Scala có thể được thực hiện nhanh hơn nhưng trong C. Tuy nhiên, mặc dù những gì các microbenchmarks cho chúng ta biết, mọi người sử dụng Java.

Answer 7

list.filter (e => e * 2> 10) .map (e => e * 2)

nỗ lực này làm giảm đầu tiên trên danh sách. Vì vậy, vượt qua thứ hai là trên các yếu tố ít hơn.