NG Programmiersprache?

Mr. N

nachfrager schrieb:

Warum soll das performanter sein?

Weil die Fibonacci-Zahlen nicht immer wieder berechnet werden. Wenn du fib 4 rekursiv berechnest, berechnest du fib 1, fib 2, fib 3 und fib 4 immer auch (bei der naiven Rekursion sogar teilweise mehrfach). Bei der rekursiven Liste von volkard werden die Zahlen nur einmal berechnet und wiederverwendet.

Zeus

Wenn ich blos den "Rekursionsschritt"? bei der Version erkennen würde

volkard

Also baue ich mir zuerst Schlösser mit 5 Stockwerken der Abstraktion und muß dann doch selber die Abstraktion bis runter auf sagen wir mal C-Niveau auflösen und mir vorstellen, wie er es innendrin macht, damit ich nicht in eine Falle tapse, und eine sehr langsame Funktion baue. Uih, das würde mich aber ein bißchen nerven.

Mr. N schrieb:

nachfrager schrieb:

Warum soll das performanter sein?

Weil die Fibonacci-Zahlen nicht immer wieder berechnet werden. Wenn du fib 4 rekursiv berechnest, berechnest du fib 1, fib 2, fib 3 und fib 4 immer auch (bei der naiven Rekursion sogar teilweise mehrfach). Bei der rekursiven Liste von volkard werden die Zahlen nur einmal berechnet und wiederverwendet.

Da nehme ich dann doch lieber eine for-schleife.

Mr. N

hehe schrieb:

Da nehme ich dann doch lieber eine for-schleife.

Dann zeig deine Künste.

Zeus

Mr. N schrieb:

hehe schrieb:

Da nehme ich dann doch lieber eine for-schleife.

Dann zeig deine Künste.

Uninstressant, die For-Schleife für Fibonacci steht bei Stackoverflow. Hab ich gemerkt nachdem ich meine implementiert habe *gg*.

Mr. N

Zeus schrieb:

Mr. N schrieb:

hehe schrieb:

Da nehme ich dann doch lieber eine for-schleife.

Dann zeig deine Künste.

Uninstressant, die For-Schleife für Fibonacci steht bei Stackoverflow. Hab ich gemerkt nachdem ich meine implementiert habe *gg*.

Dann könnte man vergleichen, welche Methode komplizierter ist.

Zeus

http://stackoverflow.com/questions/1518726/recursive-fibonacci

int fib(int n)
{
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }           
    return b;
}

Auf die iterative Version bin ich nur darauf gekommen, weil ich es in Tabellenform auf Papier gebracht habe.

Mr. N

Erstmal was ganz anderes: Überleg dir doch, nano-lang auf github zu schieben.

Zeus schrieb:

http://stackoverflow.com/questions/1518726/recursive-fibonacci
int fib(int n)
{
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }           
    return b;
}
Auf die iterative Version bin ich nur darauf gekommen, weil ich es in Tabellenform auf Papier gebracht habe.

OK, dann vergleichen wir es mal mit der berühmten idiomatischen Haskell-Version:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Mal davon abgesehen, dass diese Version eine _Liste_ _aller_ Fibonacci-Zahlen erzeugt, also [1,1,2,3,5,8,13,21...]...

Die iterative Version von dir besitzt durchaus eine beachtliche Komplexität. Man muss schon nachdenken, was das macht. Genauso wie bei der Version mit zipWith. Natürlich ist für dich die iterative Version einfacher, weil du es seit Jahren übst, auf iterative Algorithmen zu starren, und sie zu entziffern. Bei den funktionalen Pendants fehlt dir da einfach die Übung.

Aber das ist nichts angeborenes. Beide Algorithmen sind für einen sehr unerfahrenen Programmierer undurchdringlich.

Ich habe mir mal die Mühe gemacht, den iterativen Algorithmus so umzubauen, dass er auch eine unendliche Liste von Fibonacci-Zahlen (modulo 2⁶⁴) erzeugt:

boost::uint64_t a = 1, b = 1;
cout << "1 1 ";
for (int i = 3; ; i++) {
    boost::uint64_t c = a + b;
    a = b;
    b = c;
    cout << b << ' ';
}

Antoras

Also ich finde, dass rekursive Algos oft deutlich einfacher zu lesen sind als die iterativen. Auch weil sie viel kürzer sind. Weiterer Vorteil der rekursiven Variante: man hat unveränderliche Objekte.

Zeus

@Mr.N
Nur weil ich für hehe antworte, heisst es nicht, dass ich es leichter finde. Ich find die Version, die Volkard gepostet habe, am leichtesten

volkard

Naja, die hier gewählte Sprache ist auch irgendwie nicht passend zum Problem.

Vielleicht würde Paarzuweisung was retten.

int fib(int n)
{
    alt,neu = 1,1;
    for i=3 to n
      alt,neu = neu,alt+neu
    return neu
}

Oder yield? Nee, eher nicht.

Vielleicht mit swap.

int fib(int n)
{
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++)
       swap(a+=b,b);
    return b;
}

Nein, eher auch nicht.

volkard

Mr. N schrieb:

Ich habe mir mal die Mühe gemacht, den iterativen Algorithmus so umzubauen, dass er auch eine unendliche Liste von Fibonacci-Zahlen (modulo 2⁶⁴) erzeugt:
boost::uint64_t a = 1, b = 1;
cout << "1 1 ";
for (int i = 3; ; i++) {
    boost::uint64_t c = a + b;
    a = b;
    b = c;
    cout << b << ' ';
}

Ja.
Oder

10 a=1:b=1
20 a=a+b:print a
30 b=b+a:print b
40 goto 20

volkard schrieb:

10 a=1:b=1
20 a=a+b:print a
30 b=b+a:print b
40 goto 20

back to basic

Nexus

Mr. N schrieb:

Die iterative Version von dir besitzt durchaus eine beachtliche Komplexität. Man muss schon nachdenken, was das macht. Genauso wie bei der Version mit zipWith. Natürlich ist für dich die iterative Version einfacher, weil du es seit Jahren übst, auf iterative Algorithmen zu starren, und sie zu entziffern. Bei den funktionalen Pendants fehlt dir da einfach die Übung.

Dass man mit funktionalen Programmiersprachen gewisse Anweisungen sehr elegant und kompakt ausdrücken kann, bestreite ich gar nicht. Das ist ja auch etwas, was mir an Haskell so gefällt. Allerdings erfordert dieser Weg einige Abstraktion, zum Beispiel viel mehr als eine Schleife. Oder zumindest eine andere Art von Abstraktion, von der ich behaupte, dass sie am Anfang weniger naheliegend und intuitiv ist.

Nimm zum Beispiel Pseudocode: Er dient dazu, unabhängig von der Programmiersprache Abläufe und Algorithmen zu beschreiben. Und er besitzt oft die Form eines iterativen Rezepts wie bei der Schleife hier, je nach Problem auch einer einfachen Rekursionsvorschrift. Aber sowas Ähnliches wie zipWith findet man nirgends, weil High-Order-Functions eher schwierig zu verstehen sind. Hingegen ist ein

f(n) = f(n-1) + f(n-2)
f(0) = 0
f(1) = 1

auch für Leute verständlich, die gar nicht programmieren können.

Ironisch ist doch, dass sowohl C++ als auch Haskell die Fibonacci-Berechnung so formulieren könnten. Aber in Haskell nimmt man aus Performancegründen zipWith und tail , und in C++ nimmt man aus Performancegründen for .

volkard

Nexus schrieb:

Aber in Haskell nimmt man aus Performancegründen zipWith und tail , und in C++ nimmt man aus Performancegründen for .

Man staunt, was sich die Haskell-Leute so basteln, um auf O(n) Zeit zu kommen.

fib 0 = 0
fib 1 = 1
fib n | even n         = f1 * (f1 + 2 * f2)
      | n `mod` 4 == 1 = (2 * f1 + f2) * (2 * f1 - f2) + 2
      | otherwise      = (2 * f1 + f2) * (2 * f1 - f2) - 2
   where k = n `div` 2
         f1 = fib k
         f2 = fib (k-1)

oder

fibs = scanl (+) 0 (1:fibs)
fibs = 0 : scanl (+) 1 fibs

oder

fibs = fix (scanl (+) 0 . (1:))
fibs = fix ((0:) . scanl (+) 1)

oder

fibs = unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1)

oder

fibs = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)

oder

import Control.Monad.State
fib :: Integer -> Integer
fib n = flip evalState (0,1) $ do
  forM (xrange n) $ \_ -> do
    (a,b) <- get
    put (b,a+b)
  (a,b) <- get
  return a 

xrange n = [0..(n-1)]

Da läuft doch was schief! Wobei ich nicht behaupten will, bei C++ liefe nicht auch was schief.

Mr. N

fib n = fib' n     0       1 1
  where fib' total current a _ | total == current = a
        fib' total current a b                    = fib' total (current + 1) b (a + b)

Um die iterative Version mal klassisch und ohne Control.Monad.State in die tail-rekursive Form zu übersetzen.

Und wieso ist es nun ein Problem, dass man in Haskell mehrere Lösungen für ein Problem finden kann?

Wenn bei Haskell und C++ "etwas schief läuft", wo läuft es dann nicht schief?

Mr. N

Und weils so schön ist, zipWith in C++:

using std::vector;
using boost::result_of;

template<typename F, typename T1, typename T2>
vector<typename result_of<F(T1,T2)>::type>
zipWith(F f, vector<T1> const &a, vector<T2> const &b) {
  vector<typename result_of<F(T1,T2)>::type> res;
  vector<T1>::const_iterator itA = a.begin();
  vector<T2>::const_iterator itB = b.begin();
  for (; itA != a.end() && itB != b.end(); ++itA, ++itB)
    res.push_back(f(*itA, *itB));
  return res;
}

knivil

Mr. N schrieb:

(define (sum xs) (fold-left + 0 xs))

In Scheme bzw. Srfi-1 gibt es nur fold und entspricht deinem fold-left.

volkard schrieb:

Ich bevorzuge da Sachen, die weniger abstrakt als Rekursion sind.
summe=0
foreach i in xs
  summe+=i

Und schwubs hat man vergessen die Summe zu initialisieren. Diese Variante hat aber auch weitere Nachteile. Kannst du allein mit diesen Zeilen beweisen, dass es das gleiche wie ist

(as,bs) = split xs
summe1=0
foreach i in as
  summe1 += i

summe2=0
foreach i in bs
  summe2 += i

summe = summe1 + summe2

Wahrscheinlich, da es ein einfacher Fall ist. (Dieses Beispiel zielt auf Parallelitaet ab).

Auf die iterative Version bin ich nur darauf gekommen, weil ich es in Tabellenform auf Papier gebracht habe.

Man kann sie auch herleiten, siehe Funktionale Programmierung.: Sprachdesign und Programmiertechnik. Auch sind die expliziten Zuweisungen in der C-Variante ueberfluessig.

Ich find die Version, die Volkard gepostet habe, am leichtesten

Auch nur weil du damit gross geworden bist.

fibi = let next n m = (n+m) : (next m (n+m)) in 0:1:(next 0 1)

Meine bevorzugte Variant, da es unfold nicht direkt gibt, bzw. mit diesem unschoenen Maybe dazwischen. Nachteilhaft ist die explizite Rekursion. Sie ist die iterate-Variante.

Zeus

knivil schrieb:

Auf die iterative Version bin ich nur darauf gekommen, weil ich es in Tabellenform auf Papier gebracht habe.

Man kann sie auch herleiten, siehe Funktionale Programmierung.: Sprachdesign und Programmiertechnik. Auch sind die expliziten Zuweisungen in der C-Variante ueberfluessig.

Hab ich das nicht getan?

knivil schrieb:

Ich find die Version, die Volkard gepostet habe, am leichtesten

Auch nur weil du damit gross geworden bist.

Ich bin mit imperativen Programmiersprachen groß geworden und finde Volker's Rekursive Definition am besten! Was willst du mir mit dein Kommentar sagen, dass du mich nicht verstanden hast? Ich weiss es nicht!!