सिंगल-लाइन सी / सी ++। भाग २

इससे पहले, मैंने पहले ही सिंगल-लाइन इन सी ++ पर एक लेख प्रकाशित किया था। इसलिए इस पोस्ट में मैं कुछ और एल्गोरिदम का उल्लेख करना चाहता हूं, साथ ही दो संख्याओं के आदान-प्रदान के लिए एल्गोरिदम के कई कार्यान्वयन (ऑपरेटिंग समय की गणना के साथ)।
सभी इच्छुक कृपया कटौती के लिए पूछें;)

1. सादगी के लिए परीक्षण

इस फ़ंक्शन को कॉल करने के लिए, prime(100, int(sqrt(100))); लिखें prime(100, int(sqrt(100)));

 bool prime(int n, int div) { return ( div == 1) ? true : (n % div != 0) && (prime(n, div-1)); } 

इससे बचने के लिए, आप एक आवरण समारोह बना सकते हैं:

 bool prime(int n) { return ( n == 1 )? 0 : ( prime( n, int(sqrt(n))) ) ; } 

और अब, फ़ंक्शन को कॉल करने के लिए, बस prime(100) लिखें prime(100)

2. ग्रे कोड

एक ग्रे कोड गैर-नकारात्मक संख्याओं की संख्या के लिए एक प्रणाली है जब दो पड़ोसी संख्याओं के कोड बिल्कुल एक बिट में भिन्न होते हैं।

 int codeGrey (int n) { return n ^ (n >> 1); } 

साथ ही ग्रे का रिवर्स कोड ढूंढ रहा है

 int revCodeGrey (int g) { int n; for (n=0; g; n ^=g, g>>=1); return n; } 

विभिन्न क्षेत्रों में ग्रे कोड के कई उपयोग हैं:

• ग्रे बिट कोड एक एन-डायमेंशनल क्यूब में हैमिल्टनियन चक्र से मेल खाता है
• हनोई टावरों की समस्या को हल करने में
• आनुवंशिक एल्गोरिदम के सिद्धांत में आवेदन

3. द्विपद गुणांक की गणना

द्विपद गुणांक न्यूटन के द्विपद के विस्तार में गुणांक है एक्स की शक्तियों में।

 int binomialCoefficient(int k, int n) { return (n==k || k==0)?1:binomialCoefficient(k-1,n-1)+binomialCoefficient(k,n-1); } 

4. भाज्य भाजक की डिग्री का पता लगाना

दो नंबर दिए गए हैं: [n] और [k]। यह उस डिग्री की गणना करने के लिए आवश्यक है जिस पर भाजक [के] को संख्या [एन] में शामिल किया गया है।

 int factPow(int n, int k) { return (n)? (n/k + factPow(n/k, k)):0; } 

5. संख्या [a] को शक्ति [b] मोडुलो [p] को ऊपर उठाना।

 nt powM(int a, int b, int p) { return b ? (a * powM(a-1, b, p) % p) : 1; } 

आप यहां भारतीय प्रतिपादक एल्गोरिथ्म का भी उपयोग कर सकते हैं।

 int powM(int a, int b, int p) { return b ? ((b&1?a:1)*powM(a*a, b/2, p) % p) : 1; } 

---

स्वपा का मेरा अध्ययन

इसलिए मुझे विभिन्न प्रकार के SWAPs का पता लगाने का विचार मिला, जो सबसे तेज है।
SWAP टेस्ट एक ऐसा कार्यक्रम होगा

  int a=1, b=2; for(int i=0; i<=300000000; i++) { swap(&a, &b); } 

जहां स्वैप के बजाय, दो मूल्यों के आदान-प्रदान के लिए अलग-अलग एल्गोरिदम होंगे।

SWAP0

तो चलो STLivsky मानक एल्गोरिथ्म से शुरू करते हैं:

 template <class T> void swap0 ( T& a, T& b ) { T c(a); a=b; b=c; } 

उनके संकेतक इस प्रकार थे:

  1,996 sec. 1,986 sec. 1,996 sec. 

SWAP1

अगला SWAP तथाकथित XOR SWAP होगा:

 void swap1(int *a, int *b) { *a ^= ( *b ^= ( *a ^= *b )); } 

उनके संकेतक इस प्रकार थे:

  3,603 sec. 3,603 sec. 3,608 sec. 

SWAP2

 void swap2(int *a, int *b) { *a += *b -= *a = *b - *a; } 

उसके संकेतक इस प्रकार थे:

  3.728 sec. 3.723 sec. 3.728 sec. 

SWAP3

 void swap3(int *a, int *b) { *a /= *b = (*a= *a * (*b)) / (*b); } 

उसके संकेतक इस प्रकार थे:

  7.878 sec. 7.862 sec. 7.862 sec. 

SWAP4

 void swap4(int *a, int *b) { *b= *a + *b - (*a = *b); } 

उसके संकेतक इस प्रकार थे:

  2.012 sec. 2.007 sec. 2.012 sec. 

SWAP5

 void swap5(int *a, int *b) { *a=(*b=(*a=*b^*a)^*b)^*a; } 

उसके संकेतक इस प्रकार थे:

  3.198 sec. 3.213 sec. 3.198 sec. 

SWAP6

खैर, और कोडांतरक GCC संकलक के लिए सम्मिलित करें

 void swap7(int *a, int *b) { asm volatile( "XOR %%EAX, %%EBX; \n\t" "XOR %%EBX, %%EAX; \n\t" "XOR %%EAX, %%EBX; \n\t" :"=a"(*a),"=b"(*b) :"a"(*a),"b"(*b) ); } 

उसके संकेतक इस प्रकार थे:

  2.199 sec. 2.153 sec. 2.167 sec. 

जैसा कि आप देख सकते हैं कि हमारी शोध तालिका इस प्रकार है:

1.  SWAP0 - 1.992 sec. 

2.  SWAP4 - 2.010 sec. 

3.  SWAP6 - 2.173 sec. 

4.  SWAP5 - 3.203 sec. 

5.  SWAP1 - 3.604 sec. 

6.  SWAP2 - 3.726 sec. 

7.  SWAP3 - 7.867 sec.