Cách nhanh nhất để tổng hợp một bộ sưu tập trong Scala

Question

Tôi đã thử các bộ sưu tập khác nhau trong Scala để tổng hợp các phần tử của nó là gì và chúng chậm hơn nhiều so với tổng Java (mảng for). Có cách nào để Scala nhanh như các mảng Java không?

Tôi đã nghe nói rằng trong scala 2,8 mảng sẽ giống như trong java, nhưng họ chậm hơn trong thực tế

Answer 1

Lập chỉ mục thành các mảng trong một vòng lặp while nhanh như trong Scala như trong Java. (Scala của "cho" vòng lặp không phải là xây dựng ở mức độ thấp rằng Java là, do đó sẽ không làm việc theo cách bạn muốn.)

Vì vậy, nếu trong Java mà bạn nhìn thấy

for (int i=0 ; i < array.length ; i++) sum += array(i) 

trong Scala bạn nên viết

var i=0 
while (i < array.length) { 
    sum += array(i) 
    i += 1 
} 

và nếu bạn làm điểm chuẩn của mình một cách thích hợp, bạn sẽ thấy không có sự khác biệt về tốc độ.

Nếu bạn có trình lặp nào, thì Scala nhanh bằng Java trong hầu hết mọi thứ. Ví dụ, nếu bạn có một ArrayList của đôi và trong Java bạn thêm chúng vào sử dụng

for (double d : arraylist) { sum += d } 

sau đó trong Scala bạn sẽ có xấp xỉ càng nhanh - nếu sử dụng một cấu trúc dữ liệu tương đương như ArrayBuffer - với

arraybuffer.foreach(sum += _) 

và không quá xa nhãn hiệu với một trong hai

sum = (0 /: arraybuffer)(_ + _) 
sum = arraybuffer.sum // 2.8 only 

Hãy ghi nhớ, tuy nhiên, rằng có một hình phạt để trộn các cấu trúc cấp cao và cấp thấp. Ví dụ, nếu bạn quyết định bắt đầu với một mảng nhưng sau đó sử dụng "foreach" trên nó thay vì chỉ mục vào nó, Scala phải bọc nó trong một bộ sưu tập (ArrayOps trong 2.8) để làm cho nó hoạt động, và thường sẽ phải các nguyên thủy là tốt.

Dù sao, để thử nghiệm benchmark, hai chức năng là bạn bè:

def time[F](f: => F) = { 
    val t0 = System.nanoTime 
    val ans = f 
    printf("Elapsed: %.3f\n",1e-9*(System.nanoTime-t0)) 
    ans 
} 

def lots[F](n: Int, f: => F): F = if (n <= 1) f else { f; lots(n-1,f) } 

Ví dụ:

val a = Array.tabulate(1000000)(_.toDouble) 
val ab = new collection.mutable.ArrayBuffer[Double] ++ a 
def adSum(ad: Array[Double]) = { 
    var sum = 0.0 
    var i = 0 
    while (i<ad.length) { sum += ad(i); i += 1 } 
    sum 
} 

// Mixed array + high-level; convenient, not so fast 
scala> lots(3, time(lots(100,(0.0 /: a)(_ + _)))) 
Elapsed: 2.434 
Elapsed: 2.085 
Elapsed: 2.081 
res4: Double = 4.999995E11 

// High-level container and operations, somewhat better 
scala> lots(3, time(lots(100,(0.0 /: ab)(_ + _))))  
Elapsed: 1.694 
Elapsed: 1.679 
Elapsed: 1.635 
res5: Double = 4.999995E11 

// High-level collection with simpler operation 
scala> lots(3, time(lots(100,{var s=0.0;ab.foreach(s += _);s}))) 
Elapsed: 1.171 
Elapsed: 1.166 
Elapsed: 1.162 
res7: Double = 4.999995E11 

// All low level operations with primitives, no boxing, fast! 
scala> lots(3, time(lots(100,adSum(a))))    
Elapsed: 0.185 
Elapsed: 0.183 
Elapsed: 0.186 
res6: Double = 4.999995E11 

Answer 2

Scala 2,8 Arraylà mảng JVM/Java và như vậy có đặc tính hiệu suất giống hệt nhau. Nhưng điều đó có nghĩa là họ không thể trực tiếp có thêm phương pháp hợp nhất chúng với phần còn lại của bộ sưu tập Scala. Để cung cấp ảo tưởng rằng các mảng có các phương thức này, có các chuyển đổi tiềm ẩn cho các lớp bao bọc thêm các khả năng đó. Nếu bạn không cẩn thận, bạn sẽ phải chịu chi phí quá cao bằng cách sử dụng các tính năng đó.

Trong những trường hợp lặp overhead là rất quan trọng, bạn rõ ràng có thể nhận được một iterator (hoặc duy trì một chỉ số nguyên, cho các cấu trúc tuần tự được lập chỉ mục như Array hoặc IndexedSeq khác) và sử dụng một vòng lặp while, mà là một cấu trúc ngôn ngữ cấp mà không cần hoạt động trên các hàm (chữ hoặc cách khác) nhưng có thể biên dịch các khối mã trong dòng.

val l1 = List(...) // or any Iteralbe 
val i1 = l1.iterator 
while (i1.hasNext) { 
    val e = i1.next 
    // Do stuff with e 
} 

Mã như vậy sẽ thực thi cơ bản nhanh như đối tác Java.

Answer 3

Rất khó để giải thích tại sao một số mã bạn đã không được hiển thị thực hiện tồi tệ so với một số mã khác mà bạn chưa hiển thị trong một số điểm chuẩn mà bạn chưa hiển thị.

Bạn có thể quan tâm đến this question và câu trả lời được chấp nhận của nó, cho một điều. Nhưng điểm chuẩn mã JVM là khó, vì JIT sẽ tối ưu hóa mã theo những cách khó dự đoán (đó là lý do tại sao JIT đánh bại tối ưu hóa truyền thống tại thời gian biên dịch).

Answer 4

Các scala thích hợp hoặc chức năng đã làm điều này sẽ là:

val numbers = Array(1, 2, 3, 4, 5) 
val sum = numbers.reduceLeft[Int](_+_) 

Kiểm tra liên kết này để giải thích đầy đủ các cú pháp: http://www.codecommit.com/blog/scala/quick-explanation-of-scalas-syntax

tôi nghi ngờ điều này sẽ nhanh hơn so với làm việc đó theo những cách được mô tả trong các câu trả lời khác nhưng tôi chưa thử nghiệm nên tôi không chắc chắn. Theo tôi đây là cách thích hợp để làm điều đó mặc dù kể từ khi Scala là một ngôn ngữ chức năng.

Answer 5

Bây giờ bạn có thể chỉ cần sử dụng tổng.

val values = Array.fill[Double](numValues)(0) 

val sumOfValues = values.sum 

Answer 6

Thời gian không phải là mối quan tâm duy nhất. Với sum bạn có thể thấy một vấn đề tràn:

scala> Array(2147483647,2147483647).sum 
res0: Int = -2 

trong trường hợp này gieo hạt foldLeft với một Long là một lợi thế

scala> Array(2147483647,2147483647).foldLeft(0L)(_+_) 
res1: Long = 4294967294