Ve C (kesinlikle değil) en uygun benim uygulamaları, Python, Erlang ve Haskell karşılaştırın egzersiz için bir programlama olarak Project Euler 51 *almış. Biraz daha yüksek yürütme kez elde etmek için, ben asıl sorun belirtildiği gibi 500 yerine 1000'den fazla bölenlerine ile ilk üçgeni sayısı için arama.

Sonuç şudur:

C:

lorenzo@enzo:~/erlang$ gcc -lm -o euler12.bin euler12.c
lorenzo@enzo:~/erlang$ time ./euler12.bin
842161320

real    0m11.074s
user    0m11.070s
sys 0m0.000s

python:

lorenzo@enzo:~/erlang$ time ./euler12.py 
842161320

real    1m16.632s
user    1m16.370s
sys 0m0.250s

pypy ile python:

lorenzo@enzo:~/Downloads/pypy-c-jit-43780-b590cf6de419-linux64/bin$ time ./pypy /home/lorenzo/erlang/euler12.py 
842161320

real    0m13.082s
user    0m13.050s
sys 0m0.020s

eğer x:

lorenzo@enzo:~/erlang$ erlc euler12.erl 
lorenzo@enzo:~/erlang$ time erl -s euler12 solve
Erlang R13B03 (erts-5.7.4) [source] [64-bit] [smp:4:4] [rq:4] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.4  (abort with ^G)
1> 842161320

real    0m48.259s
user    0m48.070s
sys 0m0.020s

haskell:

lorenzo@enzo:~/erlang$ ghc euler12.hs -o euler12.hsx
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12.hsx ...
lorenzo@enzo:~/erlang$ time ./euler12.hsx 
842161320

real    2m37.326s
user    2m37.240s
sys 0m0.080s

Özet:

• C: 100%
• python: 692% (pypy ile 118%)
• eğer x: 436% (RichardC 135% teşekkürler)
• haskell: 1421%

C diğer üç gibi hesaplamalar için uzun ve rasgele uzunluk tamsayı kullanır gibi büyük bir avantajı var sanırım. Ayrıca bir ilk çalışma zamanı (Diğerleri?) yüklemeye gerek yok.

Soru 1: Eğer x, Python ve Haskell keyfi uzunluğu tamsayı kullanarak hız nedeniyle kaybetmek veya onlar değerleri MAXINT daha az olduğu sürece, değil mi?

Soru 2: Haskell neden bu kadar yavaş? Frenler devre dışı bırakan bir derleyici bayrağı var ya da benim uygulama mı? (İkincisi Haskell yedi mühürler ile bir kitap olduğundan oldukça muhtemel bana.)

Soru 3: Bana yolu değiştirmeden bu uygulamaları optimize etmek için nasıl bazı ipuçları sunmak istiyorum faktörleri tespit edebilir misiniz? Herhangi bir şekilde iyileştirme: daha iyi, daha hızlı, daha "yerli" dili.

DÜZENLEME:

Soru 4: İşlevsel uygulamaları benim LCO (son çağrı optimizasyon, bir izin verin.k.kuyruk özyineleme bir eleme) ve çağrı yığını üzerine gereksiz çerçeveler ekleyerek önlemek? dolayısıyla

Gerçekten benim Haskell ve Ayrık bilgi çok sınırlı olduğunu itiraf etmeliyim rağmen aynı algoritma mümkün olduğunca benzer uygulamak için dört dilde çalıştı.

Kaynak kodları kullanılır:

#include <stdio.h>
#include <math.h>

int factorCount (long n)
{
    double square = sqrt (n);
    int isquare = (int) square;
    int count = isquare == square ? -1 : 0;
    long candidate;
    for (candidate = 1; candidate <= isquare; candidate   )
        if (0 == n % candidate) count  = 2;
    return count;
}

int main ()
{
    long triangle = 1;
    int index = 1;
    while (factorCount (triangle) < 1001)
    {
        index   ;
        triangle  = index;
    }
    printf ("%ld\n", triangle);
}

#! /usr/bin/env python3.2

import math

def factorCount (n):
    square = math.sqrt (n)
    isquare = int (square)
    count = -1 if isquare == square else 0
    for candidate in range (1, isquare   1):
        if not n % candidate: count  = 2
    return count

triangle = 1
index = 1
while factorCount (triangle) < 1001:
    index  = 1
    triangle  = index

print (triangle)

-module (euler12).
-compile (export_all).

factorCount (Number) -> factorCount (Number, math:sqrt (Number), 1, 0).

factorCount (_, Sqrt, Candidate, Count) when Candidate > Sqrt -> Count;

factorCount (_, Sqrt, Candidate, Count) when Candidate == Sqrt -> Count   1;

factorCount (Number, Sqrt, Candidate, Count) ->
    case Number rem Candidate of
        0 -> factorCount (Number, Sqrt, Candidate   1, Count   2);
        _ -> factorCount (Number, Sqrt, Candidate   1, Count)
    end.

nextTriangle (Index, Triangle) ->
    Count = factorCount (Triangle),
    if
        Count > 1000 -> Triangle;
        true -> nextTriangle (Index   1, Triangle   Index   1)  
    end.

solve () ->
    io:format ("~p~n", [nextTriangle (1, 1) ] ),
    halt (0).

factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
    where square = sqrt $ fromIntegral number
          isquare = floor square

factorCount' number sqrt candidate count
    | fromIntegral candidate > sqrt = count
    | number `mod` candidate == 0 = factorCount' number sqrt (candidate   1) (count   2)
    | otherwise = factorCount' number sqrt (candidate   1) count

nextTriangle index triangle
    | factorCount triangle > 1000 = triangle
    | otherwise = nextTriangle (index   1) (triangle   index   1)

main = print $ nextTriangle 1 1

GHC 7.0.3, gcc 4.4.6, Linux 2.6.29 x86_64 Core2 Duo (2.5 GHz) makine, Haskell için ghc -O2 -fllvm -fforce-recomp kullanarak derleme kullanarak ve gcc -O3 -lm C. için

• C rutin 8.4 saniye daha hızlı muhtemelen -O3 çünkü sizin çalıştırmak daha) çalışır
• Haskell çözüm 36 saniye (-O2 bayrağı nedeniyle) çalışır
• factorCount' kodunuzu açıkça yazılan ve Integer (burada benim yanlış tanı düzeltmek için Daniel için teşekkürler!) varsaymak değil. Açık tür bir imza zaten standart bir uygulamadır) Int ve zamanı kullanma vererek değiştirir11.1 saniye
• factorCount' gereksiz fromIntegral denir. Bir düzeltme herhangi bir değişiklik olsa (derleyici akıllı, sizin için şanslı) sonuçları.
• rem daha hızlı ve yeterli olduğu mod kullanılır. Bu zaman değişir8.5 saniye.
• factorCount' sürekli asla değişmeyen iki ekstra argümanlar(, *number*37)uygulama. İşçi/kapsayıcı bir dönüşümü bize verir:

 $ time ./so
 842161320  

 real    0m7.954s  
 user    0m7.944s  
 sys     0m0.004s  

- İşte bu doğru7.95 saniye. Sürekliyarım saniye daha hızlı C çözüm daha. -fllvm bayrak olmadan hala NCG arka uç, bu durumda iyi de yapıyor 8.182 seconds, alıyorum.

Sonuç: Haskell harika.

Kod Sonuç

factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
    where square = sqrt $ fromIntegral number
          isquare = floor square

factorCount' :: Int -> Int -> Int -> Int -> Int
factorCount' number sqrt candidate0 count0 = go candidate0 count0
  where
  go candidate count
    | candidate > sqrt = count
    | number `rem` candidate == 0 = go (candidate   1) (count   2)
    | otherwise = go (candidate   1) count

nextTriangle index triangle
    | factorCount triangle > 1000 = triangle
    | otherwise = nextTriangle (index   1) (triangle   index   1)

main = print $ nextTriangle 1 1

EDİT: soruları sağlayan keşfettiğimiz, bu Yüzden şimdi

Soru 1: kullanması nedeniyle hız kaybetmeden ayrık, python ve haskell Yap keyfi uzunluğu tamsayı veya yok değerini düşük olduğu sürece MAXİNT daha?

Haskell, Integer Int daha yavaş ama ne kadar yavaş hesaplamaları gerçekleştirilen bağlıdır. Neyse ki (64 bit makineler için) Int yeterlidir. Taşınabilirlik uğruna büyük ihtimal Şifremi Int64 Word64 (C long bir tek dil değil) kullanmak için yeniden yazın.

Soru 2: haskell Neden bu kadar yavaş? Yok derleyici bir bayrak o kapatır frenler ya da benim uygulama mı? (İkincisi oldukça haskell gibi muhtemel bana yedi mühürler ile bir kitap.)

Soru 3: bana bu optimize etmek için nasıl bazı ipuçları sunabilir misin faktörleri saptamak şekilde değiştirmeden uygulamaları? Herhangi bir şekilde iyileştirme: daha iyi, daha hızlı, daha "yerli" dili.

Yukarıda ben cevap ne olduğunu. Cevap oldu

• 0) -O2) Kullanımı optimizasyonu
• 1) mümkün olduğunca hızlı bir şekilde:-mümkün ciltsiz) türleri Kullanın
• 2) rem mod (sık unutulan bir optimizasyon) ve
• 3) işçi/sarıcı dönüşümü (belki de en yaygın optimizasyonu).

Soru 4: işlevsel benim uygulamaları LCO ve dolayısıyla izin çağrı yığını üzerine gereksiz çerçeveler ekleyerek önlemek?

Evet, sorun o değildi. İyi iş ve iyi ki bu kabul.