tôi tò mò về những điều sau xây dựng trong Java 8:Phương thức DoubleStream.sum() của Java-8 có ổn định khi chạy song song không?
double[] doubles = //...
double sum = DoubleStream.of(doubles).parallel().sum();
Để cắt theo đuổi:
- sẽ giá trị của
sumluôn luôn giống nhau, ví dụ khi chạy trên các máy tính khác nhau?
More nền ...
Floating điểm số học là lossy và (không giống như số học giá trị thực) không phải là kết. Vì vậy, trừ khi chăm sóc được thực hiện trong cách công việc được chia và tập hợp lại, nó có thể dẫn đến kết quả không xác định.
Tôi rất vui khi khám phá ra rằng phương pháp sum() sử dụng Kahan Summation dưới mui xe. Điều này làm giảm đáng kể lỗi, nhưng vẫn không cho kết quả chính xác *.
Trong cuộc gọi lặp lại, các cuộc gọi lặp lại của tôi xuất hiện để trả về cùng một kết quả, nhưng tôi muốn biết mức độ ổn định mà chúng ta có thể giả định là an toàn. ví dụ:
- Ổn định trong mọi trường hợp?
- Ổn định trên các máy tính có cùng số lõi?
- Chỉ ổn định trên một máy tính nhất định?
- Không thể phụ thuộc vào nó ổn định?
Tôi rất vui khi giả định cùng một phiên bản JVM trên mỗi máy tính.
Dưới đây là một thử nghiệm tôi whipped lên:
public static void main(String[] args) {
Random random = new Random(42L);
for (int j = 1; j < 20; j++) {
// Stream increases in size and the magnitude of the values at each iteration.
double[] doubles = generate(random, j*100, j);
// Like a simple for loop
double sum1 = DoubleStream.of(doubles).reduce(0, Double::sum);
double sum2 = DoubleStream.of(doubles).sum();
double sum3 = DoubleStream.of(doubles).parallel().sum();
System.out.println(printStats(doubles, sum1, sum2, sum3));
// Is the parallel computation stable?
for (int i = 0; i < 1000; i++) {
double sum4 = DoubleStream.of(doubles).parallel().sum();
assert sum4 == sum3;
}
Arrays.sort(doubles);
}
}
/**
* @param spread When odd, returns a mix of +ve and -ve numbers.
* When even, returns only +ve numbers.
* Higher values cause a wider spread of magnitudes in the returned values.
* Must not be negative.
*/
private static double[] generate(Random random, int count, int spread) {
return random.doubles(count).map(x -> Math.pow(4*x-2, spread)).toArray();
}
private static String printStats(double[] doubles, double sum1, double sum2, double sum3) {
DoubleSummaryStatistics stats = DoubleStream.of(doubles).summaryStatistics();
return String.format("-----%nMin: %g, Max: %g, Average: %g%n"
+ "Serial difference: %g%n"
+ "Parallel difference: %g",
stats.getMin(), stats.getMax(), stats.getAverage(), sum2-sum1, sum3-sum1);
}
Khi tôi chạy này, vài lần lặp đầu tiên là:
-----
Min: -1.89188, Max: 1.90414, Average: 0.0541140
Serial difference: -2.66454e-15
Parallel difference: -2.66454e-15
-----
Min: 0.000113827, Max: 3.99513, Average: 1.17402
Serial difference: 1.70530e-13
Parallel difference: 1.42109e-13
-----
Min: -7.95673, Max: 7.87757, Average: 0.0658356
Serial difference: 0.00000
Parallel difference: -7.10543e-15
-----
Min: 2.53794e-09, Max: 15.8122, Average: 2.96504
Serial difference: -4.54747e-13
Parallel difference: -6.82121e-13
Chú ý rằng trong khi sum2 & sum3 có thể được giả định là chính xác hơn sum1 - chúng có thể không giống nhau!
Tôi gieo Random với 42, vì vậy nếu có ai nhận được kết quả khác với tôi, điều đó sẽ ngay lập tức chứng minh một số điều. :-)
*Đối với người hiếu ...
- Dưới đây là some (python) algorithms mà cho kết quả chính xác
- Thuật toán chính xác-sum hợp với đặc điểm hiệu suất tốt nhất nghe có vẻ tôi đã nghe nói là given here (yêu cầu đăng ký ACM hoặc phí). Phải mất 5 flops cho mỗi đầu vào, nhưng được viết (trong C) để khai thác song song cấp hướng dẫn và chỉ chạy chậm hơn 2-3 lần so với tổng kết ngây thơ, mà âm thanh khá tốt cho một kết quả chính xác. (c.f.Kahan tổng kết 4 flops mỗi đầu vào)
+1 cho câu hỏi thú vị, được viết bằng một trường hợp thử nghiệm được ném vào! (Rất ít câu hỏi như thế này trên SO ngày nay ...) –
Tôi mong rằng câu trả lời sẽ là "không, đừng mong đợi sự ổn định chút nào." –
Tôi nghĩ tài liệu về [DoubleStream :: sum] (http://docs.oracle.com/javase/8/docs/api/java/util/stream/DoubleStream.html#sum--) khá rõ ràng về điều này vấn đề: "Giá trị của tổng số dấu phẩy động là một hàm cả hai giá trị đầu vào cũng như thứ tự ** của các hoạt động bổ sung. Thứ tự của các hoạt động bổ sung của phương pháp này là ** cố ý không được xác định ** để cho phép để thực hiện tính linh hoạt để cải thiện tốc độ và độ chính xác của kết quả tính toán. " – nosid