अजगर पीएचपी गति

Question

बनाम मैं Project Euler से एक समस्या को हल करने (BTW, समस्या 25) चाहते हैं, और मैं अजगर में एक समाधान पाया:

fibonacci = 1 
old1 = 0 
old2 = 1 
limit = 1000 

i = 1 

while len(str(fibonacci)) < limit: 
    fibonacci = old1 + old2 
    old1 = old2 
    old2 = fibonacci 
    i = i + 1 

print(i) 

यह गणना करने के लिए 1.5 सेकंड लिया।

मैं PHP में एक ही लागू किया, इस कोड है:

$fibonacci = 1; 
$old1 = 0; 
$old2 = 1; 
$limit = 1000; 

$i = 1; 

while (strlen((string)$fibonacci) < $limit){ 
    $fibonacci = $old1 + $old2; 
    $old1 = $old2; 
    $old2 = $fibonacci; 
    $i = $i + 1; 
} 
print($i); 

और यह 30 मिनट से अधिक, और अभी भी की गणना ...

ले लिया मुझे पता है कि अजगर तेजी पीएचपी से माना जाता है , लेकिन फिर भी यह इतना बड़ा अंतर नहीं होना चाहिए। परिणामों को तेज़ी से प्राप्त करने के लिए मेरे PHP कोड को कैसे सुधारें, अगर ऐसा करने का कोई तरीका है?

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

मैं इस पोस्ट तो पहले मेरी समाधान काम करने के लिए नहीं जा रहा था नीचे टिप्पणी के आधार पर संपादित करें। एक समाधान यह एक डाल करने के लिए वर्ष है, जबकि के बजाय हो सकता है:

while (strlen(number_format($fibonacci, 0, '', '')) < $limit){ ... } 

लेकिन फिर से एक बड़ा गति मुद्दा है।

तो अंतिम समाधान BCMath उपयोग कर रहा है:

$fibonacci = '1'; 
$old1 = '0'; 
$old2 = '1'; 
$limit = 1000; 

$i = 1; 

while (strlen($fibonacci) < $limit){ 

    $fibonacci = bcadd($old1, $old2); 
    $old1 = $old2; 
    $old2 = $fibonacci; 
    $i = $i + 1; 
} 
echo $fibonacci . "<br />"; 
print($i); 

तो तुम PHP में अजगर के रूप में एक ही गति से परिणाम प्राप्त कर सकते हैं।

Answer 1

निश्चित रूप से, PHP एक अनंत लूप में जा रहा है। अगर कोई गलती नहीं हुई तो ऐसा कोई लंबा रास्ता नहीं हो सकता है ...

मुझे नहीं लगता कि strlen के साथ इन नंबरों के अंकों की गिनती PHP में काम करने जा रही है। PHP पायथन से कम परिशुद्धता में, वैज्ञानिक नोटेशन में संख्याओं से निपट रहा है।

मैंने $ fibonacci और प्रत्येक चरण के लिए $ i प्रिंट करने के लिए PHP को echo कथन डीबगिंग जोड़ा।

एक ठेठ अजगर लाइन लगता है कि

fib is 7540113804746346429 
i is 92 

पीएचपी में, कि PHP में इसे पूरा करने के

fib is 7.54011380475E+18 
i is 92 

है, तो आप शायद एक उच्च परिशुद्धता गणित पुस्तकालय का उपयोग करना होगा।

http://www.php.net/manual/en/book.bc.php देखें - आप अतिरिक्त को पूरा करने के लिए bcadd फ़ंक्शन का उपयोग कर सकते हैं, और यह पाइथन में काम करेगा।

Answer 2

यह एक गति मुद्दा नहीं है, यह समाप्ति की स्थिति में एक तर्क समस्या है।

शायद यह खत्म नहीं होने वाला है। जब आप अपने परीक्षण परीक्षण में स्ट्रिंग में $ fibonacci के वर्तमान मान को परिवर्तित करते हैं, तो इसे स्ट्रिंग में डालने पर इसे दशमलव प्रारूप में परिवर्तित कर दिया जाएगा और दशमलव स्थानों के सीमित सेट (आपकी सटीक सेटिंग पर निर्भर) तक छोटा कर दिया जाएगा। अंकों की संख्या 1000 से बहुत कम होगी, इसलिए समय समाप्ति की स्थिति कभी नहीं मिलेगी।

Answer 3

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

def fibonacci_digits(limit): 
    limit = 10**limit 
    fib = 1 
    old1 = 0 
    old2 = 1 

    i = 1 
    size = 1 
    while size < limit: 
     fib = old1 + old2 
     if not size//fib: # // is pythons integer division operator, not a comment 
      size *= 10 
     old1 = old2 
     old2 = fib 
     i += 1 

    return i 

print fibonacci_digits(1000) 

स्ट्रिंग में कनवर्ट करना धीमा है और लगभग सही काम नहीं है। यहां समय सारिणी परिणाम हैं:

$ python -mtimeit -s'import fib' 'fib.fibonacci_digits(1000)' 
10 loops, best of 3: 30.2 msec per loop 

$ python -mtimeit -s'import fib' 'fib.fibonacci_digits2(1000)' 
10 loops, best of 3: 1.41 sec per loop 

Answer 4

कई परियोजनाओं में यूलर समस्याओं को बड़ी संख्या में संभालना होगा। PHP आपकी बड़ी संख्या 2.579234678963E+12 जैसा दिखता है जो संख्या का घातीय प्रतिनिधित्व है ... यह काम करना स्पष्ट रूप से कठिन है। तो, अधिकांश समस्याओं के लिए, BCMath Functions के साथ जाना सबसे अच्छा है। यह आपकी संख्या को उतना ही रखेगा जितना कि यह एक विशाल संख्या है।

ध्यान दें कि echo bcmul(500,500); का उपयोग echo 500*500 जितना तेज़ नहीं होगा। और, बीसीएमएथ फ़ंक्शन रिटर्न वैल्यू हमेशा तार होते हैं।

अपनी समस्या को ठीक करने के लिए सभी अंकगणितीय परिचालनों को संबंधित बीसीएमएथ फ़ंक्शन के साथ प्रतिस्थापित करें।

Answer 5

समस्या यह है कि आप बड़ी संख्या में काम कर रहे हैं। आपको बीसी मठ कार्यों का उपयोग करना चाहिए (php.net/bc)। तो आपका कोड हो सकता है:

$fibonacci = "1"; 
$old1 = "0"; 
$old2 = "1"; 
$limit = 1000; 

$i = 1; 

while (strlen($fibonacci) < $limit){ 
    $fibonacci = bcadd($old1, $old2); 
    $old1 = $old2; 
    $old2 = $fibonacci; 
    $i = $i + 1; 
} 
print($i); 

मैंने कोशिश की है और इसमें लगभग 0.0 9 5 लगते हैं।

Answer 6

मैंने थोड़ा पाइथन कोड अनुकूलित किया। अंकों की संख्या की जांच करने के लिए लेन (str()) का उपयोग करना बहुत धीमा है। अपने कार्यक्रम math.log10 द्वारा प्रतिस्थापित चलाने बहुत तेजी से

पहले कार्यकाल फाइबोनैचि अनुक्रम में 1000 अंक होने के लिए है: 4782 परिकलित ०.००८५७३ में सेकंड

import time 
from math import log10 


def digits(n): # Return the number of digits for n>=1 
    return int(log10(n))+1 

fibonacci = 1L # Thanks to Python to handle very big numbers 
old1 = 0 
old2 = 1 
limit = 1000 

i = 1 


start = time.time() #Start timer for bench 
while digits(fibonacci) < limit: 
    fibonacci = old1 + old2 
    old1 = old2 
    old2 = fibonacci 
    i += 1 



print "The first term in the Fibonacci sequence to contain %s digits is : %s" % (str(limit), str(i)) 

print "Calculated in %3.6f seconds" % (time.time() - start)