[Python] प्रोजेक्ट यूलर के साथ स्पीड तुलना: सी बनाम पायथन बनाम एरलांग बनाम हास्केल


Answers

Erlang कार्यान्वयन के साथ कुछ समस्याएं हैं। निम्नलिखित के लिए बेसलाइन के रूप में, आपके कोड रहित कोड के लिए 12.7 सेकंड की तुलना में आपके अनमोडिफाइड एरलांग प्रोग्राम के लिए मेरा मापा निष्पादन समय 47.6 सेकंड था।

यदि आप कम्प्यूटेशनल गहन एरलांग कोड को चलाने के लिए चाहते हैं तो सबसे पहले आपको मूल कोड का उपयोग करना चाहिए। erlc +native euler12 साथ संकलन समय को 41.3 सेकंड तक मिला। हालांकि इस तरह के कोड पर देशी संकलन से अपेक्षाकृत यह बहुत कम गति (केवल 15%) है, और समस्या आपका उपयोग -compile(export_all) का उपयोग है। यह प्रयोग के लिए उपयोगी है, लेकिन तथ्य यह है कि सभी कार्यों को बाहरी संकलक संभावित रूप से पहुंचने योग्य होते हैं, मूल संकलक बहुत रूढ़िवादी होते हैं। (सामान्य बीएएम एमुलेटर इतना प्रभावित नहीं होता है।) इस घोषणा को -export([solve/0]). साथ बदलना -export([solve/0]). एक बेहतर गति देता है: 31.5 सेकंड (आधार रेखा से लगभग 35%)।

लेकिन कोड में स्वयं एक समस्या है: कारक लूप में प्रत्येक पुनरावृत्ति के लिए, आप यह परीक्षण करते हैं:

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

सी कोड ऐसा नहीं करता है। आम तौर पर, एक ही कोड के विभिन्न कार्यान्वयन के बीच उचित तुलना करना मुश्किल हो सकता है, और विशेष रूप से यदि एल्गोरिदम संख्यात्मक है, क्योंकि आपको यह सुनिश्चित करने की आवश्यकता है कि वे वास्तव में एक ही काम कर रहे हैं। कुछ टाइपकास्ट के कारण कहीं एक कार्यान्वयन में थोड़ी सी गोल करने वाली त्रुटि से दूसरे की तुलना में कई और पुनरावृत्ति हो सकती है, भले ही दोनों अंततः एक ही परिणाम तक पहुंच जाएं।

इस संभावित त्रुटि स्रोत को खत्म करने के लिए (और प्रत्येक पुनरावृत्ति में अतिरिक्त परीक्षण से छुटकारा पाएं), मैं निम्नानुसार कारकउंट फ़ंक्शन को फिर से लिखता हूं, सी कोड पर बारीकी से मॉडलिंग किया गया है:

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.

यह पुनः लिखना, कोई export_all , और देशी संकलन, मुझे निम्नलिखित रन टाइम दिया:

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

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

जो सी कोड की तुलना में बहुत बुरा नहीं है:

$ time ./a.out 
842161320

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

इस बात पर विचार करते हुए कि एरलांग संख्यात्मक कोड लिखने की दिशा में तैयार नहीं है, इस तरह के कार्यक्रम पर सी से केवल 50% धीमी है, यह बहुत अच्छी है।

अंत में, आपके प्रश्नों के बारे में:

प्रश्न 1: मनमानी लंबाई पूर्णांक का उपयोग करने के कारण एरलांग, पायथन और हैकेल ढीली गति करें या जब तक मान MAXINT से कम न हों?

हाँ, कुछ हद तक। एरलांग में, "32/64-बिट अंकगणित का उपयोग लपेटने के साथ" कहने का कोई तरीका नहीं है, इसलिए जब तक कि संकलक आपके पूर्णांक (और आमतौर पर नहीं कर सकता) पर कुछ सीमाएं साबित कर सकता है, इसे देखने के लिए सभी गणनाओं को जांचना होगा अगर वे एक टैग किए गए शब्द में फिट हो सकते हैं या यदि उन्हें उन्हें ढेर-आवंटित बिग्नम में बदलना है। भले ही रनटाइम पर अभ्यास में कोई भी बिग्नम का उपयोग नहीं किया जाता है, फिर भी इन जांचों को निष्पादित करना होगा। दूसरी तरफ, इसका मतलब है कि आप जानते हैं कि एल्गोरिदम कभी अप्रत्याशित पूर्णांक रैपरराउंड की वजह से असफल नहीं होगा यदि आप अचानक इसे पहले से बड़े इनपुट देते हैं।

प्रश्न 4: क्या मेरे कार्यात्मक कार्यान्वयन एलसीओ को अनुमति देते हैं और इसलिए कॉल स्टैक पर अनावश्यक फ्रेम जोड़ने से बचें?

हां, आपका एरलांग कोड अंतिम कॉल अनुकूलन के संबंध में सही है।

Question

मैंने प्रोजेक्ट यूलर से प्रोग्रामिंग अभ्यास के रूप में समस्या # 12 ली है और सी, पायथन, एरलांग और हास्केल में मेरे (निश्चित रूप से इष्टतम नहीं) कार्यान्वयन की तुलना की है। कुछ उच्च निष्पादन समय प्राप्त करने के लिए, मैं मूल समस्या में बताए गए 500 के बजाय 1000 से अधिक divisors के साथ पहले त्रिकोण संख्या की खोज करता हूं।

नतीजा निम्न है:

सी:

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

अजगर:

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

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

पायपी के साथ पायथन:

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

हास्केल:

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

सारांश:

  • सी: 100%
  • पायथन: 692% (पीईपीई के साथ 118%)
  • Erlang: 436% (रिचर्ड सी के लिए 135% धन्यवाद)
  • हास्केल: 1421%

मुझे लगता है कि सी का एक बड़ा फायदा है क्योंकि यह गणना के लिए लंबे समय तक उपयोग करता है और अन्य तीनों के रूप में मनमाने ढंग से लंबाई पूर्णांक नहीं करता है। इसके अलावा इसे पहले रनटाइम लोड करने की आवश्यकता नहीं है (दूसरों को करें?)।

प्रश्न 1: क्या एरलांग, पायथन और हास्केल मनमानी लंबाई पूर्णांक का उपयोग करने के कारण गति खो देते हैं या जब तक मान MAXINT से कम नहीं MAXINT ?

प्रश्न 2: हास्केल इतना धीमा क्यों है? क्या कोई कंपाइलर ध्वज है जो ब्रेक को बंद करता है या यह मेरा कार्यान्वयन है? (उत्तरार्द्ध काफी संभावना है क्योंकि हास्केल मेरे लिए सात मुहरों वाली एक पुस्तक है।)

प्रश्न 3: क्या आप मुझे कुछ संकेत बता सकते हैं कि इन कार्यान्वयनों को अनुकूलित करने के तरीके को बदलने के तरीके को बदलने के बिना कैसे? किसी भी तरह से अनुकूलन: भाषा के लिए बेहतर, तेज, अधिक "मूल"।

संपादित करें:

प्रश्न 4: क्या मेरे कार्यात्मक कार्यान्वयन एलसीओ (अंतिम कॉल अनुकूलन, उर्फ ​​पूंछ रिकर्सन उन्मूलन) परमिट करते हैं और इसलिए कॉल स्टैक पर अनावश्यक फ्रेम जोड़ने से बचते हैं?

मैंने वास्तव में चार भाषाओं में जितना संभव हो उतना एल्गोरिदम लागू करने की कोशिश की, हालांकि मुझे यह मानना ​​है कि मेरा हास्केल और एरलांग ज्ञान बहुत सीमित है।

स्रोत कोड का इस्तेमाल किया गया:

#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



प्रश्न 3: क्या आप मुझे कुछ संकेत बता सकते हैं कि इन कार्यान्वयनों को अनुकूलित करने के तरीके को बदलने के तरीके को बदलने के बिना कैसे? किसी भी तरह से अनुकूलन: भाषा के लिए बेहतर, तेज, अधिक "मूल"।

सी कार्यान्वयन उप-स्थानिक है (जैसा कि थॉमस एम। डुबुइसन द्वारा संकेत दिया गया है), संस्करण 64-बिट पूर्णांक (यानी लंबी डेटाटाइप) का उपयोग करता है। मैं बाद में असेंबली लिस्टिंग की जांच करूंगा, लेकिन एक शिक्षित अनुमान के साथ, संकलित कोड में कुछ मेमोरी एक्सेस चल रही हैं, जो 64-बिट पूर्णांक का उपयोग करके धीमे हो जाते हैं। यह वह है या जेनरेट कोड (यह तथ्य है कि आप एसएसई रजिस्टर में कम 64-बिट इन्स फिट कर सकते हैं या 64-बिट पूर्णांक के लिए डबल के चारों ओर गोल कर सकते हैं)।

यहां संशोधित कोड है (बस int के साथ लंबे समय तक प्रतिस्थापित करें और मैं स्पष्ट रूप से कारक कार्ट में रेखांकित करता हूं, हालांकि मुझे नहीं लगता कि यह 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);
}

चल रहा है + समय यह देता है:

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

संदर्भ के लिए, थॉमस द्वारा पहले के जवाब में हैकेल कार्यान्वयन देता है:

$ 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

निष्कर्ष: ghc से कुछ भी नहीं लेना, यह एक महान संकलक है, लेकिन जीसीसी आमतौर पर तेज़ कोड उत्पन्न करता है।




Some more numbers and explanations for the C version. Apparently noone did it during all those years. Remember to upvote this answer so it can get on top for everyone to see and learn.

Step One: Benchmark of the author's programs

Laptop Specifications:

  • CPU i3 M380 (931 MHz - maximum battery saving mode)
  • 4GB memory
  • Win7 64 bits
  • Microsoft Visual Studio 2012 Ultimate
  • Cygwin with gcc 4.9.3
  • Python 2.7.10

Commands:

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

Filenames are: integertype_architecture_compiler.exe

  • integertype is the same as the original program for now (more on that later)
  • architecture is x86 or x64 depending on the compiler settings
  • compiler is gcc or vs2012

Step Two: Investigate, Improve and Benchmark Again

VS is 250% faster than gcc. The two compilers should give a similar speed. Obviously, something is wrong with the code or the compiler options. Let's investigate!

The first point of interest is the integer types. Conversions can be expensive and consistency is important for better code generation & optimizations. All integers should be the same type.

It's a mixed mess of int and long right now. We're going to improve that. What type to use? The fastest. Gotta benchmark them'all!

----------
$ 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

Integer types are int long int32_t uint32_t int64_t and uint64_t from #include <stdint.h>

There are LOTS of integer types in C, plus some signed/unsigned to play with, plus the choice to compile as x86 or x64 (not to be confused with the actual integer size). That is a lot of versions to compile and run ^^

Step Three: Understanding the Numbers

Definitive conclusions:

  • 32 bits integers are ~200% faster than 64 bits equivalents
  • unsigned 64 bits integers are 25 % faster than signed 64 bits (Unfortunately, I have no explanation for that)

Trick question: "What are the sizes of int and long in C?"
The right answer is: The size of int and long in C are not well-defined!

From the C spec:

int is at least 32 bits
long is at least an int

From the gcc man page (-m32 and -m64 flags):

The 32-bit environment sets int, long and pointer to 32 bits and generates code that runs on any i386 system.
The 64-bit environment sets int to 32 bits and long and pointer to 64 bits and generates code for AMD's x86-64 architecture.

From MSDN documentation (Data Type Ranges) https://msdn.microsoft.com/en-us/library/s3f49ktz%28v=vs.110%29.aspx :

int, 4 bytes, also knows as signed
long, 4 bytes, also knows as long int and signed long int

To Conclude This: Lessons Learned

  • 32 bits integers are faster than 64 bits integers.

  • Standard integers types are not well defined in C nor C++, they vary depending on compilers and architectures. When you need consistency and predictability, use the uint32_t integer family from #include <stdint.h> .

  • Speed issues solved. All other languages are back hundreds percent behind, C & C++ win again ! They always do. The next improvement will be multithreading using OpenMP :D




हास्केल पैकेज से कुछ फ़ंक्शंस का उपयोग कर आपके हास्केल कार्यान्वयन को बहुत बढ़ाया जा सकता है। इस मामले में मैंने प्राइम्स का इस्तेमाल किया, जो कि 'कैबल इंस्टाल प्राइम' के साथ स्थापित है;)

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)

समय:

आपका मूल कार्यक्रम:

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

TotalSeconds      : 16.3807409
TotalMilliseconds : 16380.7409

बेहतर कार्यान्वयन

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

TotalSeconds      : 0.0383436
TotalMilliseconds : 38.3436

जैसा कि आप देख सकते हैं, यह एक ही मशीन पर 38 मिलीसेकंड में चलता है जहां आपका 16 सेकंड में चलाया जाता है :)

संकलन आदेश:

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



I made the assumption that the number of factors is only large if the numbers involved have many small factors. So I used thaumkid's excellent algorithm, but first used an approximation to the factor count that is never too small. It's quite simple: Check for prime factors up to 29, then check the remaining number and calculate an upper bound for the nmber of factors. Use this to calculate an upper bound for the number of factors, and if that number is high enough, calculate the exact number of factors.

The code below doesn't need this assumption for correctness, but to be fast. It seems to work; only about one in 100,000 numbers gives an estimate that is high enough to require a full check.

Here's the code:

// 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;
            }
        }
    }
}

This finds the 14,753,024th triangular with 13824 factors in about 0.7 seconds, the 879,207,615th triangular number with 61,440 factors in 34 seconds, the 12,524,486,975th triangular number with 138,240 factors in 10 minutes 5 seconds, and the 26,467,792,064th triangular number with 172,032 factors in 21 minutes 25 seconds (2.4GHz Core2 Duo), so this code takes only 116 processor cycles per number on average. The last triangular number itself is larger than 2^68, so




प्रश्न 1: मनमानी लंबाई पूर्णांक का उपयोग करने के कारण एरलांग, पायथन और हैकेल ढीली गति करें या जब तक मान MAXINT से कम न हों?

यह असंभव है। मैं एर्लांग और हास्केल के बारे में ज्यादा कुछ नहीं कह सकता (ठीक है, शायद नीचे हास्केल के बारे में थोड़ा सा) लेकिन मैं पाइथन में कई अन्य बाधाओं को इंगित कर सकता हूं। प्रत्येक बार जब प्रोग्राम पायथन में कुछ मानों के साथ एक ऑपरेशन निष्पादित करने का प्रयास करता है, तो यह सत्यापित करना चाहिए कि मान उचित प्रकार से हैं या नहीं, और इसमें कुछ समय लगता है। आपका factorCount फ़ंक्शन केवल range (1, isquare + 1) साथ एक सूची आवंटित करता है, और रनटाइम, मॉलोक-स्टाइल मेमोरी आवंटन काउंटर के साथ एक सीमा पर पुनरावर्तित होने की तुलना में धीमा तरीका है जैसा कि आप सी में करते हैं। विशेष रूप से, factorCount() कई बार कहा जाता है और इसलिए कई सूचियों को आवंटित करता है। साथ ही, हमें यह नहीं भूलना चाहिए कि पायथन का अर्थ है और सीपीथन दुभाषिया का अनुकूलन करने पर कोई बड़ा ध्यान नहीं है।

संपादित करें : ओह, ठीक है, मुझे लगता है कि आप पाइथन 3 का उपयोग कर रहे हैं तो range() एक सूची नहीं लौटाती है, लेकिन जनरेटर। इस मामले में, सूचियों को आवंटित करने के बारे में मेरा बिंदु आधा गलत है: फ़ंक्शन केवल range ऑब्जेक्ट्स आवंटित करता है, जो अक्षम हैं लेकिन फिर भी बहुत सारी वस्तुओं के साथ सूची आवंटित करने के रूप में अक्षम नहीं हैं।

प्रश्न 2: हैकेल इतनी धीमी क्यों है? क्या कोई कंपाइलर ध्वज है जो ब्रेक को बंद करता है या यह मेरा कार्यान्वयन है? (उत्तरार्द्ध काफी संभावना है क्योंकि हैकेल एक पुस्तक है जिसमें सात मुहर हैं।)

क्या आप Hugs का उपयोग कर रहे हैं? हग्स काफी धीमी दुभाषिया है। यदि आप इसका उपयोग कर रहे हैं, तो हो सकता है कि आप GHC साथ बेहतर समय प्राप्त कर सकें - लेकिन मैं केवल हाइपोटिस को संहिताबद्ध कर रहा हूं, हुडेल कंपाइलर हुड के नीचे एक अच्छी चीज है और मेरी समझ से परे तरीका है :)

प्रश्न 3: क्या आप मुझे कुछ संकेत बता सकते हैं कि मैं इन कारकों को निर्धारित करने के तरीके को बदलने के बिना इन कार्यान्वयन को कैसे अनुकूलित कर सकता हूं? किसी भी तरह से अनुकूलन: भाषा के लिए बेहतर, तेज, अधिक "मूल"।

मैं कहूंगा कि आप एक असुरक्षित खेल खेल रहे हैं। विभिन्न भाषाओं को जानने का सबसे अच्छा हिस्सा उन्हें सबसे अलग तरीके से उपयोग करना है :) लेकिन मैं digress, मुझे इस बिंदु के लिए कोई सिफारिश नहीं है। क्षमा करें, मुझे आशा है कि कोई इस मामले में आपकी मदद कर सकता है :)

प्रश्न 4: क्या मेरे कार्यात्मक कार्यान्वयन एलसीओ को अनुमति देते हैं और इसलिए कॉल स्टैक पर अनावश्यक फ्रेम जोड़ने से बचें?

जहां तक ​​मुझे याद है, आपको बस यह सुनिश्चित करने की आवश्यकता है कि मूल्य लौटने से पहले आपका रिकर्सिव कॉल अंतिम आदेश है। दूसरे शब्दों में, नीचे दिए गए जैसे फ़ंक्शन इस तरह के अनुकूलन का उपयोग कर सकते हैं:

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

हालांकि, यदि आपका फ़ंक्शन नीचे जैसा था, तो आपके पास ऐसा अनुकूलन नहीं होगा, क्योंकि रिकर्सिव कॉल के बाद कोई ऑपरेशन (गुणा) है:

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

मैंने कुछ स्थानीय चरों में परिचालन को अलग करने के लिए यह स्पष्ट कर दिया कि कौन से संचालन निष्पादित किए गए हैं। हालांकि, इन कार्यों को नीचे के रूप में देखना सबसे सामान्य है, लेकिन वे जो बिंदु बना रहे हैं उसके बराबर हैं:

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

ध्यान दें कि यह संकलक / दुभाषिया पर निर्भर करता है कि यह पूंछ रिकर्सन करेगा या नहीं। उदाहरण के लिए, यदि मुझे अच्छी तरह से याद है तो पाइथन दुभाषिया ऐसा नहीं करता है (मैंने अपने उदाहरण में पाइथन का उपयोग केवल इसके धाराप्रवाह वाक्यविन्यास के कारण किया था)। वैसे भी, अगर आपको दो पैरामीटर के साथ फैक्टोरियल फ़ंक्शंस जैसे अजीब सामान मिलते हैं (और पैरामीटर में से एक में acc , accumulator आदि जैसे नाम हैं) अब आप जानते हैं कि लोग ऐसा क्यों करते हैं :)




#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 -Ofast euler.c

समय ./a.out

2.79s उपयोगकर्ता 0.00s सिस्टम 99% सीपीयू 2.794 कुल




Trying 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
        }
    }
}

I get:

original c version: 9.1690 100%
go: 8.2520 111%

But using:

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
}

I get:

original c version: 9.1690 100%
thaumkid's c version: 0.1060 8650%
first go version: 8.2520 111%
second go version: 0.0230 39865%

I also tried Python3.6 and pypy3.3-5.5-alpha:

original c version: 8.629 100%
thaumkid's c version: 0.109 7916%
Python3.6: 54.795 16%
pypy3.3-5.5-alpha: 13.291 65%

and then with following code I got:

original c version: 8.629 100%
thaumkid's c version: 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)



अपने Erlang कार्यान्वयन को देख रहे हैं। समय में पूरे वर्चुअल मशीन की शुरुआत, आपके प्रोग्राम को चलाने और वर्चुअल मशीन को रोकने में शामिल है। मुझे पूरा यकीन है कि एरलांग वीएम की स्थापना और रोकना कुछ समय लगता है।

यदि समय erlang आभासी मशीन के भीतर किया गया था, तो परिणाम अलग-अलग होंगे क्योंकि उस मामले में हमारे पास केवल प्रश्न के कार्यक्रम के लिए वास्तविक समय होगा। Otherwise, i believe that the total time taken by the process of starting and loading of the Erlang Vm plus that of halting it (as you put it in your program) are all included in the total time which the method you are using to time the program is outputting. Consider using the erlang timing itself which we use when we want to time our programs within the virtual machine itself timer:tc/1 or timer:tc/2 or timer:tc/3 . In this way, the results from erlang will exclude the time taken to start and stop/kill/halt the virtual machine. That is my reasoning there, think about it, and then try your bench mark again.

I actually suggest that we try to time the program (for languages that have a runtime), within the runtime of those languages in order to get a precise value. C for example has no overhead of starting and shutting down a runtime system as does Erlang, Python and Haskell (98% sure of this - i stand correction). So (based on this reasoning) i conclude by saying that this benchmark wasnot precise /fair enough for languages running on top of a runtime system. Lets do it again with these changes.

EDIT: besides even if all the languages had runtime systems, the overhead of starting each and halting it would differ. so i suggest we time from within the runtime systems (for the languages for which this applies). The Erlang VM is known to have considerable overhead at start up!