Najlepszy sposób na wygenerowanie sekwencji Lista <Double> wartości dla początku, końca i kroku?


14

Jestem naprawdę zaskoczony, że nie mogłem znaleźć odpowiedzi na to pytanie, chociaż może po prostu używam niewłaściwych wyszukiwanych haseł lub czegoś takiego. Najbliżej udało mi się znaleźć jest to , ale proszą o generowanie szeregu specyficzną doubleS o rozmiarze określonego etapu, a odpowiedzi traktować go jako taki. Potrzebuję czegoś, co wygeneruje liczby o dowolnym rozmiarze początku, końca i kroku.

Wydaje mi się, że musi być gdzieś taka metoda w bibliotece, ale jeśli tak, to nie mogłem jej łatwo znaleźć (ponownie, może po prostu używam złych wyszukiwanych haseł lub czegoś takiego). Oto, co sam przygotowałem w ciągu ostatnich kilku minut, aby to zrobić:

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);
    }

}

Te metody uruchamiają prostą pętlę, mnożąc wartość stepindeksu sekwencji i dodając do startprzesunięcia. Ogranicza to łączenie błędów zmiennoprzecinkowych, które występowałyby przy ciągłej inkrementacji (np. Dodawanie stepzmiennej do każdej iteracji).

Dodałem generateSequenceRoundedmetodę dla tych przypadków, w których ułamek wielkości kroku może powodować zauważalne błędy zmiennoprzecinkowe. Wymaga to nieco więcej arytmetyki, więc w sytuacjach szczególnie wrażliwych na wydajność, takich jak nasza, miło jest mieć możliwość użycia prostszej metody, gdy zaokrąglanie nie jest konieczne. Podejrzewam, że w większości ogólnych przypadków użycia zaokrąglenie narzutu byłoby nieznaczne.

Zauważ, że celowo wyłączone logiki do obsługi „nienormalne” argumenty takie jak Infinity, NaN, start> endlub ujemną stepwielkość dla prostoty i pragną skoncentrować się na kwestii pod ręką.

Oto kilka przykładów użycia i odpowiadających danych wyjściowych:

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]

Czy istnieje już biblioteka, która już zapewnia taką funkcjonalność?

Jeśli nie, czy są jakieś problemy z moim podejściem?

Czy ktoś ma lepsze podejście do tego?

Odpowiedzi:


17

Sekwencje można łatwo generować za pomocą interfejsu API Java 11 Stream.

Bezpośrednim podejściem jest użycie 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());
}

W zakresach z dużą liczbą iteracji doublebłąd precyzji może się kumulować, powodując większy błąd bliżej końca zakresu. Błąd można zminimalizować, przechodząc do IntStreamliczb całkowitych i pojedynczego podwójnego mnożnika i używając go:

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());
}

Aby doublew ogóle pozbyć się błędu precyzji, BigDecimalmożna użyć:

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());
}

Przykłady:

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]
}

Metoda iteracji z tym podpisem (3 parametry) została dodana w Javie 9. Tak więc, dla Java 8 wygląda kod

DoubleStream.iterate(start, d -> d + step)
    .limit((int) (1 + (end - start) / step))

To jest lepsze podejście.
Vishwa Ratna

Widzę kilka błędów kompilacji (JDK 1.8.0) error: method iterate in interface DoubleStream cannot be applied to given types; return DoubleStream.iterate(start, d -> d <= end, d -> d + step) required: double,DoubleUnaryOperator. found: double,(d)->d <= end,(d)->d + step. reason: actual and formal argument lists differ in length. Podobne błędy dla IntStream.iteratei Stream.iterate. Również non-static method doubleValue() cannot be referenced from a static context.
NanoWizard,

1
Odpowiedź zawiera kod Java 11
Evgeniy Khyst

@NanoWizard rozszerzył odpowiedź o próbkę dla Java 8
Evgeniy Khyst,

Trójargumentowy iterator został dodany w Javie 9
Thorbjørn Ravn Andersen

3

Ja osobiście skróciłbym nieco klasę DoubleSequenceGenerator dla innych gadżetów i używałbym tylko jednej metody generatora sekwencji , która zawiera opcję wykorzystania dowolnej pożądanej precyzji lub wcale nie precyzji:

W poniższej metodzie generatora, jeśli do opcjonalnego parametru setPrecision nie zostanie dostarczone nic (lub jakakolwiek wartość mniejsza niż 0), wówczas nie jest wykonywane zaokrąglanie z dokładnością dziesiętną. Jeśli podano wartość 0 dla wartości dokładności, liczby są zaokrąglane do najbliższej liczby całkowitej (tj. 89,674 jest zaokrąglane do 90,0). Jeśli podana jest konkretna wartość dokładności większa niż 0, wówczas wartości są konwertowane na tę dokładność dziesiętną.

BigDecimal jest tutaj używany do ... no cóż ... precyzji:

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 ....
}

I w 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));

A konsola wyświetla:

[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]

Ciekawe pomysły, choć widzę kilka problemów. 1. Dodając do valkażdej iteracji, otrzymujesz addytywną utratę precyzji. W przypadku bardzo dużych sekwencji błąd ostatnich kilku cyfr może być znaczący. 2. Powtarzające się połączenia BigDecimal.valueOf()są stosunkowo drogie. Uzyskasz lepszą wydajność (i precyzję) poprzez konwersję danych wejściowych na BigDecimals i użycie BigDecimaldla val. W rzeczywistości, używając doublefor val, tak naprawdę nie zyskujesz na precyzji, z BigDecimalwyjątkiem zaokrąglania.
NanoWizard,

2

Spróbuj tego.

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());
}

Tutaj,

int java.math.BigDecimal.scale()

Zwraca skalę tego BigDecimal. Jeśli zero lub dodatnia, skala jest liczbą cyfr po prawej stronie przecinka dziesiętnego. Jeśli ujemna, nieskalowana wartość liczby jest mnożona przez dziesięć do potęgi negacji skali. Na przykład skala -3 oznacza, że ​​nieskalowana wartość jest mnożona przez 1000.

W main ()

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

I wyjście:

[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]

2
  1. Czy istnieje już biblioteka, która już zapewnia taką funkcjonalność?

    Przepraszam, nie wiem, ale sądząc po innych odpowiedziach i ich względnej prostocie - nie, nie ma. Nie ma potrzeby. Cóż prawie...

  2. Jeśli nie, czy są jakieś problemy z moim podejściem?

    Tak i nie. Masz co najmniej jeden błąd i trochę miejsca na zwiększenie wydajności, ale samo podejście jest prawidłowe.

    1. Twój błąd: błąd zaokrąglania (wystarczy zmienić while (mult*fraction < 1.0)na while (mult*fraction < 10.0)i powinien to naprawić)
    2. Wszystkie pozostałe nie docierają do end... cóż, może po prostu nie były wystarczająco spostrzegawcze, aby przeczytać komentarze w twoim kodzie
    3. Wszystkie pozostałe są wolniejsze.
    4. Po prostu zmiana stanu w głównej pętli z int < Doublena int < intzauważalnie zwiększy szybkość twojego kodu
  3. Czy ktoś ma lepsze podejście do tego?

    Hmm ... W jaki sposób?

    1. Prostota? generateSequenceDoubleStream@Evgeniy Khyst wygląda dość prosto. I powinien być użyty ... ale może nie, z powodu kolejnych dwóch punktów
    2. Precyzyjny? generateSequenceDoubleStreamnie jest! Ale nadal można go zapisać za pomocą wzoru start + step*i. A start + step*iwzór jest precyzyjny. Tylko BigDoublearytmetyka stałoprzecinkowa może ją pokonać. Ale BigDoublesą powolne, a ręczna arytmetyka stałoprzecinkowa jest uciążliwa i może być nieodpowiednia dla twoich danych. Nawiasem mówiąc, w kwestiach dotyczących precyzji możesz się bawić: https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html
    3. Szybkość ... cóż, teraz jesteśmy na niepewnym gruncie. Sprawdź tę replikę https://repl.it/repls/RespectfulSufficientWorker Nie mam teraz przyzwoitego stanowiska testowego, więc użyłem repl.it ... co jest całkowicie nieodpowiednie do testowania wydajności, ale nie jest to najważniejsze. Chodzi o to - nie ma jednoznacznej odpowiedzi. Tyle że w twoim przypadku, co nie jest całkowicie jasne z twojego pytania, zdecydowanie nie powinieneś używać BigDecimal (czytaj dalej).

      Próbowałem grać i optymalizować pod kątem dużych nakładów. I twój oryginalny kod, z pewnymi drobnymi zmianami - najszybszy. Ale może potrzebujesz ogromnych ilości małych Lists? To może być zupełnie inna historia.

      Ten kod jest dość prosty i dość szybki:

        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;
        }

    Jeśli wolisz bardziej elegancki sposób (lub powinniśmy to nazwać idiomatycznym), osobiście sugerowałbym:

    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());
    }

    W każdym razie możliwe zwiększenie wydajności to:

    1. Spróbuj przełączyć się z Doublena double, a jeśli naprawdę ich potrzebujesz, możesz przełączyć się ponownie, sądząc po testach, wciąż może być szybszy. (Ale nie ufaj mojemu, spróbuj sam z danymi w swoim środowisku. Jak powiedziałem - repl.it jest do bani dla testów porównawczych)
    2. Trochę magii: osobna pętla dla Math.round()... może ma to coś wspólnego z lokalizacją danych. Nie polecam tego - wynik jest bardzo niestabilny. Ale jest fajnie.

      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. Zdecydowanie powinieneś uważać się za bardziej leniwego i generować liczby na żądanie bez przechowywania ich w Lists

  4. Podejrzewam, że w większości ogólnych przypadków użycia zaokrąglenie narzutu byłoby nieznaczne.

    Jeśli coś podejrzewasz - przetestuj :-) Moja odpowiedź brzmi „Tak”, ale znowu… nie wierz mi. Sprawdź to.

Wróćmy więc do głównego pytania: czy istnieje lepszy sposób?
Tak oczywiście!
Ale to zależy.

  1. Wybierz Big Decimal, jeśli potrzebujesz bardzo dużych liczb i bardzo małych liczb. Ale jeśli rzucisz je z powrotem na Double, i co więcej, użyj go z liczbą „bliskich” wielkości - nie ma takiej potrzeby! Kasa tego samego replika: https://repl.it/repls/RespectfulSufficientWorker - ostatni test pokazuje, że nie będzie żadnej różnicy w wynikach , ale utrata prędkości kopania.
  2. Dokonaj mikrooptymalizacji na podstawie właściwości danych, zadania i środowiska.
  3. Preferuj krótki i prosty kod, jeśli nie ma wiele do zyskania dzięki zwiększeniu wydajności o 5-10%. Nie trać czasu
  4. Może możesz użyć arytmetyki punktu stałego, jeśli możesz i jeśli warto.

Poza tym wszystko w porządku.

PS . W replice jest także implementacja formuły sumowania Kahan ... dla zabawy. https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html#1346 i działa - można złagodzić błędy sumowania

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.