Bilişim çalışıyorumAckermann(4,1)ve farklı diller/Derleyiciler arasında performans olarak büyük bir fark var. Aşağıda benim sonuçlarıİ7 3820QM, 16 G, çekirdek 12.10 64 bit Ubuntu,

C: s 1.6, 12**(gcc 4.7.2)

int ack(int m, int n) {
  if (m == 0) return n 1;
  if (n == 0) return ack(m-1, 1);
  return ack(m-1, ack(m, n-1));
}

int main() {
  printf("%d\n", ack(4,1));
  return 0;
}

Bunun: s 3.6, 14**(bunun 3.12.1)

let rec ack = function
  | 0,n -> n 1
  | m,0 -> ack (m-1, 1)
  | m,n -> ack (m-1, ack (m, n-1))
in print_int (ack (4, 1))

Standart ML: s 5.1mlton -codegen c -cc-opt -O3(mlton 20100608 ile)

fun ack 0 n = n 1
  | ack m 0 = ack (m-1) 1
  | ack m n = ack (m-1) (ack m (n-1));
print (Int.toString (ack 4 1));

Raket: s 11.5racket(raket v5.3.3)

(require racket/unsafe/ops)

(define   unsafe-fx )
(define - unsafe-fx-)
(define (ack m n)
  (cond
    [(zero? m) (  n 1)]
    [(zero? n) (ack (- m 1) 1)]
    [else (ack (- m 1) (ack m (- n 1)))]))

(time (ack 4 1))

Haskell: bitmemiş, 22 ghc -O2 sonra sistem tarafından öldürüldü(dzd 7.4.2)

Haskell: s 1.8ajhc(ajhc 0.8.0.4 ile)

main = print $ ack 4 1
  where ack :: Int -> Int -> Int
        ack 0 n = n 1
        ack m 0 = ack (m-1) 1
        ack m n = ack (m-1) (ack m (n-1))

Haskell sürümü çok fazla bellek alır çünkü düzgün bir şekilde sonlandırmak için başarısız sadece bir tanesidir. Benim makine donuyor ve öldürülmeden önce takas alanı doldurur. Ben ağır kodu fuglifying olmadan bunu geliştirmek için ne yapabilirim?

EDİT: Çözümleri akıllı sınıfları ve bazı takdir ediyorum, ama senden istediğim şey tam olarak değil. Bu oldukça verimli bir şekilde (yığın, kuyruk çağrıları, kutulama, vb.) derleyici belirli bir desen işleme olup olmadığını görmek daha kolaydır daha ackermann işlevi bilgisayar.

2 DÜZENLEYİN: Çeşitli tepkiler belirttiği gibi, bu a bug in recent versions of GHC gibi görünüyor. Ben AJHC ile aynı kodu deneyin ve çok daha iyi performans elde.

Çok teşekkür ederim :)

NB:Yüksek bellek kullanımı sorunu yığını üzerinde yeni yığınlarının taşması ve ayırma yığını üzerine çöp toplama olup olmadığını kontrol değil nerede, 35**,. Zaten DZD BAŞ giderilmiştir.

CPS-dönüştürme ack çok daha iyi performans elde edebildim:

module Main where

data P = P !Int !Int

main :: IO ()
main = print $ ack (P 4 1) id
  where
    ack :: P -> (Int -> Int) -> Int
    ack (P 0 n) k = k (n   1)
    ack (P m 0) k = ack (P (m-1) 1) k
    ack (P m n) k = ack (P m (n-1)) (\a -> ack (P (m-1) a) k)

Özgün işlevi, bu bir sabit uzayda çalışırken benim makinede kullanılabilir tüm bellek tüketir.

$ time ./Test
65533
./Test  52,47s user 0,50s system 96% cpu 54,797 total

Bunun hala daha hızlı, ancak:

$ time ./test
65533./test  7,97s user 0,05s system 94% cpu 8,475 total

Düzenleme:JHC orijinal programı ile derlenmiş gibi hızlı Bunun versiyonu olarak: yaklaşık

$ time ./hs.out 
65533
./hs.out  5,31s user 0,03s system 96% cpu 5,515 total

Edit 2:Keşfettiğim bir şey daha: yığın yığın daha büyük bir boyutu ile orijinal programınızı ( RTS -kc1M) çalışan sabit alanda çalışmasını sağlar. CPS sürümü hala biraz daha hızlı ama.

Edit 3:Yaklaşık olarak hızlı Bunun bir şekilde el ile ana döngü çözümü ile çalışan bir versiyonunu üretmeyi başardı. Ancak, sadece RTS -kc1M (Dan bu davranış hakkında 37* *Doel) ile çalıştırdığınızda çalışır:

{-# LANGUAGE CPP #-}
module Main where

data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !Int

ack0 :: Int -> Int
ack0 n =(n 1)

#define C(a) a
#define CONCAT(a,b) C(a)C(b)

#define AckType(M) CONCAT(ack,M) :: Int -> Int

AckType(1)
AckType(2)
AckType(3)
AckType(4)

#define AckDecl(M,M1) \
CONCAT(ack,M) n = case n of { 0 -> CONCAT(ack,M1) 1 \
; 1 ->  CONCAT(ack,M1) (CONCAT(ack,M1) 1) \
; _ ->  CONCAT(ack,M1) (CONCAT(ack,M) (n-1)) }

AckDecl(1,0)
AckDecl(2,1)
AckDecl(3,2)
AckDecl(4,3)

ack :: P -> (Int -> Int) -> Int
ack (P m n) k = case m of
  0 -> k (ack0 n)
  1 -> k (ack1 n)
  2 -> k (ack2 n)
  3 -> k (ack3 n)
  4 -> k (ack4 n)
  _ -> case n of
    0 -> ack (P (m-1) 1) k
    1 -> ack (P (m-1) 1) (\a -> ack (P (m-1) a) k)
    _ -> ack (P m (n-1)) (\a -> ack (P (m-1) a) k)

main :: IO ()
main = print $ ack (P 4 1) id

Test:

$ time ./Test  RTS -kc1M
65533
./Test  RTS -kc1M  6,30s user 0,04s system 97% cpu 6,516 total

4 düzenleyinGörünüşe göre, uzay sızıntısı RTS -kc1M gelecekte gerekli olmayacak yani 38**,.