Ein Kollege frage mich, wie ich in Java 8 am besten eine laufende Summe eines Streams ermittle. Nun haben die Java-Götter kein scan() wie in Scala oder Haskell spendiert, und so war das beste, was mir einfiel:
AtomicInteger accu = new AtomicInteger(0);
List<Integer> list = Stream.of(1, 2, 3, 4, 5)
.map(i -> i + accu.getAndUpdate(j -> i + j))
.collect(Collectors.toList()); //1,3,6,10,15
Gibt es einen weniger “hackeligen” Weg, das zu erreichen?
Das ist das “Hammer/Nagel”-Syndrom.
Streams sind Javas functional programming Feature.
Einer der Grundpfeiler von FP ist, dass die Elemente einer Liste keinerlei Bezug zueinander haben. Das ist beispielweise wichtig, um die Streamsverarbeitung parallelisieren zu können.
In deinem Beispiel ist aber die Reihenfolge der Elemente in der Eingangsliste (was eben genau eine Beziehung dieser Elemente untereinander darstellt) wichtig, weil sonst die Ergebnisliste falsach ist.
Ergo: FP (und damit Streams) ist nicht der beste Ansatz dieses Problem zu lösen…
Wenn man also schon mit der Wahl des Werkzeugs nicht ganz auf der Linie liegt kann man es auch richtig mißbrauchen (normaler Weise ist die Verwendung von .forEach() ein sicheres Zeichen, dass Streams nicht optimal ist):
List<Integer> runningSum = new ArrayList<>();
List<Integer> list = Stream.of(1, 2, 3, 4, 5)
.forEach(i -> runningSum .add(i+ runningSum.stream().mapToInt(j->j).sum() ));
bye
TT
Das Argument kann ich nicht ganz nachvollziehen. Funktionale Sprachen wie Haskell haben eine scan Funktion, die genau dieses Problem löst, also kann es gar nicht so ein “Nicht-FP”-Problem sein: http://hackage.haskell.org/package/base-4.11.1.0/docs/Prelude.html#v:scanl
Ich denke eher, dass Java Streams einfach noch zu beschränkt sind (teilweise wurde ja schon nachgebessert, z.B. mit takeWhile in Java 9)
Deine Lösung hat übrigens eine quadratische Laufzeit, meine ist linear.
Habe übrigens noch eine andere Variante gefunden:
Stream.of(1, 2, 3, 4, 5)
.collect(ArrayList<Integer>::new,
(l, r) -> l.add(l.size() > 0 ? l.get(l.size() - 1) + r: r),
ArrayList<Integer>::addAll);
Kein Zugriff auf die Umgebung mehr, aber nicht unbedingt besser zu verstehen und wahrscheinlich weniger performant.
Provokante Frage meinerseits:
Warum sollte Haskel die einzige Programmiersprache sein, die keine Konstrukte enthält, die der „reinen Lehre“ des der Sprache zu Grunde liegenden Pradigmas widersprechen?
Sicher.
Aber da habe ich dann dieses Schlagwort: premature optimization…
Sicher könnte theoretisch auch Haskell auch nicht so FP-mäßige Sachen enthalten (praktisch eher weniger, da musst du erst mal an Menschen wie Edward Kmett vorbei), aber in dem Fall ist es eben nicht die einzige Sprache:
Scala: Scala Standard Library 2.12.3 - scala.collection.TraversableLike
Clojure: reductions - clojure.core | ClojureDocs - Community-Powered Clojure Documentation and Examples
Python: itertools — Functions creating iterators for efficient looping — Python 3.12.1 documentation
Sag ich doch…
Hmm… geht denn da nichts mit “forEach(Consumer c)”?
final int[] chksum = new int[1];
Stream<Integer> s = Stream.of(1,2,3,4,5);
s.forEach(new Consumer<Integer>() {
public void accept(Integer t) {
chksum[0] += t;
};
});Das summiert nur alles auf, ich will auch die Zwischenergebnisse haben.
Abgesehen davon, dass Stream::forEach void zurückgibt, ist das Ergebnis aus deiner runningList auch komplett anders, bzw. falsch (1,3,7,15,31)
Und warum Spacerat hier ein Integer-Array verwendet, erschliesst sich mir auch nicht wirklich, wenn es nur um einen Integer geht.
Landei hat bereits was mit collect gehabt, das identisch ist.
Lediglich bei Landei ist das ArrayList::addAll fehlerträchtig und sollte lieber durch sowas geändert werden, damit auch ein parallel funktioniert.
Stream<Integer> stream = Stream.generate(() -> 1).limit(100000);
//stream = Stream.of(1,2,3,4,5);
List<Integer> result = stream.parallel()
.collect(ArrayList::new, (a, b) -> {
if (a.size() == 0) {
a.add(b);
} else {
int last = a.get(a.size() - 1);
a.add(last + b);
}
},
(a, b) -> {
if (a.size() == 0) {
a.addAll(b);
} else {
int last = a.get(a.size() - 1);
List<Integer> c = b.stream().map(i -> i + last).collect(Collectors.toList());
a.addAll(c);
}
}
);
result.forEach(System.out::println);
Wobei, das schon etwas absurd wirkt.
Nicht direkt. Premature optimization ist, wenn man systematisch durch den Code geht und jedes for(int i=0;i<n;i++) durch for(int i=0;i<n;++i) ersetzt, oder jedes int y = x * 3; durch int y = x+x+x;. Wenn es um die asymptotische Komplexität geht, ist das nicht „premature“ und nicht „optimization“, sondern „don’t implement crap due to laziness“ oder so.
Aber wenn man weiß, dass die Eingabe „klein“ ist (d.h. nur wenige hundert Elemente enthält), macht es wohl schlicht keinen Unterschied, und dann sind das nicht die 3%, um die es geht, und man sollte die einfachste Lösung verwenden.
Trotzdem, in bezug auf die Frage, ob es sinnvoll ist, einen (prefix) scan parallel zu berechnen, verweise ich mal auf Vector Models for Data-Parallel Computing von Guy Blelloch.
Das wirft aber tatsächlich die Frage auf, was für ein stream das denn ist. Man kann zwar prinzipiell rausfinden, ob der stream „ordered“ ist oder nicht, aber tatsächlich wäre die Implementierung auf einem Array vieeel einfacher, wenn man es „gut“ (d.h. effizient parallel) machen wollte. Einen „normalen, kleinen stream“ denke ich, dass die Lösung aus dem Eröffnungsbeitrag die mit dem besten Verhältnis zwischen Kompaktheit, Performance und Lesbarkeit hat.
(Das erste mal, dass ich eine accepted Answer mit MINUS 25 votes gesehen habe: c++ - Parallel prefix sum - fastest Implementation - Stack Overflow )
Ist doch auch kein Ding
Stream<Integer> s = Stream.of(1,2,3,4,5);
final List<Integer> chkSums = new ArrayList<>();
s.forEach(new Consumer<Integer>() {
int sum = 0;
public void accept(Integer t) {
sum += t;
chkSums.add(sum);
};
});