1. Куча / Говнокод #13543

    +125

    1. 1
    2. 2
    3. 3
    4. 4
    5. 5
    6. 6
    7. 7
    8. 8
    : %fib
        ( left right count limit -- result )
        2dup u<= if 2drop swap drop exit then
        1+ 2swap tuck + 2swap recurse ;
    
    : fib
        ( n -- n )
        1 2 0 -rot 2swap %fib ;

    Где там ForthGovno?

    Запостил: wvxvw, 03 Августа 2013

    Комментарии (17) RSS

    • показать все, что скрытоДля стекового языка нормальный код.
      Ответить
      • показать все, что скрытоЯ когда второе "слово" написал, понял, что в первом расставил аргументы в неправильном порядке, но вспоминая, как мучительно долго я к этому порядку шел, решил оставить как есть :)
        Ответить
      • показать все, что скрытоРекурсивный фибоначчи - говно на любом языке (ну, видимо кроме мемоизирующих).
        Ответить
        • показать все, что скрытоС хвостовой рекурсией тоже вполне норм.
          Ответить
        • показать все, что скрытоКому-то вообще приходилось их вычислять на практике? Числа Фибоначчи, конечно, встречаются часто, но напрямую их вычислять вроде редко нужно (разве что на project euler).
          Фибоначчиевы кучи не требуют вычисления чисел в рантайме, числа используются только при анализе. Да и вообще эти кучи используются редко, ибо сливают pairing heaps.
          Быть может, при написании аллокаторов кто-то использовал... Есть у кого примеры?
          Ответить
    • показать все, что скрытоNon legitur, graecum est.
      Ответить
      • показать все, что скрыто
        function dup2(args) {
            return args.push(args[args.length - 2], args[args.length - 2]);
        }
        
        function leq(args) {
            args[args.length - 2] = args[args.length - 2] <= args[args.length - 2];
            args.length--;
            return args;
        }
        
        function drop(args) {
            args.length--;
            return args;
        }
        
        function drop2(args) {
            return drop(drop(args));
        }
        
        function swap(args) {
            var temp = args[args.length - 1];
            args[args.length - 1] = args[args.length - 2];
            args[args.length - 2] = temp;
            return args;
        }
        
        function swap2(args) {
            var temp = args[0];
            args[0] = args[args.length - 2];
            args[args.length - 2] = temp;
            temp = args[1];
            args[1] = args[args.length - 1];
            args[args.length - 1] = temp;
            return args;
        }
        
        function oneplus(args) {
            args[args.length - 1]++;
            return args;
        }
        
        function plus(args) {
            args[args.length - 2] = args[args.length - 1] +  args[args.length - 2];
            return drop(args);
        }
        
        function tuck(args) {
            args[args.length] = args[args.length - 1];
            args[args.length - 2] = args[args.length - 3];
            args[args.length - 3] = args[args.length - 1];
            return args;
        }
        
        function _fib(args) {
            if (leq(dup2(args))) {
                return drop(swap(drop2(args)));
            }
            return _fib(swap2(plus(tuck(swap2(oneplus(args))))));
        }

        Это более менее описывает происходящее (не тестировал).
        Ответить
    • Говно. И дело не только в ракурсии.
      Во-первих именование, что значит "%"? Вспомогательные слова принято называть (вот-так).
      Во-вторых, стековый комментарий располагается на той же строчке, где и начало опеделения, через 2 пробела, а ещё он не соответствует реальным параметрам, что только запутывает: у первого слова должно быть ( left right limit count -- result ), слова работают с беззнаковыми числами, поэтому у второго должно быть ( u1 -- u2 ), а не n (это значит знаковое).
      В-третьих много лишних и бесполезных действий: SWAP DROP — это NIP , 1 2 0 -ROT — это 0 1 2.
      Вот исправленная версия:
      http://ideone.com/NK9ydn
      : (fib)  ( prevprev prev count -- u )
             ?DUP
             IF  >R TUCK + R> 1- RECURSE
             ELSE  NIP
             THEN ;
           
          : fib  ( u1 -- u2 )  0 1 ROT (fib) ;
           
          : .fibs  ( u -- )
             0 ?DO
               I fib .
             LOOP ;
           
          10 .fibs
      Или с локалками, если тяжело вращать в голове стек:
      http://ideone.com/TyW0If
      : (fib)  { prevprev prev count -- u }
         count
         IF  prev prevprev prev + count 1- RECURSE
         ELSE  prev
         THEN ;
       
      : fib  { u1 -- u2 }  0 1 u1 (fib) ;
      Но вообще на императивном языке лучше писать императивно:
      http://ideone.com/qrTUo5
      : fib  ( u1 -- u2 )
         0 1 ROT
         0 ?DO
           TUCK +
         LOOP
         NIP ;
      Ответить

    Добавить комментарий