Der beste Weg, um eine List <Double> -Sequenz von Werten zu generieren, wenn Start, Ende und Schritt angegeben sind?

14

Ich bin eigentlich sehr überrascht, dass ich hier keine Antwort darauf finden konnte, obwohl ich vielleicht nur die falschen Suchbegriffe verwende oder so. Closest ich finden konnte , ist dies , aber sie fragen über einen bestimmten Bereich der Erzeugung von doubles mit einem bestimmten Schrittgröße, und die Antworten behandeln sie als solche. Ich brauche etwas, das die Zahlen mit beliebiger Start-, End- und Schrittgröße generiert.

Ich denke, irgendwo in einer Bibliothek muss es schon eine solche Methode geben, aber wenn ja, konnte ich sie nicht leicht finden (wieder verwende ich vielleicht nur die falschen Suchbegriffe oder so). Folgendes habe ich mir in den letzten Minuten selbst ausgedacht:

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

}

Diese Methoden führen eine einfache Schleife aus, die das stepmit dem Sequenzindex multipliziert und zum startOffset addiert . Dies verringert das Zusammensetzen von Gleitkommafehlern, die bei kontinuierlicher Inkrementierung auftreten würden (z. B. Hinzufügen der stepVariablen zu einer Variablen bei jeder Iteration).

Ich habe die generateSequenceRoundedMethode für Fälle hinzugefügt , in denen eine gebrochene Schrittgröße zu merklichen Gleitkommafehlern führen kann. Es erfordert etwas mehr Arithmetik, daher ist es in extrem leistungsempfindlichen Situationen wie unserer schön, die Option zu haben, die einfachere Methode zu verwenden, wenn die Rundung nicht erforderlich ist. Ich vermute, dass in den meisten allgemeinen Anwendungsfällen der Rundungsaufwand vernachlässigbar wäre.

Beachten Sie, dass ich ausgeschlossen Logik absichtlich für „abnormal“ Argumente wie Handhabung Infinity, NaN, start> end, oder eine negative stepGröße für Einfachheit und begehrt auf der Frage auf der Hand zu konzentrieren.

Hier einige Beispiele für die Verwendung und die entsprechende Ausgabe:

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]

Gibt es bereits eine Bibliothek, die diese Art von Funktionalität bietet?

Wenn nicht, gibt es Probleme mit meinem Ansatz?

Hat jemand einen besseren Ansatz dafür?

NanoWizard
quelle

Antworten:

17

Sequenzen können einfach mit der Java 11 Stream API generiert werden.

Der einfache Ansatz besteht darin, Folgendes zu verwenden 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());
}

In Bereichen mit einer großen Anzahl von Iterationen kann sich ein doublePräzisionsfehler ansammeln, der zu einem größeren Fehler näher am Ende des Bereichs führt. Der Fehler kann durch Umschalten auf IntStreamund Verwenden von Ganzzahlen und einfachem Doppelmultiplikator minimiert werden :

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

Um einen doublePräzisionsfehler überhaupt zu beseitigen, BigDecimalkann Folgendes verwendet werden:

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

Beispiele:

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

Die mit dieser Signatur iterierte Methode (3 Parameter) wurde in Java 9 hinzugefügt. Für Java 8 sieht der Code also so aus

DoubleStream.iterate(start, d -> d + step)
    .limit((int) (1 + (end - start) / step))
Evgeniy Khyst
quelle
Dies ist ein besserer Ansatz.
Vishwa Ratna
Ich sehe mehrere Kompilierungsfehler (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. Ähnliche Fehler für IntStream.iterateund Stream.iterate. Auch non-static method doubleValue() cannot be referenced from a static context.
NanoWizard
1
Antwort enthält Java 11 Code
Evgeniy Khyst
@NanoWizard erweiterte die Antwort mit einem Beispiel für Java 8
Evgeniy Khyst
Der Iterator mit drei Argumenten wurde in Java 9
Thorbjørn Ravn Andersen
3

Ich persönlich würde ich die verkürzen DoubleSequenceGenerator Klasse bis etwas für andere Leckereien und verwenden nur eine Sequenzgenerator Methode, die die Option enthält zu verwenden , was auch immer gewünschte Präzision wollten oder keine Präzision überhaupt nutzen:

Wenn in der folgenden Generatormethode dem optionalen Parameter setPrecision nichts (oder ein Wert kleiner als 0) zugeführt wird, wird keine Rundung mit Dezimalgenauigkeit durchgeführt. Wenn für einen Genauigkeitswert 0 angegeben wird, werden die Zahlen auf die nächste ganze Zahl gerundet (dh: 89.674 wird auf 90,0 gerundet). Wenn ein bestimmter Genauigkeitswert größer als 0 angegeben wird, werden die Werte in diese Dezimalgenauigkeit konvertiert.

BigDecimal wird hier verwendet für ... na ja ... Präzision:

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

Und in 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));

Und die Konsole zeigt an:

[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]
DevilsHnd
quelle
Interessante Ideen, obwohl ich einige Probleme sehe. 1. Durch Hinzufügen zu valjeder Iteration erhalten Sie einen additiven Präzisionsverlust. Bei sehr großen Sequenzen kann der Fehler bei den letzten Zahlen erheblich sein. 2. Wiederholte Anrufe BigDecimal.valueOf()sind relativ teuer. Sie erhalten eine bessere Leistung (und Präzision), wenn Sie die Eingaben in BigDecimals konvertieren und BigDecimalfor verwenden val. Wenn Sie ein doublefor verwenden val, erhalten Sie keinen Präzisionsvorteil, BigDecimalaußer vielleicht bei der Rundung.
NanoWizard
2

Versuche dies.

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

Hier,

int java.math.BigDecimal.scale()

Gibt die Skalierung dieses BigDecimal zurück. Bei Null oder positiv ist die Skala die Anzahl der Stellen rechts vom Dezimalpunkt. Wenn negativ, wird der nicht skalierte Wert der Zahl mit zehn multipliziert mit der Potenz der Negation der Skala multipliziert. Zum Beispiel bedeutet eine Skala von -3, dass der nicht skalierte Wert mit 1000 multipliziert wird.

In main ()

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

Und Ausgabe:

[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]
Maddy
quelle
2
  1. Gibt es bereits eine Bibliothek, die diese Art von Funktionalität bietet?

    Entschuldigung, ich weiß es nicht, aber nach anderen Antworten und ihrer relativen Einfachheit zu urteilen - nein, das gibt es nicht. Das ist nicht nötig. Naja fast...

  2. Wenn nicht, gibt es Probleme mit meinem Ansatz?

    Ja und nein. Sie haben mindestens einen Fehler und etwas Raum für Leistungssteigerungen, aber der Ansatz selbst ist korrekt.

    1. Ihr Fehler: Rundungsfehler (wechseln Sie einfach while (mult*fraction < 1.0)zu while (mult*fraction < 10.0)und das sollte ihn beheben)
    2. Alle anderen erreichen das nicht end... nun, vielleicht waren sie einfach nicht aufmerksam genug, um Kommentare in Ihrem Code zu lesen
    3. Alle anderen sind langsamer.
    4. Wenn Sie nur den Zustand in der Hauptschleife von int < Doubleauf ändern , int < intwird die Geschwindigkeit Ihres Codes spürbar erhöht
  3. Hat jemand einen besseren Ansatz dafür?

    Hmm ... auf welche Weise?

    1. Einfachheit? generateSequenceDoubleStreamvon @Evgeniy Khyst sieht ganz einfach aus. Und sollte verwendet werden ... aber vielleicht nein, wegen der nächsten zwei Punkte
    2. Präzise? generateSequenceDoubleStreamist nicht! Kann aber trotzdem mit dem Muster gespeichert werden start + step*i. Und das start + step*iMuster ist präzise. Nur eine BigDoubleFestkomma-Arithmetik kann es schlagen. Aber BigDoubles sind langsam und manuelle Festkomma-Arithmetik ist langwierig und möglicherweise für Ihre Daten ungeeignet. In Sachen Präzision können Sie sich übrigens damit unterhalten: https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html
    3. Geschwindigkeit ... nun sind wir auf wackeligen Böden. Schauen Sie sich diese Replik an https://repl.it/repls/RespectfulSufficientWorker Ich habe momentan keinen anständigen Prüfstand, daher habe ich repl.it verwendet ... was für Leistungstests völlig unzureichend ist, aber es ist nicht der Hauptpunkt. Der Punkt ist - es gibt keine eindeutige Antwort. Abgesehen davon, dass Sie in Ihrem Fall, der aus Ihrer Frage nicht ganz klar hervorgeht, BigDecimal definitiv nicht verwenden sollten (lesen Sie weiter).

      Ich habe versucht zu spielen und für große Eingaben zu optimieren. Und Ihr ursprünglicher Code mit einigen geringfügigen Änderungen - der schnellste. Aber vielleicht brauchen Sie enorme Mengen kleiner Lists? Dann kann das eine ganz andere Geschichte sein.

      Dieser Code ist nach meinem Geschmack recht einfach und schnell genug:

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

    Wenn Sie einen eleganteren Weg bevorzugen (oder wir sollten ihn als idiomatisch bezeichnen), würde ich persönlich vorschlagen:

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

    Mögliche Leistungssteigerungen sind:

    1. Versuchen Sie, von zu Doublezu wechseln double, und wenn Sie sie wirklich brauchen, können Sie wieder zurückschalten. Nach den Tests ist dies möglicherweise immer noch schneller. (Aber vertraue mir nicht, versuche es selbst mit deinen Daten in deiner Umgebung. Wie gesagt - repl.it ist scheiße für Benchmarks)
    2. Ein bisschen Magie: separate Schleife für Math.round()... vielleicht hat es etwas mit Datenlokalität zu tun. Ich empfehle dies nicht - das Ergebnis ist sehr instabil. Aber es macht Spaß.

      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. Sie sollten auf jeden Fall in Betracht ziehen, fauler zu sein und bei Bedarf Zahlen zu generieren, ohne diese dann in Lists zu speichern

  4. Ich vermute, dass in den meisten allgemeinen Anwendungsfällen der Rundungsaufwand vernachlässigbar wäre.

    Wenn Sie etwas vermuten - testen Sie es :-) Meine Antwort lautet "Ja", aber noch einmal ... glauben Sie mir nicht. Probier es aus.

Zurück zur Hauptfrage: Gibt es einen besseren Weg?
Ja natürlich!
Aber es kommt darauf an.

  1. Wählen Sie Big Dezimal , wenn Sie sehr brauchen große Zahlen und sehr kleine Zahlen. Aber wenn Sie sie zurückwerfen Doubleund darüber hinaus, verwenden Sie sie mit Zahlen von "enger" Größe - keine Notwendigkeit für sie! Überprüfen Sie die gleiche Antwort: https://repl.it/repls/RespectfulSufficientWorker - Der letzte Test zeigt, dass es keinen Unterschied in den Ergebnissen gibt , sondern einen Geschwindigkeitsverlust.
  2. Nehmen Sie einige Mikrooptimierungen vor, die auf Ihren Dateneigenschaften, Ihrer Aufgabe und Ihrer Umgebung basieren.
  3. Bevorzugen Sie kurzen und einfachen Code, wenn die Leistungssteigerung von 5-10% nicht zu viel bringt. Taille deine Zeit nicht
  4. Verwenden Sie möglicherweise eine Festkomma-Arithmetik, wenn Sie können und wenn es sich lohnt.

Davon abgesehen geht es dir gut.

PS . Es gibt auch eine Implementierung der Kahan Summation Formula in der Antwort ... nur zum Spaß. https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html#1346 und es funktioniert - Sie können Summierungsfehler verringern

x00
quelle