Fibonaccizahlen, Iteratoren und andere Spielereien

for (int i=0,f[2]={0,1};f[i%2]<=9999;++i,f[i%2]=f[0]+f[1])
    if (f[i%2]>999) std::cout << f[i%2] << '\n';

Sone

Was mir gerade auffällt: Ich weiß, es passt nicht zum Iteratoren-Modell von C++, aber wie wäre denn ein Java-like Iterator? Einer, der eine Methode hasMore() bereitstellt?
Das wäre doch einfacher als deine Policy.

nwp3 schrieb:

Auch auf die Gefahr als Ignorant dazustehen: Du hast aus einem Dreizeiler eine über 100 Zeilen große C++-Bestie gemacht. Als Spielerei ganz nett, aber unverständlich bis zum geht nicht mehr. Daher frage ich mal direkt: Ist das für dich eine ernsthafte Lösung oder mehr fürs C++-Äquivalent zum IOCCC?

Wenn du mich meinst: Spielerei natürlich ^^

Werner Salomon

Zunächst dachte ich ja da meldet sich keiner mehr, aber jetzt sieht's schon gut aus

Da Sone hier wohl den meisten Raum einnimmt

Sone schrieb:

Hast du den Thread denn nicht aufmerksam gelesen? Das Ding das ich damals gebastelt hab'... sieh es dir nochmal an...

Welcher Thread - gibt es da einen Link? Was hast Du gebastelt, was soll ich mir ansehen?

Meine älteste Datei, hier auf dem PC, an dem ich gerade sitze, die eine Fibonacciiterator-Implementierung enthält, hat einen Zeitstempel von 2008 - und das war lange nicht die erste. Ich glaub' das habe ich mal für eine Project-Euler-Aufgabe gemacht. Da warst Du (Sone) noch nicht mal hier im Forum registriert.
Und die Idee so etwas in einen Iterator zu pressen, haben sicher schon viele gehabt - sogar Sone (wie's aussieht).

CJosef schrieb:

Blähware!
Idee: beschränke dich aufs Notwendige und mach da keinen ~~Hermann~~ Werner draus!

Vielleicht hätte ich noch ein paar einleitende Worte spendieren sollen.
Zunächst mal ist das hier eine Spielerei - zumal mit der Anwendung auf Fibonaccizahlen. Natürlich kann man es reduzieren

nnI schrieb:

Dafür braucht man nur eine Rekursive Methode mit 3 Zeilen

auch ohne Rekursion käme man mit weniger als 3 Zeilen hin. Aber darum ging es gar nicht.

Motivation 1 war einfach mal zu zeigen, es geht.

Motivation 2 ist auch zu zeigen, wie (und dass!) man das Iterieren kapseln kann (in einem Iterator - wie sinnig). Außer iterieren wird in dem hier vorliegenden Beispiel nicht viel gemacht - die Zahl wird schlicht ausgegeben. Deshalb kommt das hier auch nicht so raus, wo da der Vorteil sein soll - mea culpa.
Aus meiner beruflichen Praxis sind mir aber ad hoc zwei Fälle bekannt, wo iterieren und bearbeiten des aktuellen Elements ein etwas chaotischer Code von mehreren tausend Zeilen geworden sind. Spitzenreiter war eine for-Schleife mit knapp 1000 Zeilen, die gespickt war mit Fallunterscheidungen und Funktionsaufrufen, die sowohl die Iteration, als auch die Bearbeitung betrafen. Dieser Code wurde nur noch von zwei Leuten gleichzeitig bearbeitet, da man Angst hatte, dass einer allein vielleicht etwas übersieht. Ich hatte irgendwann mal entschieden, alles weg zu werfen und neu zu schreiben (mit Iterator) - ich habe es nie bereut - ganz im Gegenteil.

cooky451 schrieb:

Man mag darüber streiten ob man das nicht auch ohne boost implementieren hätte können, aber die Iteratorvariante mit dem Schulaufgaben-Dreizeiler zu vergleichen, zeugt einfach nur von völliger Ahnungslosigkeit.

cooky451 scheint ähnlich gelagerte Fälle zu kennen.
Darüber hinaus ist es nämlich in vielen Fällen der Praxis gar nicht offensichtlich, dass überhaupt eine Iteration vorliegt (wie z.B. bei einer Zahlenfolge).

Motivation 3 war zu zeigen, wie es mit boost.iterator geht. Hat man die Auswahl der Template-Argumente erst mal überstanden, dann ist der Rest fast geschenkt. Find' ich persönlich einfach mal cool - das ist genau dass was Bjarne Stroustrup mit Spaß an der Programmierung meint. Ob man das im Einzelfall auch einsetzt oder nicht, sollte natürlich von anderen Kriterien abhängen - aber in einem Forum wie hier ist das doch ein lohnendes Thema - IMHO.

:xmas2: Werner

(to be continued)

Sone

Gut gut, war auch nur eine Vermutung. :xmas2:
(Mit "den Thread" meinte ich den Thread den du im ersten Post verlinkt hast. Da habe ich auch was iterierbares gebastelt, dachte du hast die Idee genommen und was schöneres draus gemacht, war offensichtlich nicht der Fall)

Werner Salomon

Hallo dodapisa,

Danke für Deinen Beitrag

dodapisa schrieb:

Es ist mMn nicht die Aufgabe eines Iterators herauszufinden, ob er am Ende ist oder nicht. Keep Iterators Simple, Stupid (oder so).

das ist die Frage, im Grunde tut das doch jeder Iterator irgendwie. Allen voran die istream- und istreambuf-Iteratoren. Der istream_iterator versucht in seiner operator++-Methode ein weiteres Element zu lesen. Er merkt sich (muss sich merken) wenn das schief geht. Und damit wird er dann zum Ende-Iterator.
Weiter sind mir auch Implementierungen von Iteratoren Assoziativer Container (map, set, etc.) bekannt, die ganz klar im operator++ feststellen - ich bin am Ende und ein interner Zeiger bekommt dann einen definierten Wert, der identisch ist, mit dem des Ende-Iterators.

dodapisa schrieb:

Dein Design funktioniert auch nur halb. Ich sehe zumindest keine Lösung mit deinem Iterator, die die 4-stelligen Fibonaccizahlen ausgibt und ohne Schleifen auskommt.

Zwei Vorschläge dazu:

typedef fibonacci::iterator< int, function< bool( int, int ) > > Fibo;
    copy( find_if( Fibo( 1,0, []( int prev, int fn )->bool { return prev + fn >= 10000; } ), Fibo(), []( int fn )->bool { return fn >= 1000; } ), Fibo(),
        ostream_iterator< int >( cout << "Die 4-stelligen Fibonaccizahlen lauten: ", " " ) );
    cout << endl;

und

auto _4stellig = []( int fn )->bool { return fn >= 1000 && fn < 10000; };
    copy( boost::make_filter_iterator( _4stellig, fibonacci::iterator< int >(1,0) ), boost::make_filter_iterator( _4stellig, fibonacci::iterator< int >() ),
        ostream_iterator< int >( cout << "Die 4-stelligen Fibonaccizahlen lauten: ", " " ) );
    cout << endl;

dodapisa schrieb:

Eine unendliche Folge ist kein Weltuntergang, der ostream_iterator hat auch kein Ende.

Der ostream_iterator ist ein Outputiterator und der Fibonacci-Iterator ist ein Inputiterator. Das gilt für alle Zahlenfolgen-Iteratoren.
Für einen Outputiterator ist z.B. ein ==-Operator gar nicht gefordert, da ein Algorithmus (z.B. copy) den aktuellen Outputiterator nie auf Ende abfragt. damit ist auch kein Ende-Iterator erforderlich. Inputiteratoren ohne Ende gehen nur mit den *_n-Algorithmen - außer copy_n fällt mir i.A. gar keiner ein.
D.h. ohne Endeiterator müsste man auf die ganzen schönen Vorteile der Algorithmen verzichten.

dodapisa schrieb:

Dummerweise gibt es nur einen Algorithmus in der Standardbibliothek, der unendliche Input-Iteratoren erlaubt, copy_n . Deshalb habe ich mir ein copy_until geschrieben und damit kann das Problem ähnlich kurz gelöst werden: ...

So was wie until-Algorithmen hatte ich auch schon mal im Focus. Aber außer bei Project-Euler (alles geht bis unendlich) hatte ich dafür praktisch keine Verwendung.

dodapisa schrieb:

Weil dein Iterator bei mir nicht kompiliert (vielleicht habe ich eine zu alte Boost-Version), habe ich ihn in begrenzterer Form noch einmal geschrieben.

Ich benutze VS10 mit boost 1.48 - was benutzt Du?

Gruß
Werner

nn

Werner Salomon schrieb:

Vielleicht hätte ich noch ein paar einleitende Worte spendieren sollen.
Zunächst mal ist das hier eine Spielerei - zumal mit der Anwendung auf Fibonaccizahlen. Natürlich kann man es reduzieren

Wie sähe denn eine reduzierte Lösung in modernem C++ aus ? Möglichst unter Erhaltung der Struktur des originalen Algorithmus.

Also quasi die C++11 Variante von dem hier:

public static IEnumerable<uint> AllFibos()
{
    uint a = 1;
    uint b = 1;

    do
    {
        yield return a;

        try
        {
            uint c = checked(a + b);
            a = b;
            b = c;
        }
        catch (OverflowException)
        {
            break;
        }
    } while (true);
}

In C# fällt mir das Denken von Folgen als Aufzählungen irgendwie leichter.

nn

Ok, habe selber mal etwas probiert und bin soweit gekommen

class Fibos : public std::iterator<std::input_iterator_tag, unsigned int, ptrdiff_t, unsigned int const*, unsigned int>
{
private:
  unsigned int m_a;
  unsigned int m_b;
public:

  Fibos() : m_a(1), m_b(1)
  {}

  operator bool() const 
  { 
    return m_a <= m_b; 
  }

  Fibos& operator++() 
  { 
    unsigned int tmp = m_a;
    m_a = m_b;
    m_b += tmp;

    return *this; 
  }

  Fibos operator++(int) 
  { 
    Fibos tmp = *this; 
    ++*this; 
    return tmp; 
  }

  unsigned int operator*() const 
  { 
    return m_a; 
  }

  unsigned int const* operator->() const 
  { 
    return &m_a;
  }
};

Ist zwar nicht perfekt, aber das Prinzip ist mir jetzt klar. :xmas2:

Werner Salomon

nn schrieb:

Werner Salomon schrieb:

Zunächst mal ist das hier eine Spielerei - zumal mit der Anwendung auf Fibonaccizahlen. Natürlich kann man es reduzieren

Wie sähe denn eine reduzierte Lösung in modernem C++ aus ?

Ich meinte mit reduzierte Lösung das, was z.B. derzweizeiler gepostet hat (s.o.). 'modernes C++' braucht es da nicht. Mein Favorit sähe etwa so aus:

for( int prev = 1, fn = 0; fn < 10000; prev += fn, swap( fn, prev ) )
        if( fn >= 1000 )
            cout << fn << " ";

nn schrieb:

Möglichst unter Erhaltung der Struktur des originalen Algorithmus.

keine Ahnung, was Du damit meinst. Der Algorithmus ist immer unverändert - so oder so.

nn schrieb:

Also quasi die C++11 Variante von dem hier:

public static IEnumerable<uint> AllFibos()
{
    uint a = 1;
    uint b = 1;

    do
    {
        yield return a;

        try
        {
            uint c = checked(a + b);
            a = b;
            b = c;
        }
        catch (OverflowException)
        {
            break;
        }
    } while (true);
}

Ich vermute mal, dass das 'yield return a;' soviel wie push_back-in-den-Ergebnis-Enumerator bedeutet. Dann macht das für mich Sinn.

nn schrieb:

In C# fällt mir das Denken von Folgen als Aufzählungen irgendwie leichter.

alles Gewohnheit

nn schrieb:

Ok, habe selber mal etwas probiert und bin soweit gekommen
...
Ist zwar nicht perfekt, aber das Prinzip ist mir jetzt klar. :xmas2:

Fein

:xmas2: Werner

nn

Werner Salomon schrieb:

Ich meinte mit reduzierte Lösung das, was z.B. derzweizeiler gepostet hat (s.o.). 'modernes C++' braucht es da nicht. Mein Favorit sähe etwa so aus:
for( int prev = 1, fn = 0; fn < 10000; prev += fn, swap( fn, prev ) )
        if( fn >= 1000 )
            cout << fn << " ";

Das ist aber auch wieder nur eine Lösung, die alles im Voraus berechnet. Der wichtigste Grund, Folgen über Iteration darzustellen, wurde ja im Thread genannt: Lazy Evaluation.

Bei Fibonaccizahlen macht das sicher keinen Sinn, aber von z.B. der Folge der Primzahlen will man sicher nicht erstmal welche berechnen, wenn es z.B. um ein Problem geht, wie "welches ist die kleinste Primzahl für die gilt ...". Natürlich macht es da auch nur Sinn, wenn man verschiedene Abfragen auf solche Folgen machen will. Da kann man dann auch noch optimieren und schon berechnete Elemente cachen, damit neue Iteratorinstanzen nicht alles noch mal berechnen.

Man kann solche Aufzählungen auch schön verketten. Wenn man sich, ich bleib mal bei C#, so was schreibt

AllFibos().Where(n => n % 2 == 0)

kann man über die geraden Fibonaccizahlen iterieren. Darum die Frage, wie man das in modernem C++ machen würde.

Werner Salomon schrieb:

nn schrieb:

Möglichst unter Erhaltung der Struktur des originalen Algorithmus.

keine Ahnung, was Du damit meinst. Der Algorithmus ist immer unverändert - so oder so.

Ich meinte mit Struktur, dass nicht alle Teile der Implementierung über z.B. verschiedene Member der Iteratorimplementierung verteilt rum liegen. Z.B. die Überlaufprüfung in meinem C++ Experiment.

Werner Salomon schrieb:

Ich vermute mal, dass das 'yield return a;' soviel wie push_back-in-den-Ergebnis-Enumerator bedeutet. Dann macht das für mich Sinn.

Es passiert ähnliches wie bei einer Lambda-Expression. Funktionen, die yield return enthalten, werden hinter den Kulissen in Objekte verpackt. Das Ende der Funktion ist auch das Ende des Iterators.

In soweit hatte ich den Thread falsch verstanden. Ich dachte es geht um effizientes Arbeiten mit, potentiell unendlichen, Zahlenfolgen. Dabei ging es doch nur darum, sich an kompliziertem Code zu ergötzen.

Shade Of Mine

nn schrieb:

In soweit hatte ich den Thread falsch verstanden. Ich dachte es geht um effizientes Arbeiten mit, potentiell unendlichen Zahlenfolgen. Dabei ging es doch nur darum, sich an kompliziertem Code zu ergötzen.

Mag sein - aber prinzipiell ist die C++ Lösung hier schon korrekt: einen Iterator schreiben.

Denn nichts anderes macht man in C# - nur dass man in C# mit yield halt absolut genial den Iterator verstecken kann.

Werner Salomon

nn schrieb:

Darum die Frage, wie man das in modernem C++ machen würde.

Wenn Du das so meinst, dann würde ich sagen, so wie gezeigt.

nn schrieb:

Ich meinte mit Struktur, dass nicht alle Teile der Implementierung über z.B. verschiedene Member der Iteratorimplementierung verteilt rum liegen. Z.B. die Überlaufprüfung in meinem C++ Experiment.

Ja - das ist ein wichtiger Punkt. Genau das versuchte ich hier zu erläutern.

Werner Salomon schrieb:

Motivation 2 ist auch zu zeigen, wie (und dass!) man das Iterieren kapseln kann (in einem Iterator - wie sinnig).

Es geht auch darum, das Iterieren und damit auch 'Definition des Endes' von der eigentlichen Aktion auf dem Element zu entkoppeln.

nn schrieb:

Ich dachte es geht um effizientes Arbeiten mit, potentiell unendlichen, Zahlenfolgen. Dabei ging es doch nur darum, sich an kompliziertem Code zu ergötzen.

Keineswegs, ich hatte oben schon darauf hingewiesen, dass das durchaus einen praktischen Belang hat - wenn auch das Beispiel mit Fibonaccizahlen eher theoretischer Natur ist.

Für Projekt Euler hatte ich mir unter anderen einen Primzahl-Iterator, einen Iterator für Pythagoräische Tripel, eine Iterator für die Teiler einer Zahl und andere geschrieben. Das schöne ist, dass man sie ruckzug für neue Aufgabe wieder verwenden konnte. Und wenn der Bereich nicht reicht, muss mal halt für das Templateargument statt ' long ' eine selbst geschriebenes BigInt nehmen.

Gruß
Werner

knivil

Naja, ich bin der Meinung, wenn man Lazy Evaluation benoetigt, dann sollte wohl eher zu Haskell gegriffen warden. Auch ist ein Iterator konzeptionell verschieden von einer Liste. Naechster Punkt: Wie kombinere ich verschiedene Lazy Listen/Iteratoren mittels map, filter fold um neue Lazy Listen/Iteratoren zu erhalten?

Wenn modernes C++ mittlerweile das Schreiben von Code ist, bei dem man 10mal so lang braucht ihn zu verstehen, sollte man nicht mehr so viel modernes C++ schreiben.

nn

knivil schrieb:

Naechster Punkt: Wie kombinere ich verschiedene Lazy Listen/Iteratoren mittels map, filter fold um neue Lazy Listen/Iteratoren zu erhalten?

Ich bin nicht sicher, auf wen sich diese Frage bezieht. Daher beantworte ich sicherheitshalber mal den C# Teil.

Auch diese Verkettungen sind lazy, Stichwort: Defered Execution.

Zum Verpacken von schwer zu berechnenden Objekten bietet sich in C# auch noch Lazy<T> an, sowas kann man in C++ aber einfach mit einem Smart Pointer nachbauen.

Wenn man mehr funktional programmieren will, kann man C# auch noch mit in F# geschriebenem Code ergänzen. Man kann die meisten F# Konzepte aber auch in C# nachbauen, siehe z.B. das Buch "Real World Functional Programming".

knivil

Ich meinte das schon im Kontext von C++ und denke dabei nicht an schwer zu berechnene Objekte. Iteratoren dienten hier um unendliche Datenstrukturen wie Liste von Fibonaccizahlen abzubilden. Angenommen ich habe zwei unendliche Listen als Iteratoren, wie kombiniere ich sie, um einen neuen Iterator ueber eine unendliche Datenstruktur zu erhalten, also ein Iteratorcombinator ist gesucht. Eine Loesung mittels Lazy<T> oder Smartpointer fuer unendliche Datenstrukturen passt nicht in das Konzept von Iteratoren als Abbildung von unendlichen Datenstrukturen.