Perbandingan kecepatan dengan Project Euler: C vs Python vs Erlang vs Haskell

Saya telah mengambil Soal # 12 dari Project Euler sebagai latihan pemrograman dan untuk membandingkan implementasi (pasti tidak optimal) saya dalam C, Python, Erlang dan Haskell. Untuk mendapatkan waktu eksekusi yang lebih tinggi, saya mencari nomor segitiga pertama dengan lebih dari 1000 pembagi daripada 500 seperti yang dinyatakan dalam masalah asli.

Hasilnya adalah sebagai berikut:

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

Python dengan PyPy:

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

Erlang:

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

Ringkasan:

• C: 100%
• Python: 692% (118% dengan PyPy)
• Erlang: 436% (135% terima kasih untuk RichardC)
• Haskell: 1421%

Saya mengira bahwa C memiliki keuntungan besar karena menggunakan panjang untuk perhitungan dan bukan bilangan bulat panjang sewenang-wenang seperti tiga lainnya. Juga tidak perlu memuat runtime terlebih dahulu (Lakukan yang lain?).

Pertanyaan 1: Apakah Erlang, Python dan Haskell kehilangan kecepatan karena menggunakan bilangan bulat panjang sewenang-wenang atau tidak mereka asalkan nilainya kurang dari MAXINT?

Pertanyaan 2: Mengapa Haskell begitu lambat? Apakah ada flag compiler yang mematikan rem atau implementasi saya? (Yang terakhir sangat mungkin karena Haskell adalah buku dengan tujuh meterai bagi saya.)

Pertanyaan 3: Dapatkah Anda menawarkan saya beberapa petunjuk bagaimana mengoptimalkan implementasi ini tanpa mengubah cara saya menentukan faktor-faktornya? Optimalisasi dengan cara apa pun: lebih baik, lebih cepat, lebih "asli" ke bahasa.

EDIT:

Pertanyaan 4: Apakah implementasi fungsional saya memungkinkan LCO (optimasi panggilan terakhir, alias penghapusan rekursi ekor) dan karenanya menghindari menambahkan frame yang tidak perlu ke tumpukan panggilan?

Saya benar-benar mencoba menerapkan algoritma yang sama dengan semirip mungkin dalam empat bahasa, meskipun saya harus mengakui bahwa pengetahuan Haskell dan Erlang saya sangat terbatas.

Kode sumber yang digunakan:

#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

Menggunakan GHC 7.0.3, gcc 4.4.6, Linux 2.6.29pada x86_64 Core2 Duo (2.5GHz) mesin, kompilasi menggunakan ghc -O2 -fllvm -fforce-recompuntuk Haskell dan gcc -O3 -lmuntuk C.

• Rutin C Anda berjalan dalam 8,4 detik (lebih cepat dari yang mungkin karena -O3)
• Solusi Haskell berjalan dalam 36 detik (karena -O2bendera)
• factorCount'Kode Anda tidak secara eksplisit diketik dan default ke Integer(terima kasih kepada Daniel untuk memperbaiki kesalahan diagnosis saya di sini!). Memberikan tanda tangan jenis eksplisit (yang merupakan praktik standar) menggunakan Intdan waktu berubah menjadi 11,1 detik
• di dalam factorCount'kamu telah memanggil sia-sia fromIntegral. Perbaikan menghasilkan tidak ada perubahan sekalipun (kompiler pintar, beruntung untuk Anda).
• Anda menggunakan modtempat remyang lebih cepat dan memadai. Ini mengubah waktu menjadi 8,5 detik .
• factorCount'terus menerapkan dua argumen tambahan yang tidak pernah berubah ( number, sqrt). Transformasi pekerja / pembungkus memberi kita:

 $ time ./so
 842161320  

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

Benar, 7,95 detik . Secara konsisten setengah detik lebih cepat dari solusi C . Tanpa -fllvmbendera saya masih mendapatkan 8.182 seconds, jadi backend NCG baik dalam kasus ini juga.

Kesimpulan: Haskell luar biasa.

Kode yang dihasilkan

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

EDIT: Jadi sekarang kita sudah menjelajahi itu, mari kita jawab pertanyaannya

Pertanyaan 1: Apakah erlang, python dan haskell kehilangan kecepatan karena menggunakan bilangan bulat panjang arbitrer atau tidak asalkan nilainya kurang dari MAXINT?

Di Haskell, menggunakan Integerlebih lambat daripada Inttetapi berapa banyak lebih lambat tergantung pada perhitungan yang dilakukan. Untungnya (untuk mesin 64 bit) Intsudah cukup. Demi portabilitas, Anda mungkin harus menulis ulang kode saya untuk digunakan Int64atau Word64(C bukan satu-satunya bahasa dengan a long).

Pertanyaan 2: Mengapa haskell sangat lambat? Apakah ada flag compiler yang mematikan rem atau implementasi saya? (Yang terakhir sangat mungkin karena haskell adalah buku dengan tujuh meterai bagi saya.)

Pertanyaan 3: Dapatkah Anda menawarkan saya beberapa petunjuk bagaimana mengoptimalkan implementasi ini tanpa mengubah cara saya menentukan faktor-faktornya? Optimalisasi dengan cara apa pun: lebih baik, lebih cepat, lebih "asli" ke bahasa.

Itulah yang saya jawab di atas. Jawabannya adalah

• 0) Gunakan optimasi via -O2
• 1) Gunakan jenis yang cepat (terutama: tidak mampu kotak) bila memungkinkan
• 2) remtidak mod(optimasi yang sering dilupakan) dan
• 3) transformasi pekerja / pembungkus (mungkin optimasi yang paling umum).

Pertanyaan 4: Apakah implementasi fungsional saya mengizinkan LCO dan karenanya menghindari menambahkan frame yang tidak perlu ke dalam tumpukan panggilan?

Ya, bukan itu masalahnya. Kerja bagus dan senang Anda menganggap ini.

Ada beberapa masalah dengan implementasi Erlang. Sebagai garis dasar untuk yang berikut ini, waktu eksekusi terukur saya untuk program Erlang Anda yang tidak dimodifikasi adalah 47,6 detik, dibandingkan dengan 12,7 detik untuk kode C.

Hal pertama yang harus Anda lakukan jika Anda ingin menjalankan kode Erlang intensif komputasi adalah menggunakan kode asli. Kompilasi dengan erlc +native euler12mendapat waktu ke 41,3 detik. Namun ini adalah speedup yang jauh lebih rendah (hanya 15%) dari yang diharapkan dari kompilasi asli pada kode semacam ini, dan masalahnya adalah penggunaan Anda -compile(export_all). Ini berguna untuk eksperimen, tetapi fakta bahwa semua fungsi berpotensi dapat dijangkau dari luar menyebabkan kompiler asli menjadi sangat konservatif. (Emulator BEAM normal tidak terlalu terpengaruh.) Mengganti deklarasi ini dengan -export([solve/0]).memberikan speedup yang jauh lebih baik: 31,5 detik (hampir 35% dari baseline).

Tetapi kode itu sendiri memiliki masalah: untuk setiap iterasi dalam loop factorCount, Anda melakukan tes ini:

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

Kode C tidak melakukan ini. Secara umum, mungkin sulit untuk membuat perbandingan yang adil antara implementasi berbeda dari kode yang sama, dan khususnya jika algoritma ini numerik, karena Anda perlu memastikan bahwa mereka benar-benar melakukan hal yang sama. Kesalahan pembulatan sedikit dalam satu implementasi karena beberapa typecast di suatu tempat dapat menyebabkannya melakukan lebih banyak iterasi daripada yang lain meskipun keduanya akhirnya mencapai hasil yang sama.

Untuk menghilangkan kemungkinan sumber kesalahan ini (dan menyingkirkan tes tambahan di setiap iterasi), saya menulis ulang fungsi factorCount sebagai berikut, dimodelkan dengan cermat pada kode C:

factorCount (N) ->
    Sqrt = math:sqrt (N),
    ISqrt = trunc(Sqrt),
    if ISqrt == Sqrt -> factorCount (N, ISqrt, 1, -1);
       true          -> factorCount (N, ISqrt, 1, 0)
    end.

factorCount (_N, ISqrt, Candidate, Count) when Candidate > ISqrt -> Count;
factorCount ( N, ISqrt, Candidate, Count) ->
    case N rem Candidate of
        0 -> factorCount (N, ISqrt, Candidate + 1, Count + 2);
        _ -> factorCount (N, ISqrt, Candidate + 1, Count)
    end.

Penulisan ulang ini, tidak export_all, dan kompilasi asli, memberi saya jangka waktu berikut:

$ erlc +native euler12.erl
$ time erl -noshell -s euler12 solve
842161320

real    0m19.468s
user    0m19.450s
sys 0m0.010s

yang tidak terlalu buruk dibandingkan dengan kode C:

$ time ./a.out 
842161320

real    0m12.755s
user    0m12.730s
sys 0m0.020s

mengingat bahwa Erlang sama sekali tidak diarahkan untuk menulis kode numerik, karena hanya 50% lebih lambat daripada C pada program seperti ini cukup bagus.

Akhirnya, mengenai pertanyaan Anda:

Pertanyaan 1: Apakah erlang, python dan haskell kehilangan kecepatan karena menggunakan bilangan bulat panjang sewenang-wenang atau tidak mereka asalkan nilainya kurang dari MAXINT?

Ya, agak. Di Erlang, tidak ada cara untuk mengatakan "gunakan aritmatika 32/64-bit dengan wrap-around", jadi kecuali jika kompiler dapat membuktikan beberapa batasan pada bilangan bulat Anda (dan biasanya tidak bisa), ia harus memeriksa semua perhitungan untuk melihat jika mereka dapat memuat satu kata yang ditandai atau jika harus mengubahnya menjadi bignum yang dialokasikan untuk tumpukan. Bahkan jika tidak ada bignum yang pernah digunakan dalam praktek saat runtime, pemeriksaan ini harus dilakukan. Di sisi lain, itu berarti Anda tahu bahwa algoritma tidak akan pernah gagal karena pembungkus integer yang tidak terduga jika Anda tiba-tiba memberikan input yang lebih besar daripada sebelumnya.

Pertanyaan 4: Apakah implementasi fungsional saya mengizinkan LCO dan karenanya menghindari menambahkan frame yang tidak perlu ke dalam tumpukan panggilan?

Ya, kode Erlang Anda sudah benar sehubungan dengan optimasi panggilan terakhir.

Sehubungan dengan optimasi Python, selain menggunakan PyPy (untuk percepatan yang cukup mengesankan dengan nol perubahan pada kode Anda), Anda bisa menggunakan toolchain terjemahan PyPy untuk mengkompilasi versi yang sesuai dengan RPython, atau Cython untuk membangun modul ekstensi, keduanya yang lebih cepat daripada versi C dalam pengujian saya, dengan modul Cython hampir dua kali lebih cepat . Untuk referensi saya menyertakan hasil benchmark C dan PyPy juga:

C (dikompilasi dengan gcc -O3 -lm)

% time ./euler12-c 
842161320

./euler12-c  11.95s 
 user 0.00s 
 system 99% 
 cpu 11.959 total

PyPy 1.5

% time pypy euler12.py
842161320
pypy euler12.py  
16.44s user 
0.01s system 
99% cpu 16.449 total

RPython (menggunakan revisi PyPy terbaru, c2f583445aee)

% time ./euler12-rpython-c
842161320
./euler12-rpy-c  
10.54s user 0.00s 
system 99% 
cpu 10.540 total

Cython 0.15

% time python euler12-cython.py
842161320
python euler12-cython.py  
6.27s user 0.00s 
system 99% 
cpu 6.274 total

Versi RPython memiliki beberapa perubahan utama. Untuk menerjemahkan ke dalam program mandiri, Anda perlu mendefinisikan Anda target, yang dalam hal ini adalah mainfungsinya. Itu diharapkan untuk menerima sys.argvkarena itu hanya argumen, dan diperlukan untuk mengembalikan int. Anda dapat menerjemahkannya dengan menggunakan translate.py, % translate.py euler12-rpython.pyyang diterjemahkan menjadi C dan mengkompilasinya untuk Anda.

# euler12-rpython.py

import math, sys

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

def main(argv):
    triangle = 1
    index = 1
    while factorCount(triangle) < 1001:
        index += 1
        triangle += index
    print triangle
    return 0

if __name__ == '__main__':
    main(sys.argv)

def target(*args):
    return main, None

Versi Cython ditulis ulang sebagai modul ekstensi _euler12.pyx, yang saya impor dan panggil dari file python normal. Pada _euler12.pyxdasarnya sama dengan versi Anda, dengan beberapa deklarasi tipe statis tambahan. Setup.py memiliki boilerplate normal untuk membangun ekstensi, menggunakan python setup.py build_ext --inplace.

# _euler12.pyx
from libc.math cimport sqrt

cdef int factorCount(int n):
    cdef int candidate, isquare, count
    cdef double square
    square = 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

cpdef main():
    cdef int triangle = 1, index = 1
    while factorCount(triangle) < 1001:
        index += 1
        triangle += index
    print triangle

# euler12-cython.py
import _euler12
_euler12.main()

# setup.py
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext

ext_modules = [Extension("_euler12", ["_euler12.pyx"])]

setup(
  name = 'Euler12-Cython',
  cmdclass = {'build_ext': build_ext},
  ext_modules = ext_modules
)

Jujur saya punya sedikit pengalaman dengan RPython atau Cython, dan terkejut dengan hasilnya. Jika Anda menggunakan CPython, menulis bit kode intensif CPU Anda dalam modul ekstensi Cython sepertinya cara yang sangat mudah untuk mengoptimalkan program Anda.

Pertanyaan 3: Dapatkah Anda menawarkan saya beberapa petunjuk bagaimana mengoptimalkan implementasi ini tanpa mengubah cara saya menentukan faktor-faktornya? Optimalisasi dengan cara apa pun: lebih baik, lebih cepat, lebih "asli" ke bahasa.

Implementasi C adalah suboptimal (seperti yang ditunjukkan oleh Thomas M. DuBuisson), versi menggunakan integer 64-bit (yaitu datatype panjang ). Saya akan menyelidiki daftar perakitan nanti, tetapi dengan tebakan yang berpendidikan, ada beberapa akses memori yang terjadi dalam kode yang dikompilasi, yang membuat penggunaan bilangan bulat 64-bit secara signifikan lebih lambat. Itu atau kode yang dihasilkan (baik itu fakta bahwa Anda dapat memasukkan int 64-bit kurang dalam register SSE atau bulat ganda ke integer 64-bit lebih lambat).

Berikut ini adalah kode yang dimodifikasi (cukup ganti panjang dengan int dan saya secara eksplisit menyebutkan faktorCount, meskipun saya tidak berpikir bahwa ini perlu dengan gcc -O3):

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

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

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

Running + timing memberikan:

$ gcc -O3 -lm -o euler12 euler12.c; time ./euler12
842161320
./euler12  2.95s user 0.00s system 99% cpu 2.956 total

Sebagai referensi, implementasi haskell oleh Thomas pada jawaban sebelumnya memberikan:

$ ghc -O2 -fllvm -fforce-recomp euler12.hs; time ./euler12                                                                                      [9:40]
[1 of 1] Compiling Main             ( euler12.hs, euler12.o )
Linking euler12 ...
842161320
./euler12  9.43s user 0.13s system 99% cpu 9.602 total

Kesimpulan: Mengambil apa pun dari ghc, kompiler yang hebat, tetapi gcc biasanya menghasilkan kode yang lebih cepat.

Lihatlah blog ini . Sekitar setahun terakhir ini dia telah melakukan beberapa masalah Project Euler di Haskell dan Python, dan dia umumnya menemukan Haskell jauh lebih cepat. Saya pikir antara bahasa-bahasa itu lebih berkaitan dengan kelancaran dan gaya pengkodean Anda.

Ketika datang ke kecepatan Python, Anda menggunakan implementasi yang salah! Coba PyPy , dan untuk hal-hal seperti ini Anda akan merasa jauh lebih cepat.

Implementasi Haskell Anda dapat dipercepat dengan menggunakan beberapa fungsi dari paket Haskell. Dalam hal ini saya menggunakan primes, yang baru saja diinstal dengan 'cabal install primes';)

import Data.Numbers.Primes
import Data.List

triangleNumbers = scanl1 (+) [1..]
nDivisors n = product $ map ((+1) . length) (group (primeFactors n))
answer = head $ filter ((> 500) . nDivisors) triangleNumbers

main :: IO ()
main = putStrLn $ "First triangle number to have over 500 divisors: " ++ (show answer)

Pengaturan waktu:

Program asli Anda:

PS> measure-command { bin\012_slow.exe }

TotalSeconds      : 16.3807409
TotalMilliseconds : 16380.7409

Peningkatan implementasi

PS> measure-command { bin\012.exe }

TotalSeconds      : 0.0383436
TotalMilliseconds : 38.3436

Seperti yang Anda lihat, ini berjalan dalam 38 milidetik pada mesin yang sama dengan yang Anda jalankan dalam 16 detik :)

Perintah kompilasi:

ghc -O2 012.hs -o bin\012.exe
ghc -O2 012_slow.hs -o bin\012_slow.exe

Hanya untuk bersenang-senang. Berikut ini adalah implementasi Haskell yang lebih 'asli':

import Control.Applicative
import Control.Monad
import Data.Either
import Math.NumberTheory.Powers.Squares

isInt :: RealFrac c => c -> Bool
isInt = (==) <$> id <*> fromInteger . round

intSqrt :: (Integral a) => a -> Int
--intSqrt = fromIntegral . floor . sqrt . fromIntegral
intSqrt = fromIntegral . integerSquareRoot'

factorize :: Int -> [Int]
factorize 1 = []
factorize n = first : factorize (quot n first)
  where first = (!! 0) $ [a | a <- [2..intSqrt n], rem n a == 0] ++ [n]

factorize2 :: Int -> [(Int,Int)]
factorize2 = foldl (\ls@((val,freq):xs) y -> if val == y then (val,freq+1):xs else (y,1):ls) [(0,0)] . factorize

numDivisors :: Int -> Int
numDivisors = foldl (\acc (_,y) -> acc * (y+1)) 1 <$> factorize2

nextTriangleNumber :: (Int,Int) -> (Int,Int)
nextTriangleNumber (n,acc) = (n+1,acc+n+1)

forward :: Int -> (Int, Int) -> Either (Int, Int) (Int, Int)
forward k val@(n,acc) = if numDivisors acc > k then Left val else Right (nextTriangleNumber val)

problem12 :: Int -> (Int, Int)
problem12 n = (!!0) . lefts . scanl (>>=) (forward n (1,1)) . repeat . forward $ n

main = do
  let (n,val) = problem12 1000
  print val

Menggunakan ghc -O3, ini secara konsisten berjalan dalam 0,55-0,58 detik pada mesin saya (1,73GHz Core i7).

Fungsi FactCount yang lebih efisien untuk versi C:

int factorCount (int n)
{
  int count = 1;
  int candidate,tmpCount;
  while (n % 2 == 0) {
    count++;
    n /= 2;
  }
    for (candidate = 3; candidate < n && candidate * candidate < n; candidate += 2)
    if (n % candidate == 0) {
      tmpCount = 1;
      do {
        tmpCount++;
        n /= candidate;
      } while (n % candidate == 0);
       count*=tmpCount;
      }
  if (n > 1)
    count *= 2;
  return count;
}

Mengubah rindu menjadi int, menggunakan gcc -O3 -lm, ini secara konsisten berjalan dalam 0,31-0,35 detik.

Keduanya dapat dibuat untuk berjalan lebih cepat jika Anda mengambil keuntungan dari kenyataan bahwa angka segitiga ke-n = n * (n + 1) / 2, dan n dan (n + 1) memiliki faktorisasi prima yang sama sekali berbeda, sehingga jumlah faktor dari masing-masing setengah dapat dikalikan untuk menemukan jumlah faktor keseluruhan. Pengikut:

int main ()
{
  int triangle = 0,count1,count2 = 1;
  do {
    count1 = count2;
    count2 = ++triangle % 2 == 0 ? factorCount(triangle+1) : factorCount((triangle+1)/2);
  } while (count1*count2 < 1001);
  printf ("%lld\n", ((long long)triangle)*(triangle+1)/2);
}

akan mengurangi waktu menjalankan kode c menjadi 0,17-0,19 detik, dan dapat menangani pencarian yang jauh lebih besar - lebih dari 10.000 faktor membutuhkan waktu sekitar 43 detik pada mesin saya. Saya meninggalkan speedup mirip haskell ke pembaca yang tertarik.

Pertanyaan 1: Apakah erlang, python dan haskell kehilangan kecepatan karena menggunakan bilangan bulat panjang sewenang-wenang atau tidak mereka asalkan nilainya kurang dari MAXINT?

Ini tidak mungkin. Saya tidak bisa mengatakan banyak tentang Erlang dan Haskell (well, mungkin sedikit tentang Haskell di bawah) tetapi saya bisa menunjukkan banyak kemacetan lainnya dengan Python. Setiap kali program mencoba untuk menjalankan operasi dengan beberapa nilai dalam Python, itu harus memverifikasi apakah nilai-nilai tersebut berasal dari tipe yang tepat, dan biayanya sedikit waktu. factorCountFungsi Anda hanya mengalokasikan daftar dengan range (1, isquare + 1)berbagai waktu, dan runtime, mallocalokasi memori -styled jauh lebih lambat daripada iterasi pada rentang dengan penghitung seperti yang Anda lakukan dalam C. Khususnya, factorCount()disebut beberapa kali dan karenanya mengalokasikan banyak daftar. Juga, jangan lupa bahwa Python ditafsirkan dan juru bahasa CPython tidak memiliki fokus besar untuk dioptimalkan.

EDIT : oh, well, saya perhatikan bahwa Anda menggunakan Python 3 jadi range()tidak mengembalikan daftar, tetapi generator. Dalam hal ini, poin saya tentang mengalokasikan daftar adalah setengah salah: fungsi hanya mengalokasikan rangeobjek, yang tidak efisien namun tidak seefisien mengalokasikan daftar dengan banyak item.

Pertanyaan 2: Mengapa haskell sangat lambat? Apakah ada flag compiler yang mematikan rem atau implementasi saya? (Yang terakhir sangat mungkin karena haskell adalah buku dengan tujuh meterai bagi saya.)

Apakah Anda menggunakan Pelukan ? Pelukan adalah penerjemah yang sangat lambat. Jika Anda menggunakannya, mungkin Anda bisa mendapatkan waktu yang lebih baik dengan GHC - tetapi saya hanya merenungkan hipotesis, jenis hal yang dilakukan oleh kompiler Haskell yang baik di bawah tenda cukup menarik dan jauh melampaui pemahaman saya :)

Pertanyaan 3: Dapatkah Anda menawarkan saya beberapa petunjuk bagaimana mengoptimalkan implementasi ini tanpa mengubah cara saya menentukan faktor-faktornya? Optimalisasi dengan cara apa pun: lebih baik, lebih cepat, lebih "asli" ke bahasa.

Saya akan mengatakan Anda memainkan game yang tidak lucu. Bagian terbaik dari mengetahui berbagai bahasa adalah menggunakannya dengan cara yang paling berbeda :) Tapi saya ngelantur, saya tidak punya rekomendasi untuk poin ini. Maaf, saya harap seseorang dapat membantu Anda dalam hal ini :)

Pertanyaan 4: Apakah implementasi fungsional saya mengizinkan LCO dan karenanya menghindari menambahkan frame yang tidak perlu ke dalam tumpukan panggilan?

Sejauh yang saya ingat, Anda hanya perlu memastikan bahwa panggilan rekursif Anda adalah perintah terakhir sebelum mengembalikan nilai. Dengan kata lain, fungsi seperti yang di bawah ini dapat menggunakan pengoptimalan tersebut:

def factorial(n, acc=1):
    if n > 1:
        acc = acc * n
        n = n - 1
        return factorial(n, acc)
    else:
        return acc

Namun, Anda tidak akan memiliki optimasi seperti itu jika fungsi Anda seperti di bawah ini, karena ada operasi (perkalian) setelah panggilan rekursif:

def factorial2(n):
    if n > 1:
        f = factorial2(n-1)
        return f*n
    else:
        return 1

Saya memisahkan operasi di beberapa variabel lokal untuk memperjelas operasi mana yang dijalankan. Namun, yang paling umum adalah melihat fungsi-fungsi ini seperti di bawah ini, tetapi mereka setara dengan poin yang saya buat:

def factorial(n, acc=1):
    if n > 1:
        return factorial(n-1, acc*n)
    else:
        return acc

def factorial2(n):
    if n > 1:
        return n*factorial(n-1)
    else:
        return 1

Perhatikan bahwa terserah kompiler / juru bahasa untuk memutuskan apakah akan membuat rekursi ekor. Sebagai contoh, interpreter Python tidak melakukannya jika saya ingat dengan baik (saya menggunakan Python dalam contoh saya hanya karena sintaksnya yang lancar). Lagi pula, jika Anda menemukan hal-hal aneh seperti fungsi faktorial dengan dua parameter (dan salah satu parameter memiliki nama seperti acc, accumulatordll.) Sekarang Anda tahu mengapa orang melakukannya :)

Dengan Haskell, Anda benar-benar tidak perlu berpikir dalam rekursi secara eksplisit.

factorCount number = foldr factorCount' 0 [1..isquare] -
                     (fromEnum $ square == fromIntegral isquare)
    where
      square = sqrt $ fromIntegral number
      isquare = floor square
      factorCount' candidate
        | number `rem` candidate == 0 = (2 +)
        | otherwise = id

triangles :: [Int]
triangles = scanl1 (+) [1,2..]

main = print . head $ dropWhile ((< 1001) . factorCount) triangles

Dalam kode di atas, saya telah mengganti rekursi eksplisit dalam jawaban @ Thomas dengan operasi daftar umum. Kode masih melakukan hal yang persis sama tanpa kita khawatir tentang rekursi ekor. Ini berjalan (~ 7.49s ) sekitar 6% lebih lambat dari versi dalam jawaban @ Thomas (~ 7.04s ) pada mesin saya dengan GHC 7.6.2, sedangkan versi C dari @Raedwulf berjalan ~ 3.15s . Tampaknya GHC telah meningkat dari tahun ke tahun.

PS. Saya tahu ini adalah pertanyaan lama, dan saya menemukannya dari pencarian google (saya lupa apa yang saya cari, sekarang ...). Hanya ingin mengomentari pertanyaan tentang LCO dan mengungkapkan perasaan saya tentang Haskell secara umum. Saya ingin mengomentari jawaban teratas, tetapi komentar tidak mengizinkan blok kode.

Beberapa angka lagi dan penjelasan untuk versi C. Rupanya tidak ada yang melakukannya selama bertahun-tahun. Ingatlah untuk meningkatkan jawaban ini sehingga dapat menjadi yang teratas bagi semua orang untuk melihat dan belajar.

Langkah Satu: Tolok ukur program penulis

Spesifikasi Laptop:

• CPU i3 M380 (931 MHz - mode hemat baterai maksimum)
• Memori 4GB
• Win7 64 bit
• Microsoft Visual Studio 2012 Ultimate
• Cygwin dengan gcc 4.9.3
• Python 2.7.10

Perintah:

compiling on VS x64 command prompt > `for /f %f in ('dir /b *.c') do cl /O2 /Ot /Ox %f -o %f_x64_vs2012.exe`
compiling on cygwin with gcc x64   > `for f in ./*.c; do gcc -m64 -O3 $f -o ${f}_x64_gcc.exe ; done`
time (unix tools) using cygwin > `for f in ./*.exe; do  echo "----------"; echo $f ; time $f ; done`

.

----------
$ time python ./original.py

real    2m17.748s
user    2m15.783s
sys     0m0.093s
----------
$ time ./original_x86_vs2012.exe

real    0m8.377s
user    0m0.015s
sys     0m0.000s
----------
$ time ./original_x64_vs2012.exe

real    0m8.408s
user    0m0.000s
sys     0m0.015s
----------
$ time ./original_x64_gcc.exe

real    0m20.951s
user    0m20.732s
sys     0m0.030s

Nama file adalah: integertype_architecture_compiler.exe

• integertype sama dengan program asli untuk saat ini (lebih lanjut tentang itu nanti)
• arsitektur x86 atau x64 tergantung pada pengaturan kompiler
• kompiler adalah gcc atau vs2012

Langkah Dua: Selidiki, Tingkatkan, dan Tolok Ukur Lagi

VS adalah 250% lebih cepat dari gcc. Kedua kompiler harus memberikan kecepatan yang sama. Jelas, ada yang salah dengan kode atau opsi kompilator. Mari selidiki!

Poin pertama yang menarik adalah tipe integer. Konversi dapat menjadi mahal dan konsistensi penting untuk menghasilkan & mengoptimalkan kode yang lebih baik. Semua bilangan bulat harus bertipe sama.

Ini berantakan intdan longsekarang. Kami akan memperbaikinya. Jenis apa yang digunakan? Tercepat. Harus benchmark mereka semua!

----------
$ time ./int_x86_vs2012.exe

real    0m8.440s
user    0m0.016s
sys     0m0.015s
----------
$ time ./int_x64_vs2012.exe

real    0m8.408s
user    0m0.016s
sys     0m0.015s
----------
$ time ./int32_x86_vs2012.exe

real    0m8.408s
user    0m0.000s
sys     0m0.015s
----------
$ time ./int32_x64_vs2012.exe

real    0m8.362s
user    0m0.000s
sys     0m0.015s
----------
$ time ./int64_x86_vs2012.exe

real    0m18.112s
user    0m0.000s
sys     0m0.015s
----------
$ time ./int64_x64_vs2012.exe

real    0m18.611s
user    0m0.000s
sys     0m0.015s
----------
$ time ./long_x86_vs2012.exe

real    0m8.393s
user    0m0.015s
sys     0m0.000s
----------
$ time ./long_x64_vs2012.exe

real    0m8.440s
user    0m0.000s
sys     0m0.015s
----------
$ time ./uint32_x86_vs2012.exe

real    0m8.362s
user    0m0.000s
sys     0m0.015s
----------
$ time ./uint32_x64_vs2012.exe

real    0m8.393s
user    0m0.015s
sys     0m0.015s
----------
$ time ./uint64_x86_vs2012.exe

real    0m15.428s
user    0m0.000s
sys     0m0.015s
----------
$ time ./uint64_x64_vs2012.exe

real    0m15.725s
user    0m0.015s
sys     0m0.015s
----------
$ time ./int_x64_gcc.exe

real    0m8.531s
user    0m8.329s
sys     0m0.015s
----------
$ time ./int32_x64_gcc.exe

real    0m8.471s
user    0m8.345s
sys     0m0.000s
----------
$ time ./int64_x64_gcc.exe

real    0m20.264s
user    0m20.186s
sys     0m0.015s
----------
$ time ./long_x64_gcc.exe

real    0m20.935s
user    0m20.809s
sys     0m0.015s
----------
$ time ./uint32_x64_gcc.exe

real    0m8.393s
user    0m8.346s
sys     0m0.015s
----------
$ time ./uint64_x64_gcc.exe

real    0m16.973s
user    0m16.879s
sys     0m0.030s

Jenis integer berasal int long int32_t uint32_t int64_tdan uint64_tdari#include <stdint.h>

Ada BANYAK jenis integer di C, ditambah beberapa yang ditandatangani / tidak ditandatangani untuk dimainkan, ditambah pilihan untuk mengkompilasi sebagai x86 atau x64 (jangan bingung dengan ukuran integer yang sebenarnya). Itu banyak versi untuk dikompilasi dan dijalankan ^^

Langkah Tiga: Memahami Angka

Kesimpulan pasti:

• Bilangan bulat 32 bit ~ 200% lebih cepat dari 64 bit setara
• unsigned 64 bit integers 25% lebih cepat dari 64 bit yang ditandatangani (Sayangnya, saya tidak punya penjelasan untuk itu)

Pertanyaan tipuan: "Berapa ukuran int dan panjang dalam C?"
Jawaban yang benar adalah: Ukuran int dan panjang dalam C tidak terdefinisi dengan baik!

Dari spesifikasi C:

int setidaknya 32 bit
adalah setidaknya int

Dari halaman manual gcc (flag -m32 dan -m64):

Lingkungan 32-bit menetapkan int, long dan pointer ke 32 bit dan menghasilkan kode yang berjalan pada sistem i386 apa pun.
Lingkungan 64-bit menetapkan int ke 32 bit dan panjang dan pointer ke 64 bit dan menghasilkan kode untuk arsitektur x86-64 AMD.

Dari dokumentasi MSDN (Rentang Tipe Data) https://msdn.microsoft.com/en-us/library/s3f49ktz%28v=vs.110%29.aspx :

int, 4 byte, juga dikenal sebagai masuk
panjang, 4 byte, juga tahu sebagai panjang int dan ditandatangani panjang int

Untuk Menyimpulkan Ini: Pelajaran Yang Dipetik

• Bilangan bulat 32 bit lebih cepat daripada bilangan bulat 64 bit.

• Jenis bilangan bulat standar tidak didefinisikan dengan baik dalam C atau C ++, mereka bervariasi tergantung pada kompiler dan arsitektur. Ketika Anda membutuhkan konsistensi dan prediktabilitas, gunakan uint32_tkeluarga integer dari #include <stdint.h>.

• Masalah kecepatan terpecahkan. Semua bahasa lain kembali ketinggalan ratusan persen, C & C ++ menang lagi! Mereka selalu melakukannya. Perbaikan selanjutnya akan multithreading menggunakan OpenMP: D

Melihat implementasi Erlang Anda. Waktunya sudah termasuk memulai dari seluruh mesin virtual, menjalankan program Anda dan menghentikan mesin virtual. Saya cukup yakin bahwa pengaturan dan penghentian erlang vm membutuhkan waktu.

Jika waktunya dilakukan di dalam mesin virtual erlang itu sendiri, hasilnya akan berbeda karena dalam kasus itu kami akan memiliki waktu yang sebenarnya untuk hanya program yang dimaksud. Kalau tidak, saya percaya bahwa total waktu yang dibutuhkan oleh proses memulai dan memuat Erlang Vm plus penghentian itu (seperti yang Anda masukkan ke dalam program Anda) semuanya termasuk dalam total waktu yang metode yang Anda gunakan untuk mengatur waktu program menghasilkan. Pertimbangkan untuk menggunakan erlang timing itu sendiri yang kami gunakan saat kami ingin mengatur waktu program kami di dalam mesin virtual itu sendiri timer:tc/1 or timer:tc/2 or timer:tc/3. Dengan cara ini, hasil dari erlang akan mengecualikan waktu yang dibutuhkan untuk memulai dan menghentikan / membunuh / menghentikan mesin virtual. Itulah alasan saya di sana, pikirkanlah, dan kemudian coba tanda bangku Anda lagi.

Saya sebenarnya menyarankan agar kami mencoba mengatur waktu program (untuk bahasa yang memiliki runtime), di dalam runtime bahasa tersebut untuk mendapatkan nilai yang tepat. C misalnya tidak memiliki overhead untuk memulai dan mematikan sistem runtime seperti halnya Erlang, Python dan Haskell (98% yakin akan hal ini - saya tahan koreksi). Jadi (berdasarkan alasan ini) saya menyimpulkan dengan mengatakan bahwa tolok ukur ini tidak tepat / cukup adil untuk bahasa yang berjalan di atas sistem runtime. Mari kita lakukan lagi dengan perubahan ini.

EDIT: selain itu bahkan jika semua bahasa memiliki sistem runtime, overhead memulai masing-masing dan menghentikannya akan berbeda. jadi saya sarankan kita waktu dari dalam sistem runtime (untuk bahasa yang ini berlaku). Erlang VM dikenal memiliki overhead yang cukup saat start up!

Pertanyaan 1: Apakah Erlang, Python dan Haskell kehilangan kecepatan karena menggunakan bilangan bulat panjang sewenang-wenang atau tidak asalkan nilainya kurang dari MAXINT?

Pertanyaan satu dapat dijawab dalam negatif untuk Erlang. Pertanyaan terakhir dijawab dengan menggunakan Erlang dengan tepat, seperti pada:

http://bredsaal.dk/learning-erlang-using-projecteuler-net

Karena ini lebih cepat daripada contoh C awal Anda, saya kira ada banyak masalah karena yang lain sudah dibahas secara rinci.

Modul Erlang ini dijalankan pada netbook murah dalam waktu sekitar 5 detik ... Menggunakan model jaringan thread di erlang dan, dengan demikian menunjukkan bagaimana cara mengambil keuntungan dari model acara. Itu dapat didistribusikan melalui banyak node. Dan itu cepat. Bukan kode saya.

-module(p12dist).  
-author("Jannich Brendle, [email protected], http://blog.bredsaal.dk").  
-compile(export_all).

server() ->  
  server(1).

server(Number) ->  
  receive {getwork, Worker_PID} -> Worker_PID ! {work,Number,Number+100},  
  server(Number+101);  
  {result,T} -> io:format("The result is: \~w.\~n", [T]);  
  _ -> server(Number)  
  end.

worker(Server_PID) ->  
  Server_PID ! {getwork, self()},  
  receive {work,Start,End} -> solve(Start,End,Server_PID)  
  end,  
  worker(Server_PID).

start() ->  
  Server_PID = spawn(p12dist, server, []),  
  spawn(p12dist, worker, [Server_PID]),  
  spawn(p12dist, worker, [Server_PID]),  
  spawn(p12dist, worker, [Server_PID]),  
  spawn(p12dist, worker, [Server_PID]).

solve(N,End,_) when N =:= End -> no_solution;

solve(N,End,Server_PID) ->  
  T=round(N*(N+1)/2),
  case (divisor(T,round(math:sqrt(T))) > 500) of  
    true ->  
      Server_PID ! {result,T};  
    false ->  
      solve(N+1,End,Server_PID)  
  end.

divisors(N) ->  
  divisor(N,round(math:sqrt(N))).

divisor(_,0) -> 1;  
divisor(N,I) ->  
  case (N rem I) =:= 0 of  
  true ->  
    2+divisor(N,I-1);  
  false ->  
    divisor(N,I-1)  
  end.

Tes di bawah ini berlangsung pada: Intel (R) Atom (TM) CPU N270 @ 1.60GHz

~$ time erl -noshell -s p12dist start

The result is: 76576500.

^C

BREAK: (a)bort (c)ontinue (p)roc info (i)nfo (l)oaded
       (v)ersion (k)ill (D)b-tables (d)istribution
a

real    0m5.510s
user    0m5.836s
sys 0m0.152s

C ++ 11, <20ms untuk saya - Jalankan di sini

Saya mengerti bahwa Anda ingin kiat untuk membantu meningkatkan pengetahuan khusus bahasa Anda, tetapi karena itu telah dibahas dengan baik di sini, saya pikir saya akan menambahkan beberapa konteks untuk orang-orang yang mungkin telah melihat komentar matematik pada pertanyaan Anda, dll, dan bertanya-tanya mengapa ini kode jauh lebih lambat.

Jawaban ini terutama untuk memberikan konteks agar semoga membantu orang mengevaluasi kode dalam pertanyaan Anda / jawaban lain dengan lebih mudah.

Kode ini hanya menggunakan beberapa optimisasi (jelek), tidak terkait dengan bahasa yang digunakan, berdasarkan:

1. setiap nomor lintasan adalah dalam bentuk n (n + 1) / 2
2. n dan n +1 adalah koprime
3. jumlah pembagi adalah fungsi multiplikasi

#include <iostream>
#include <cmath>
#include <tuple>
#include <chrono>

using namespace std;

// Calculates the divisors of an integer by determining its prime factorisation.

int get_divisors(long long n)
{
    int divisors_count = 1;

    for(long long i = 2;
        i <= sqrt(n);
        /* empty */)
    {
        int divisions = 0;
        while(n % i == 0)
        {
            n /= i;
            divisions++;
        }

        divisors_count *= (divisions + 1);

        //here, we try to iterate more efficiently by skipping
        //obvious non-primes like 4, 6, etc
        if(i == 2)
            i++;
        else
            i += 2;
    }

    if(n != 1) //n is a prime
        return divisors_count * 2;
    else
        return divisors_count;
}

long long euler12()
{
    //n and n + 1
    long long n, n_p_1;

    n = 1; n_p_1 = 2;

    // divisors_x will store either the divisors of x or x/2
    // (the later iff x is divisible by two)
    long long divisors_n = 1;
    long long divisors_n_p_1 = 2;

    for(;;)
    {
        /* This loop has been unwound, so two iterations are completed at a time
         * n and n + 1 have no prime factors in common and therefore we can
         * calculate their divisors separately
         */

        long long total_divisors;                 //the divisors of the triangle number
                                                  // n(n+1)/2

        //the first (unwound) iteration

        divisors_n_p_1 = get_divisors(n_p_1 / 2); //here n+1 is even and we

        total_divisors =
                  divisors_n
                * divisors_n_p_1;

        if(total_divisors > 1000)
            break;

        //move n and n+1 forward
        n = n_p_1;
        n_p_1 = n + 1;

        //fix the divisors
        divisors_n = divisors_n_p_1;
        divisors_n_p_1 = get_divisors(n_p_1);   //n_p_1 is now odd!

        //now the second (unwound) iteration

        total_divisors =
                  divisors_n
                * divisors_n_p_1;

        if(total_divisors > 1000)
            break;

        //move n and n+1 forward
        n = n_p_1;
        n_p_1 = n + 1;

        //fix the divisors
        divisors_n = divisors_n_p_1;
        divisors_n_p_1 = get_divisors(n_p_1 / 2);   //n_p_1 is now even!
    }

    return (n * n_p_1) / 2;
}

int main()
{
    for(int i = 0; i < 1000; i++)
    {
        using namespace std::chrono;
        auto start = high_resolution_clock::now();
        auto result = euler12();
        auto end = high_resolution_clock::now();

        double time_elapsed = duration_cast<milliseconds>(end - start).count();

        cout << result << " " << time_elapsed << '\n';
    }
    return 0;
}

Itu memakan waktu rata-rata sekitar 19 ms untuk desktop saya dan 80 ms untuk laptop saya, jauh dari kebanyakan kode lain yang saya lihat di sini. Dan tidak diragukan lagi, masih banyak optimisasi yang tersedia.

Mencoba GO:

package main

import "fmt"
import "math"

func main() {
    var n, m, c int
    for i := 1; ; i++ {
        n, m, c = i * (i + 1) / 2, int(math.Sqrt(float64(n))), 0
        for f := 1; f < m; f++ {
            if n % f == 0 { c++ }
    }
    c *= 2
    if m * m == n { c ++ }
    if c > 1001 {
        fmt.Println(n)
        break
        }
    }
}

Saya mendapat:

versi c asli: 9.1690 100%
go: 8.2520 111%

Tetapi menggunakan:

package main

import (
    "math"
    "fmt"
 )

// Sieve of Eratosthenes
func PrimesBelow(limit int) []int {
    switch {
        case limit < 2:
            return []int{}
        case limit == 2:
            return []int{2}
    }
    sievebound := (limit - 1) / 2
    sieve := make([]bool, sievebound+1)
    crosslimit := int(math.Sqrt(float64(limit))-1) / 2
    for i := 1; i <= crosslimit; i++ {
        if !sieve[i] {
            for j := 2 * i * (i + 1); j <= sievebound; j += 2*i + 1 {
                sieve[j] = true
            }
        }
    }
    plimit := int(1.3*float64(limit)) / int(math.Log(float64(limit)))
    primes := make([]int, plimit)
    p := 1
    primes[0] = 2
    for i := 1; i <= sievebound; i++ {
        if !sieve[i] {
            primes[p] = 2*i + 1
            p++
            if p >= plimit {
                break
            }
        }
    }
    last := len(primes) - 1
    for i := last; i > 0; i-- {
        if primes[i] != 0 {
            break
        }
        last = i
    }
    return primes[0:last]
}



func main() {
    fmt.Println(p12())
}
// Requires PrimesBelow from utils.go
func p12() int {
    n, dn, cnt := 3, 2, 0
    primearray := PrimesBelow(1000000)
    for cnt <= 1001 {
        n++
        n1 := n
        if n1%2 == 0 {
            n1 /= 2
        }
        dn1 := 1
        for i := 0; i < len(primearray); i++ {
            if primearray[i]*primearray[i] > n1 {
                dn1 *= 2
                break
            }
            exponent := 1
            for n1%primearray[i] == 0 {
                exponent++
                n1 /= primearray[i]
            }
            if exponent > 1 {
                dn1 *= exponent
            }
            if n1 == 1 {
                break
            }
        }
        cnt = dn * dn1
        dn = dn1
    }
    return n * (n - 1) / 2
}

Saya mendapat:

versi c asli: 9.1690 100%
versi c thaumkid: 0.1060 8650%
versi go pertama: 8.2520 111%
versi go kedua: 0.0230 39865%

Saya juga mencoba Python3.6 dan pypy3.3-5.5-alpha:

versi c asli: 8.629 100%
versi c parakid: 0.109 7916%
Python3.6: 54.795 16%
pypy3.3-5.5-alpha: 13.291 65%

dan kemudian dengan kode berikut saya dapat:

versi c asli: 8.629 100%
versi c thaumkid: 0.109 8650%
Python3.6: 1.489 580%
pypy3.3-5.5-alpha: 0.582 1483%

def D(N):
    if N == 1: return 1
    sqrtN = int(N ** 0.5)
    nf = 1
    for d in range(2, sqrtN + 1):
        if N % d == 0:
            nf = nf + 1
    return 2 * nf - (1 if sqrtN**2 == N else 0)

L = 1000
Dt, n = 0, 0

while Dt <= L:
    t = n * (n + 1) // 2
    Dt = D(n/2)*D(n+1) if n%2 == 0 else D(n)*D((n+1)/2)
    n = n + 1

print (t)

Perubahan: case (divisor(T,round(math:sqrt(T))) > 500) of

Untuk: case (divisor(T,round(math:sqrt(T))) > 1000) of

Ini akan menghasilkan jawaban yang benar untuk contoh multi-proses Erlang.

Saya membuat asumsi bahwa jumlah faktor hanya besar jika jumlah yang terlibat memiliki banyak faktor kecil. Jadi saya menggunakan algoritma thaumkid yang sangat baik, tetapi pertama-tama menggunakan perkiraan jumlah faktor yang tidak pernah terlalu kecil. Ini cukup sederhana: Periksa faktor prima hingga 29, lalu periksa angka yang tersisa dan hitung batas atas untuk nmber faktor. Gunakan ini untuk menghitung batas atas untuk sejumlah faktor, dan jika angka itu cukup tinggi, hitung jumlah faktor yang tepat.

Kode di bawah ini tidak memerlukan asumsi ini untuk kebenaran, tetapi untuk menjadi cepat. Tampaknya berhasil; hanya sekitar satu dari 100.000 angka yang memberikan perkiraan yang cukup tinggi sehingga memerlukan pemeriksaan penuh.

Berikut kodenya:

// Return at least the number of factors of n.
static uint64_t approxfactorcount (uint64_t n)
{
    uint64_t count = 1, add;

#define CHECK(d)                            \
    do {                                    \
        if (n % d == 0) {                   \
            add = count;                    \
            do { n /= d; count += add; }    \
            while (n % d == 0);             \
        }                                   \
    } while (0)

    CHECK ( 2); CHECK ( 3); CHECK ( 5); CHECK ( 7); CHECK (11); CHECK (13);
    CHECK (17); CHECK (19); CHECK (23); CHECK (29);
    if (n == 1) return count;
    if (n < 1ull * 31 * 31) return count * 2;
    if (n < 1ull * 31 * 31 * 37) return count * 4;
    if (n < 1ull * 31 * 31 * 37 * 37) return count * 8;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41) return count * 16;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43) return count * 32;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47) return count * 64;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53) return count * 128;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59) return count * 256;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61) return count * 512;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67) return count * 1024;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71) return count * 2048;
    if (n < 1ull * 31 * 31 * 37 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73) return count * 4096;
    return count * 1000000;
}

// Return the number of factors of n.
static uint64_t factorcount (uint64_t n)
{
    uint64_t count = 1, add;

    CHECK (2); CHECK (3);

    uint64_t d = 5, inc = 2;
    for (; d*d <= n; d += inc, inc = (6 - inc))
        CHECK (d);

    if (n > 1) count *= 2; // n must be a prime number
    return count;
}

// Prints triangular numbers with record numbers of factors.
static void printrecordnumbers (uint64_t limit)
{
    uint64_t record = 30000;

    uint64_t count1, factor1;
    uint64_t count2 = 1, factor2 = 1;

    for (uint64_t n = 1; n <= limit; ++n)
    {
        factor1 = factor2;
        count1 = count2;

        factor2 = n + 1; if (factor2 % 2 == 0) factor2 /= 2;
        count2 = approxfactorcount (factor2);

        if (count1 * count2 > record)
        {
            uint64_t factors = factorcount (factor1) * factorcount (factor2);
            if (factors > record)
            {
                printf ("%lluth triangular number = %llu has %llu factors\n", n, factor1 * factor2, factors);
                record = factors;
            }
        }
    }
}

Hal ini menemukan segitiga 14.753.024 dengan 13824 faktor dalam waktu sekitar 0,7 detik, angka segitiga 879.207.615 dengan 61.440 faktor dalam 34 detik, angka segitiga 12.524.486.975 dengan 138.240 faktor dalam 10 menit 5 detik, dan 26.467.792.064 angka segitiga dengan 172.032 faktor dalam 21 menit 25 detik (2.4GHz Core2 Duo), jadi kode ini rata-rata hanya membutuhkan 116 siklus prosesor per angka. Angka segitiga terakhir itu sendiri lebih besar dari 2 ^ 68, jadi

Saya mengubah versi "Jannich Brendle" menjadi 1000, bukannya 500. Dan mencantumkan hasil euler12.bin, euler12.erl, p12dist.erl. Kedua kode erl menggunakan '+ asli' untuk dikompilasi.

zhengs-MacBook-Pro:workspace zhengzhibin$ time erl -noshell -s p12dist start
The result is: 842161320.

real    0m3.879s
user    0m14.553s
sys     0m0.314s
zhengs-MacBook-Pro:workspace zhengzhibin$ time erl -noshell -s euler12 solve
842161320

real    0m10.125s
user    0m10.078s
sys     0m0.046s
zhengs-MacBook-Pro:workspace zhengzhibin$ time ./euler12.bin 
842161320

real    0m5.370s
user    0m5.328s
sys     0m0.004s
zhengs-MacBook-Pro:workspace zhengzhibin$

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

int factorCount (long n)
{
    double square = sqrt (n);
    int isquare = (int) square+1;
    long candidate = 2;
    int count = 1;
    while(candidate <= isquare && candidate<=n){
        int c = 1;
        while (n % candidate == 0) {
           c++;
           n /= candidate;
        }
        count *= c;
        candidate++;
    }
    return count;
}

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

gcc -lm -Ouler euler.c

waktu ./a.out

2,79 pengguna 0,00 sistem sistem 99% cpu 2,794 total