बिग्नम कार्यान्वयन जिसमें छोटे पूर्णांक

Question

का कुशल जोड़ा है, मैं एक एल्गोरिदम के लिए पाइथन के मूल बिग्नम का उपयोग कर रहा हूं और इसे C++ में परिवर्तित करके इसे चलाने और इसे गति देने का निर्णय लिया है। जब मैंने लंबे समय तक उपयोग किया, तो सी ++ पायथन की तुलना में लगभग 100x तेज था, लेकिन जब मैंने सी ++ में जीएमपी बाइंडिंग का इस्तेमाल किया, तो यह अजगर की तुलना में केवल 10x तेज था (उसी मामले के लिए जो लंबे समय तक फिट होता है)।

क्या बड़ी संख्या में छोटे परिवर्धन करने के लिए बेहतर संकेत है? उदाहरण के लिए, हमारे पास बड़ी संख्या में एन है, हम बहुत कम +1, +21, +1 इत्यादि जोड़ देंगे और प्रत्येक बार एक बार और एक और बड़ी संख्या एम जोड़ता है?

Answer 1

जीएमपी पुस्तकालय अपने आप में एक fast short integer add to MPZ routine

void mpz_add_ui (mpz_t rop, mpz_t op1, unsigned long int op2) 

मैं चाहे gmpy कि का उपयोग करता है पता नहीं है है, लेकिन अगर यह MPZ के लिए एक MPZ जोड़ने बनाम एक MPZ एक सामान्य अजगर पूर्णांक जोड़ने की कोशिश करता है और अगर देखना यह तेज़ है

संपादित

मैं बेंचमार्किंग का एक सा की कोशिश की और यह कोई फर्क

$ python -m timeit -c 'from gmpy import mpz 
> a=mpz(10**1000)' 'a+1' 
100000 loops, best of 3: 5.4 usec per loop 

$ python -m timeit -c 'from gmpy import mpz 
a=mpz(10**1000); b=mpz(1)' 'a+b' 
100000 loops, best of 3: 5.5 usec per loop 

नहीं है तो मुझे लगता है कि gmpy mpz_add_ui उपयोग नहीं करता है के रूप में मैं वास्तव में है कि होने की अपेक्षा करेंगे पाया बहुत तेज़

Answer 2

क्या आपने प्रोफाइलिंग किया था? पायथन और सी ++ पूरे अनुप्रयोगों के। ताकि आप जानते हैं कि आपको वास्तव में उस अतिरिक्त गति की आवश्यकता है।

पाइथन 3k का प्रयास करें अब इसमें कोई भी लंबाई पूर्णांक लागू है!

Answer 3

(नोट:। मैं मदद GMPY को बनाए रखने और मैं हाल ही में रिलीज में काफी कुछ अनुकूलन को क्रियान्वित किया है)

GMPY v1.11 mpz_add_ui का उपयोग करता है जब एक MPZ लिए एक छोटा सा नंबर जोड़ना। जीएमपीवाई का नवीनतम संस्करण छोटे संस्करणों के साथ काम करते समय पूर्व संस्करणों की तुलना में लगभग 25% तेज है।

With GMPY 1.04 
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000)" "a+1" 
10000000 loops, best of 3: 0.18 usec per loop 
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000);b=gmpy.mpz(1)" "a+b" 
10000000 loops, best of 3: 0.153 usec per loop 

With GMPY 1.11 
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000)" "a+1" 
10000000 loops, best of 3: 0.127 usec per loop 
$ py26 -mtimeit -s "import gmpy;a=gmpy.mpz(10**1000);b=gmpy.mpz(1)" "a+b" 
10000000 loops, best of 3: 0.148 usec per loop 

चूंकि यह तेज है एक लंबी करने के लिए एक अजगर पूर्णांक बदलने और mpz_add_ui फोन की तुलना में एक MPZ करने के लिए एक अजगर पूर्णांक कन्वर्ट करने के लिए, वहाँ एक मध्यम प्रदर्शन लाभ है। जीएमपी कार्यों बनाम मूल संचालन को लंबे समय तक कॉल करने के लिए 10x प्रदर्शन जुर्माना होने पर मुझे आश्चर्य नहीं होगा।

क्या आप कई छोटी संख्याओं को एक लंबे समय तक जमा कर सकते हैं और उन्हें एक बार में अपनी बड़ी संख्या में जोड़ सकते हैं?