Мне интересна следующая конструкция в Java 8:
double[] doubles = //...
double sum = DoubleStream.of(doubles).parallel().sum();
Чтобы прервать погоню:
- Значение
sumвсегда будет одинаковым, например. при запуске на разных компьютерах?
Подробнее...
Арифметика с плавающей точкой - это потеря и (в отличие от действительной арифметики) не ассоциативна. Поэтому, если не будет предпринята осторожность в том, как работа будет разделена и собрана, это может привести к неопределенным результатам.
Я был рад узнать, что метод sum() использует Kahan Summation под капотом. Это значительно уменьшает погрешность, но все равно не дает точных результатов *.
В моем тестировании повторяющиеся вызовы кажутся возвращать одинаковый результат каждый раз, но я хотел бы знать, насколько стабильно мы можем с уверенностью предположить, что это так. например:.
- Стабилен при любых обстоятельствах?
- Стабильно на компьютерах с одинаковым количеством ядер?
- Стабилен только на данном компьютере?
- Не может ли он быть стабильным вообще?
Я рад принять ту же версию JVM на каждом компьютере.
Здесь тест я взбивал:
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);
}
Когда я запускаю это, первые несколько итераций:
-----
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
Обратите внимание, что хотя sum2 и sum3 можно считать более точными, чем sum1 - они могут быть не такими же, как друг друга!
Я посеял Random с 42, так что если кто-то получит другой результат для меня, это немедленно докажет что-то.: -)
* Для любопытных...
- Вот некоторые (python) алгоритмы, которые дают точные результаты
- Алгоритм точной суммы с наилучшими характеристиками производительности, о которых я слышал, представлен здесь (требуется подписка ACM или плата). Он берет 5 флопов на каждый вход, но записывается (в C) для использования на уровне инструкций parallelism и работает только в 2 - 3 раза медленнее наивного суммирования, что звучит довольно хорошо для точного результата. (т.е. суммирование Кахана на 4 флопа на вход)
