Каков наилучший способ в Java для генерации последовательности значений List <Double>с указанием начала, конца и шага? - PullRequest
7 голосов
/ 22 декабря 2019

Я на самом деле очень удивлен, что не смог найти ответ на этот вопрос здесь, хотя, возможно, я просто использую неправильные условия поиска или что-то в этом роде. Самое близкое, что я мог найти, это this , но они спрашивают о генерации определенного диапазона double s с определенным размером шага, и ответы рассматривают его как таковой. Мне нужно что-то, что будет генерировать числа с произвольным размером начала, конца и шага.

Я полагаю, там имеет , чтобы где-то уже был какой-то метод подобный этому в библиотеке, но если так, то я не былне могу найти его легко (опять же, может быть, я просто использую неправильные условия поиска или что-то). Итак, вот что я приготовил самостоятельно за последние несколько минут, чтобы сделать это:

import java.lang.Math;
import java.util.List;
import java.util.ArrayList;

public class DoubleSequenceGenerator {


     /**
     * Generates a List of Double values beginning with `start` and ending with
     * the last step from `start` which includes the provided `end` value.
     **/
    public static List<Double> generateSequence(double start, double end, double step) {
        Double numValues = (end-start)/step + 1.0;
        List<Double> sequence = new ArrayList<Double>(numValues.intValue());

        sequence.add(start);
        for (int i=1; i < numValues; i++) {
          sequence.add(start + step*i);
        }

        return sequence;
    }

    /**
     * Generates a List of Double values beginning with `start` and ending with
     * the last step from `start` which includes the provided `end` value.
     * 
     * Each number in the sequence is rounded to the precision of the `step`
     * value. For instance, if step=0.025, values will round to the nearest
     * thousandth value (0.001).
     **/
    public static List<Double> generateSequenceRounded(double start, double end, double step) {

        if (step != Math.floor(step)) {
            Double numValues = (end-start)/step + 1.0;
            List<Double> sequence = new ArrayList<Double>(numValues.intValue());

            double fraction = step - Math.floor(step);
            double mult = 10;
            while (mult*fraction < 1.0) {
                mult *= 10;
            }

            sequence.add(start);
            for (int i=1; i < numValues; i++) {
              sequence.add(Math.round(mult*(start + step*i))/mult);
            }

            return sequence;
        }

        return generateSequence(start, end, step);
    }

}

Эти методы запускают простой цикл, умножая step на индекс последовательности и добавляя к start смещениеЭто уменьшает сложность ошибок с плавающей точкой, которые могут возникать при непрерывном увеличении (например, добавление step к переменной на каждой итерации).

Я добавил метод generateSequenceRounded для тех случаев, когда размер дробного шагаможет вызвать заметные ошибки с плавающей точкой. Это требует немного большей арифметики, поэтому в таких чрезвычайно чувствительных к производительности ситуациях, как наша, было бы неплохо иметь возможность использовать более простой метод, когда округление не требуется. Я подозреваю, что в большинстве случаев общего использования издержки округления будут незначительными.

Обратите внимание, что я намеренно исключил логику для обработки "ненормальных" аргументов, таких как Infinity, NaN, start> endили отрицательный размер step для простоты и желания сосредоточиться на рассматриваемом вопросе.

Вот пример использования и соответствующий результат:

System.out.println(DoubleSequenceGenerator.generateSequence(0.0, 2.0, 0.2))
System.out.println(DoubleSequenceGenerator.generateSequenceRounded(0.0, 2.0, 0.2));
System.out.println(DoubleSequenceGenerator.generateSequence(0.0, 102.0, 10.2));
System.out.println(DoubleSequenceGenerator.generateSequenceRounded(0.0, 102.0, 10.2));
[0.0, 0.2, 0.4, 0.6000000000000001, 0.8, 1.0, 1.2000000000000002, 1.4000000000000001, 1.6, 1.8, 2.0]
[0.0, 0.2, 0.4, 0.6, 0.8, 1.0, 1.2, 1.4, 1.6, 1.8, 2.0]
[0.0, 10.2, 20.4, 30.599999999999998, 40.8, 51.0, 61.199999999999996, 71.39999999999999, 81.6, 91.8, 102.0]
[0.0, 10.2, 20.4, 30.6, 40.8, 51.0, 61.2, 71.4, 81.6, 91.8, 102.0]

Существует ли существующийбиблиотека, которая уже предоставляет такую ​​функциональность?

Если нет, есть ли проблемы с моим подходом?

У кого-нибудь есть лучший подход к этому?

Ответы [ 4 ]

12 голосов
/ 31 декабря 2019

Последовательности можно легко генерировать с помощью Java 11 Stream API.

Простой подход заключается в использовании DoubleStream:

public static List<Double> generateSequenceDoubleStream(double start, double end, double step) {
  return DoubleStream.iterate(start, d -> d <= end, d -> d + step)
      .boxed()
      .collect(toList());
}

В диапазонах с большим числом итераций, double может накапливаться ошибка точности, что приводит к большей ошибке ближе к концу диапазона. Ошибка может быть минимизирована путем переключения на IntStream и использования целых чисел и одинарного двойного множителя:

public static List<Double> generateSequenceIntStream(int start, int end, int step, double multiplier) {
  return IntStream.iterate(start, i -> i <= end, i -> i + step)
      .mapToDouble(i -> i * multiplier)
      .boxed()
      .collect(toList());
}

Чтобы вообще избавиться от ошибки double, можно использовать BigDecimal:

public static List<Double> generateSequenceBigDecimal(BigDecimal start, BigDecimal end, BigDecimal step) {
  return Stream.iterate(start, d -> d.compareTo(end) <= 0, d -> d.add(step))
      .mapToDouble(BigDecimal::doubleValue)
      .boxed()
      .collect(toList());
}

Примеры:

public static void main(String[] args) {
  System.out.println(generateSequenceDoubleStream(0.0, 2.0, 0.2));
  //[0.0, 0.2, 0.4, 0.6000000000000001, 0.8, 1.0, 1.2, 1.4, 1.5999999999999999, 1.7999999999999998, 1.9999999999999998]

  System.out.println(generateSequenceIntStream(0, 20, 2, 0.1));
  //[0.0, 0.2, 0.4, 0.6000000000000001, 0.8, 1.0, 1.2000000000000002, 1.4000000000000001, 1.6, 1.8, 2.0]

  System.out.println(generateSequenceBigDecimal(new BigDecimal("0"), new BigDecimal("2"), new BigDecimal("0.2")));
  //[0.0, 0.2, 0.4, 0.6, 0.8, 1.0, 1.2, 1.4, 1.6, 1.8, 2.0]
}

Метод повторение с этой сигнатурой (3 параметра) было добавлено в Java 9. Итак, для Java 8 код выглядит как

DoubleStream.iterate(start, d -> d + step)
    .limit((int) (1 + (end - start) / step))
3 голосов
/ 23 декабря 2019

Лично я бы сократил класс DoubleSequenceGenerator для других полезностей и использовал бы только один генератор последовательностей метод, который содержит возможность использовать любойтребуемая точность требуется или вообще не используется:

В методе генератора ниже, если ничего (или любое значение меньше 0) не предоставлено для необязательного setPrecision В этом случае округление десятичной точности не выполняется. Если для значения точности задано 0 , то числа округляются до ближайшего целого числа (т. Е. 89,674 округляется до 90,0). Если задано конкретное значение точности больше 0 , то значения преобразуются в эту десятичную точность.

Здесь используется BigDecimal для ... ну .... точности:

import java.util.List;
import java.util.ArrayList;
import java.math.BigDecimal;
import java.math.RoundingMode;

public class DoubleSequenceGenerator {

     public static List<Double> generateSequence(double start, double end, 
                                          double step, int... setPrecision) {
        int precision = -1;
        if (setPrecision.length > 0) {
            precision = setPrecision[0];
        }
        List<Double> sequence = new ArrayList<>();
        for (double val = start; val < end; val+= step) {
            if (precision > -1) {
                sequence.add(BigDecimal.valueOf(val).setScale(precision, RoundingMode.HALF_UP).doubleValue());
            }
            else {
                sequence.add(BigDecimal.valueOf(val).doubleValue());
            }
        }
        if (sequence.get(sequence.size() - 1) < end) { 
            sequence.add(end); 
        }
        return sequence;
    }    

    // Other class goodies here ....
}

А в main ():

System.out.println(generateSequence(0.0, 2.0, 0.2));
System.out.println(generateSequence(0.0, 2.0, 0.2, 0));
System.out.println(generateSequence(0.0, 2.0, 0.2, 1));
System.out.println();
System.out.println(generateSequence(0.0, 102.0, 10.2, 0));
System.out.println(generateSequence(0.0, 102.0, 10.2, 0));
System.out.println(generateSequence(0.0, 102.0, 10.2, 1));

И на консоли отображается:

[0.0, 0.2, 0.4, 0.6000000000000001, 0.8, 1.0, 1.2, 1.4, 1.5999999999999999, 1.7999999999999998, 1.9999999999999998, 2.0]
[0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0, 1.0, 2.0, 2.0, 2.0]
[0.0, 0.2, 0.4, 0.6, 0.8, 1.0, 1.2, 1.4, 1.6, 1.8, 2.0]

[0.0, 10.2, 20.4, 30.599999999999998, 40.8, 51.0, 61.2, 71.4, 81.60000000000001, 91.80000000000001, 102.0]
[0.0, 10.0, 20.0, 31.0, 41.0, 51.0, 61.0, 71.0, 82.0, 92.0, 102.0]
[0.0, 10.2, 20.4, 30.6, 40.8, 51.0, 61.2, 71.4, 81.6, 91.8, 102.0]
2 голосов
/ 02 января 2020

Попробуйте это.

public static List<Double> generateSequenceRounded(double start, double end, double step) {
    long mult = (long) Math.pow(10, BigDecimal.valueOf(step).scale());
    return DoubleStream.iterate(start, d -> (double) Math.round(mult * (d + step)) / mult)
                .limit((long) (1 + (end - start) / step)).boxed().collect(Collectors.toList());
}

Здесь,

int java.math.BigDecimal.scale()

Возвращает масштаб этого BigDecimal. Если ноль или положительный, шкала - это число цифр справа от десятичной точки. Если значение отрицательное, немасштабированное значение числа умножается на десять до степени отрицания шкалы. Например, шкала -3 означает, что немасштабированное значение умножается на 1000.

В main ()

System.out.println(generateSequenceRounded(0.0, 102.0, 10.2));
System.out.println(generateSequenceRounded(0.0, 102.0, 10.24367));

И Вывод:

[0.0, 10.2, 20.4, 30.6, 40.8, 51.0, 61.2, 71.4, 81.6, 91.8, 102.0]
[0.0, 10.24367, 20.48734, 30.73101, 40.97468, 51.21835, 61.46202, 71.70569, 81.94936, 92.19303]
1 голос
/ 05 января 2020
  1. Существует ли существующая библиотека, которая уже обеспечивает такую ​​функциональность?

    Извините, я не знаю, но, судя по другим ответам и ихОтносительная простота - нет, нет. Не нужно. Ну, почти ...

  2. Если нет, есть ли проблемы с моим подходом?

    Да и нет. У вас есть по крайней мере одна ошибка и немного места для повышения производительности, но сам подход верен.

    1. Ваша ошибка: ошибка округления (просто измените while (mult*fraction < 1.0) на while (mult*fraction < 10.0), и это должно исправить ее. )
    2. Все остальные не достигают end ... ну, может быть, они просто недостаточно внимательны, чтобы читать комментарии в вашем коде
    3. Все остальные работают медленнее.
    4. Простое изменение условия в главном цикле с int < Double на int < int заметно увеличит скорость вашего кода
  3. У кого-нибудь лучшеподход к этому?

    Хм ... Каким образом?

    1. Простота? generateSequenceDoubleStream из @Evgeniy Khyst выглядит довольно просто. И следует использовать ... но, возможно, нет, из-за следующих двух пунктов
    2. Точно? generateSequenceDoubleStream нет! Но все же можно сохранить с рисунком start + step*i. И start + step*i шаблон является точным. Только BigDouble и арифметика с фиксированной точкой могут превзойти его. Но BigDouble s медленные, а ручная арифметика с фиксированной точкой утомительна и может не подходить для ваших данных. Кстати, в вопросах точности вы можете развлекаться с этим: https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html
    3. Скорость ... ну, теперь мы находимся в шатком положении. Проверьте этот repl https://repl.it/repls/RespectfulSufficientWorker У меня сейчас нет приличного тестового стенда, поэтому я использовал repl.it ..., который совершенно не подходит для тестирования производительности, но это не главное. Дело в том, что нет однозначного ответа. За исключением того, что, возможно, в вашем случае, что не совсем понятно из вашего вопроса, вам определенно не следует использовать BigDecimal (читайте дальше).

      Я пытался играть и оптимизировать для больших входов. А ваш оригинальный код с некоторыми незначительными изменениями - самый быстрый. Но, может быть, вам нужно огромное количество маленьких List с? Тогда это может быть совсем другая история.

      Этот код довольно простой на мой вкус и достаточно быстрый:

        public static List<Double> genNoRoundDirectToDouble(double start, double end, double step) {
        int len = (int)Math.ceil((end-start)/step) + 1;
        var sequence = new ArrayList<Double>(len);
        sequence.add(start);
        for (int i=1 ; i < len ; ++i) sequence.add(start + step*i);
        return sequence;
        }
    

    Если вы предпочитаете более элегантный способ(или мы должны назвать это идиоматическим), я лично предложил бы:

    public static List<Double> gen_DoubleStream_presice(double start, double end, double step) {
        return IntStream.range(0, (int)Math.ceil((end-start)/step) + 1)
            .mapToDouble(i -> start + i * step)
            .boxed()
            .collect(Collectors.toList());
    }
    

    В любом случае, возможное повышение производительности:

    1. Попробуйте переключиться с Double на double и если они вам действительно нужны, вы можете переключиться обратно, судя по тестам, все равно может быть быстрее. (Но не верьте моему, попробуйте сами с вашими данными в вашей среде. Как я уже сказал - repl.it - ​​отстой для тестов)
    2. Немного волшебства: отдельный цикл для Math.round() .. Возможно, это как-то связано с локальностью данных. Я не рекомендую это - результат очень нестабилен. Но это весело.

      double[] sequence = new double[len];
      for (int i=1; i < len; ++i) sequence[i] = start + step*i;
      List<Double> list = new ArrayList<Double>(len);
      list.add(start);
      for (int i=1; i < len; ++i) list.add(Math.round(sequence[i])/mult);
      return list;
      
    3. Вы должны определенно считать себя более ленивым и генерировать числа по требованию без сохранения, чем в List s

  4. Я подозреваю, что в большинстве случаев общего использования издержки округления будут незначительными.

    Если вы что-то подозреваете - проверьте это :-) Мой ответ "Да", но опять же ... не верьте мне. Проверьте это.

Итак, вернемся к основному вопросу: есть ли лучший способ?
Да, конечно!
Но это зависит.

  1. Выберите Большой Десятичный, если вам нужны очень большие числа и очень маленькие числа. Но если вы приведете их к Double, и более того, используйте его с числами «близкой» величины - в них нет необходимости! Извлеките тот же ответ: https://repl.it/repls/RespectfulSufficientWorker - последний тест показывает, что не будет никакой разницы в результатах , но потеря скорости раскопок.
  2. Сделайте некоторые микрооптимизации на основеВаши свойства данных, ваша задача и ваша среда.
  3. Предпочитайте короткий и простой код, если выигрыш в повышении производительности на 5-10% невелик. Не трать свое время
  4. Возможно, используйте арифметику с фиксированной точкой, если можете, и если она того стоит.

Кроме этого, у вас все хорошо.

PS . В реплик также есть реализация формулы суммирования Кахана ... просто для удовольствия. https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html#1346 и это работает - вы можете смягчить ошибки суммирования

...