Diskussion zu: Tribonacci Folge Rekursiv

iwer1

Mitglied
Abgezweigt von: https://www.java-forum.org/thema/tribonacci-folge-rekursiv.190470




Hallo!
Ein Lambda approach sollte hier nicht fehlen:
Java:
import java.util.List;
import java.util.stream.*;

public class MyClass {
    public static List<Integer> tribonacci(int n) {
        return Stream.iterate(new int[]{0, 0, 1}, s -> new int[]{s[1], s[2], s[0] + s[1] + s[2]})
                .limit(n)
                .map(a -> a[0])
                .collect(Collectors.toList());
    }
  
    public static void main(String args[]) {
      System.out.println(tribonacci(20));
    }
}
 
Zuletzt bearbeitet von einem Moderator:
K

kneitzel

Gast
So eine Stream Lösung gehört hier aus meiner Sicht nicht hin:
a) reine Anfängerfrage - da geht es um das Verständnis von Rekursion.
b) Die saubere Lösung ist in meinen Augen die iterative Lösung, die @Blender3D gezeigt hat. Einfach zu verstehende 5 Zeilen bei denen auch nicht 2 Werte mehr berechnet werden als unbedingt notwendig (Was in der Stream Lösung der Fall ist).
 
K

kneitzel

Gast
Heul doch ne Runde, anstatt zu zeigen, wie es richtig geht.
Auch @Blender3D s Lösung muss 3 Werte verwenden - das liegt in der Natur des Problems.
Bist Du zurück Tobias? (*srnr*)

Also ich habe nicht geheult, sondern meine einfache Meinung geäußert.
Des weiteren habe ich nur kritisiert, dass Du bei n=20 auch die Werte für 21 und 22 berechnest (und dann beim map aber wegwirfst).

Und nein - ich zeige keine unsinnigen Lösungen, wenn ich es ablehne
a) Anfänger mit Stream-Lösungen zu verwirren
b) Stream Lösungen auf Zwang zu bauen bei der dann zig Array Objekte erzeugt und weggeworfen werden und wenig performantes map verwendet wird. (Aber so Du Tobias bist, wird das ein Versuch sein zu zeigen, dass Stream Lösungen immer schlechte Performance haben ... das war ja seine These für die er nie Argumente bringen konnte ...)

Ansonsten sind hier alle Argumente gesagt - ob Du es nachvollziehen kannst oder nicht ist an der Stelle egal. Ich werde mich da nicht weiter drauf einlassen.
 

iwer1

Mitglied
In dem Fall lässt sich meines Erachtens keine "performantere" Stream Lösung zeigen, da kann alles noch so schöngeredet werden.

Dass vielleicht nach a[2] gemappt werden könnte, stimmt, aber dann wären die ersten Werte der Serie nicht vorhanden.

Und was ich früher vielleicht mal geschrieben habe oder was du dir gedanklich eingebildet hast, steht hier nicht zur Diskussion.
 
K

kneitzel

Gast
In dem Fall lässt sich meines Erachtens keine "performantere" Stream Lösung zeigen, da kann alles noch so schöngeredet werden.
Also eine schnellere Lösung mit Streams könnte man einfach erreichen, indem man im Stream z.B. auf einem externen Array arbeitet. Also unter dem Strich so, wie es @Blender3D mit der Schleife gemacht hat. Dann entfällt das unnötige Erzeugen vieler kleiner Arrays und auch die map Operation.

Aber da wird dann auch schnell deutlich, dass hier eine Stream Lösung einfach keinen Sinn macht, oder worin siehst Du den Sinn in einer solchen oder Deiner Stream Lösung? Wird es lesbarer? Wird es performanter? Was für Vorteile erreichst Du durch diese Lösung?

Ansonsten redet hier niemand etwas schön - außer Dir vielleicht, denn Du hast die Stream Lösung ja als Option ins Spiel gebracht.
 

iwer1

Mitglied
Vielleicht sollte dir zunächst mal klar werden, dass es unterschiedliche Ansätze für dasselbe Problem gibt. Und das bedeutet hier, dass sich die iterative, rekursive und funktionale Lösung immer etwas unterscheiden.

Außerdem sollte man innerhalb des Streams nicht auf außerhalb liegende Variablen/Daten zugreifen (Anti-pattern).
 

Blender3D

Top Contributor
Vielleicht sollte dir zunächst mal klar werden, dass es unterschiedliche Ansätze für dasselbe Problem gibt. Und das bedeutet hier, dass sich die iterative, rekursive und funktionale Lösung immer etwas unterscheiden.
Ah ich verstehe. Du wolltest zeigen wie man die Aufgabe auf keinen Fall machen sollte. Das ist dir gelungen. Du hast recht die Stream Lösung schneidet hier am schlechtesten ab. (Was nicht bedeutet, dass Streams grundsätzlich schlecht sind) Der Input von @kneitzel ist auch sehr treffend, wenn er Stream Beispiele für Anfänger für nicht geeignet hält.
 
K

kneitzel

Gast
Wenn man sich den Code der Streamlösung anschaut, dann juckt es mich in den Fingern, da ein paar einfache Refactorings zu machen. Das Array mit 0,0,1 ist eine Konstante, die ich nicht als Magic Number stehen lassen würde.
Und dann ein Array mit 0,1,2 Feldern ...

Dann führt einen das relativ schnell zu einer Klasse mit Value, Predecessor und PrePredecessor oder so.
Private Konstruktor mit den 3 Werten,
ZERO, FIRST und SECOND als Konstanten macht Sinn, denn die sind ja vorgegeben.
Dann gibt es eine Next Methode.

Dann läßt sich mit Streams arbeiten, aber diese Streams wären dann nichts anderes als ein While-Schleifen Ersatz ... Aber das wäre dann relativ übersichtlich und sauber ...

Vielleicht baue ich das morgen am Rechner mal kurz auf um das zu zeigen ...
 

iwer1

Mitglied
@Blender3D Nein, der Vollständigkeit halber sollte man alle Lösungswege zeigen. Das hat nichts mit schlecht abschneiden zu tun.

@kneitzel Bin gespannt, wie du die mehrfache Array Instantiierung vermeiden willst, ohne auf ein Anti-pattern zurückzugreifen.
 
K

kneitzel

Gast
Ich weiss nicht, was Du nicht an dem text verstehen konntest:
Und nein - ich zeige keine unsinnigen Lösungen, wenn ich es ablehne
a) Anfänger mit Stream-Lösungen zu verwirren
b) Stream Lösungen auf Zwang zu bauen bei der dann zig Array Objekte erzeugt und weggeworfen werden und wenig performantes map verwendet wird. (Aber so Du Tobias bist, wird das ein Versuch sein zu zeigen, dass Stream Lösungen immer schlechte Performance haben ... das war ja seine These für die er nie Argumente bringen konnte ...)
Und Du müsstest Dein "Anti-Pattern" erläutern. Ein Zugriff auf Daten außerhalb des Streams wird abgelehnt... Also nicht nur schreibender Zugriff ... Da wäre ich durchaus interessiert dran. Aber ich habe bisher darauf verzichtet nachzuhaken, da ich diesen Thread nicht mit solchen Diskussionen füllen möchte. (@mrBrown Evtl. abtrennen in einen eigenen Thread, so da etwas kommen sollte?)
Die Lösung mit dem Array wäre eine valide Lösung ohne Nebeneffekte, daher ist so eine limitierte Sichtweise einfach lachhaft. (Wobei ich ja schon deutlich gemacht habe, dass eine Stream Lösung auf Zwang in meinen Augen so einfach Quatsch ist!)

Aber wenn ich das aufbauen müsste, dann wäre so eine Lösung denkbar:
Java:
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class TribonacciNumber {
    public static final TribonacciNumber ZERO = new TribonacciNumber(0, null);

    private int value;
    private TribonacciNumber predecessor;

    public Integer getValue() { return value; }

    public TribonacciNumber getPredecessor() { return predecessor; }
   
    private TribonacciNumber(int value, TribonacciNumber predecessor) {
        this.value = value;
        this.predecessor = predecessor;
    }

    private TribonacciNumber next() {
        if (predecessor == null) return new TribonacciNumber(0,this);
        if (value == 0) return new TribonacciNumber(1, this);
        return new TribonacciNumber(value+predecessor.value, this);
    }

    @Override
    public String toString() {
        return Integer.toString(value);
    }

    public static List<TribonacciNumber> rangeTo(int n) {
        return Stream.iterate(ZERO, s -> s.next())
                .limit(n+1)
                .collect(Collectors.toList());
    }
}

Was aus meiner Sicht die wichtigen Punkte hier sind:
a) Klare Berechnung - in dem next findet sich mehr oder weniger direkt die Definition. Lediglich das n = 0 / n = 1 / n = 2 sind als Kriterium etwas umgeschrieben.
b) Klare Beschreibung - also kein Zugriff über Array-Operator mit 0, 1 und 2.

Und natürlich: Es werden nicht mehr Werte berechnet, als notwendig. Das mag hier zwar uninteressant sein, wenn da zwei Werte mehr berechnet werden, aber das ist schon eine prinzipielle Sache ... Es kann ja auch mal um mehr gehen als nur die Addition von zwei Zahlen.
 

iwer1

Mitglied
Also ein Lambda approach, der für den Menschen nicht mehr verständlich ist/wäre brauchen wir nicht.

@mrBrown ggf. wäre es sinnvoll, das Thema aufzuteilen, wobei aber ein Lambda approach mindestens im Thema bleiben sollte (für den TE).
 
K

kneitzel

Gast
Weil hier angebracht wurde, dass ja das funktionale Lösen hier auch in de Thread gehören würde (dem kann ich nicht wirklich folgen, denn der Thread umfasste explizit die rekursive Methode in Java. Da gehört das einfach nicht rein! Zumal dieser Stream Ansatz ja mit funktionaler Entwicklung nicht wirklich so viel zu tun hat.

Wenn das aber jemanden wirklich interessiert, dann sollte sich dieser z.B. einmal die Möglichkeiten zur Lösung in Haskell anschauen. Tribonacci ersetzen wir einfach mal per Fibonacci und schon gibt es da einen sehr schönen Wiki Eintrag:
Wenn man sich also mit funktionaler Entwicklung beschäftigen möchte, dann wäre das ein guter Ansatz. Aber im Java Bereich sehe ich nur eine relativ geringe Relevanz diesbezüglich. (Aber da kann man mich gerne eines besseren belehren...)

Und wenn man die unterschiedlichen Paradigmen voll machen möchte, dann wäre noch die logische Entwicklung. Die ist bei sowas in meinen Augen übrigens sehr anschaulich, denn da geht es ja einfach um Regeln und Wissen. Sprich: Man hinterlegt das Wissen des Anfangs und zusätzlich die Regel, wie man den Nachfolger berechnet und der Rest erfolgt dann automatisch. Wie das aussehen kann in Prolog sieht man dann z.B. unter: https://gist.github.com/hoelzro/3973656

Und ehe da was kommt a.la. dies ist ein Java Forum:
a) Ja, daher spielt diese funktionale Entwicklung keine Rolle. Das was Java da bietet ist ein Witz im Vergleich zu dem eigentlichen funktionalen Entwickeln z.B. mit haskell.
b) Natürlich geht das logische Entwickeln auch mit Java. Da braucht es ja nur eine entsprechende Inferenzmaschine, die die Auswertung des Wissens und der Regeln durchführt. Und zur Not greift man dann auf Lösungen dafür zurück wie http://www.jiprolog.com/.

Aber bezüglich der Fragestellung des TE: Dies ist komplett OffTopic und uninteressant.
 
K

kneitzel

Gast
@kneitzel Da wird zwar jedes Mal ein neues Array erstellt, jedoch werden die Arrays doch hinterher (oder zwischendurch(?) wer weiß) wieder verworfen. Ich weiß gar nicht was du hast, das ist bei deinem Vorschlag glaube ich auch so.

Als kryptisch empfinde ich das noch nicht.
Ja, sie werden wieder verworfen. Vergleichbar mit dem Zusammenbau von Strings mit +.

Aber das war ja auch kein Punkt, der mich wirklich interessierte.

Abet Dein Anti-Pattern solltest du noch ausführen, denn so pauschal würde ich das so nie formulieren. Und da du das angebracht hast, wirst Du Dir ja was dabei gedacht haben ...
 

Ähnliche Java Themen

Neue Themen


Oben