एल्गोरिथम दक्षता: Difference between revisions

From Vigyanwiki
No edit summary
Line 2: Line 2:
{{Distinguish|text=optimization, which is discussed in [[program optimization]], [[optimizing compiler]], [[loop optimization]], [[object code optimizer]], etc.}}
{{Distinguish|text=optimization, which is discussed in [[program optimization]], [[optimizing compiler]], [[loop optimization]], [[object code optimizer]], etc.}}
{{Use dmy dates|date=February 2023}}
{{Use dmy dates|date=February 2023}}
[[कंप्यूटर विज्ञान]] में, [[ कलन विधि ]] दक्षता एल्गोरिथम की एक संपत्ति है जो एल्गोरिथम द्वारा उपयोग किए जाने वाले [[कम्प्यूटेशनल संसाधन]]ों की मात्रा से संबंधित है। एक एल्गोरिथ्म अपने संसाधन उपयोग को निर्धारित करने के लिए [[एल्गोरिदम का विश्लेषण]] होना चाहिए, और एक एल्गोरिथ्म की दक्षता को विभिन्न संसाधनों के उपयोग के आधार पर मापा जा सकता है। एक दोहराई जाने वाली या सतत प्रक्रिया के लिए एल्गोरिदमिक दक्षता को इंजीनियरिंग [[उत्पादकता]] के अनुरूप माना जा सकता है।


अधिकतम दक्षता के लिए संसाधन उपयोग को कम करना वांछनीय है। हालांकि, [[समय जटिलता]] और [[अंतरिक्ष जटिलता]] जटिलता जैसे विभिन्न संसाधनों की सीधे तुलना नहीं की जा सकती है, इसलिए दो एल्गोरिदम में से कौन सा अधिक कुशल माना जाता है, यह अक्सर इस बात पर निर्भर करता है कि दक्षता के किस उपाय को सबसे महत्वपूर्ण माना जाता है।
[[कंप्यूटर विज्ञान]] में, [[ कलन विधि |कलन विधि]] दक्षता कलन विधि की एक विशेषता है जो कलन विधि द्वारा उपयोग किए जाने वाले [[कम्प्यूटेशनल संसाधन|संगणनात्मक संसाधनों]] की मात्रा से संबंधित है। एक कलन विधि को अपने संसाधन के उपयोग को निर्धारित करने के लिए [[एल्गोरिदम का विश्लेषण|कलन विधि का विश्लेषण]] करना चाहिए, और एक कलन विधि की दक्षता को विभिन्न संसाधनों के उपयोग के आधार पर मापा जा सकता है। एक पुनरावृत्ति की जाने वाली या सतत प्रक्रिया के लिए कलनविधीय दक्षता को इंजीनियरिंग [[उत्पादकता]] के अनुरूप माना जा सकता है।


उदाहरण के लिए, [[ बुलबुले की तरह ]] और टाइमसॉर्ट दोनों ही छोटे से बड़े आइटम की [[ छँटाई एल्गोरिथ्म ]] हैं। बबल सॉर्ट समय में सूची को चुकता तत्वों की संख्या के अनुपात में क्रमबद्ध करता है (<math display="inline">O(n^2)</math>, [[बिग ओ नोटेशन]] देखें), लेकिन केवल थोड़ी मात्रा में अतिरिक्त [[ स्मृति ]] की आवश्यकता होती है जो सूची की लंबाई के संबंध में स्थिर होती है (<math display="inline">O(1)</math>). टिम्सोर्ट सूची को समय के अनुसार क्रमबद्ध करता है (इसके लघुगणक की मात्रा के गुणन के अनुपात में) सूची की लंबाई में (<math display="inline">O(n\log n)</math>), लेकिन सूची की लंबाई में एक स्थान की आवश्यकता [[आनुपातिकता (गणित)]] है (<math display="inline">O(n)</math>). यदि किसी दिए गए एप्लिकेशन के लिए बड़ी सूचियों को उच्च गति से क्रमबद्ध किया जाना चाहिए, तो टाइमसोर्ट एक बेहतर विकल्प है; हालाँकि, यदि छँटाई की स्मृति पदचिह्न को कम करना अधिक महत्वपूर्ण है, तो बुलबुला छँटाई एक बेहतर विकल्प है।
अधिकतम दक्षता के लिए संसाधन उपयोग को कम करना वांछनीय है। हालांकि, [[समय जटिलता]] और [[अंतरिक्ष जटिलता]] जटिलता जैसे विभिन्न संसाधनों की प्रत्यक्ष तुलना नहीं की जा सकती है, इसलिए दो कलन विधि में से कौन सा अधिक कुशल माना जाता है, यह प्रायः इस बात पर निर्भर करता है कि दक्षता के किस उपाय को सबसे महत्वपूर्ण माना जाता है।
 
उदाहरण के लिए, [[ बुलबुले की तरह |बुलबुले सॉर्ट]] और टाइमसॉर्ट दोनों ही छोटे से बड़े आइटम की [[ छँटाई एल्गोरिथ्म |छँटाई कलन विधि]] हैं जो वस्तुओं की सूची को सबसे छोटे से सबसे बड़े तक क्रमबद्ध करते हैं। बबल सॉर्ट समय में सूची को चुकता तत्वों की संख्या के अनुपात में क्रमबद्ध करता है (<math display="inline">O(n^2)</math>, [[बिग ओ नोटेशन]] देखें), लेकिन केवल थोड़ी मात्रा में अतिरिक्त [[ स्मृति |मेमोरी]] की आवश्यकता होती है जो सूची की लंबाई के संबंध में स्थिर होती है (<math display="inline">O(1)</math>). टिम्सोर्ट सूची को समय के अनुसार क्रमबद्ध करता है (इसके लघुगणक की मात्रा के गुणन के अनुपात में) सूची की लंबाई में (<math display="inline">O(n\log n)</math>), लेकिन सूची की लंबाई में एक स्थान की आवश्यकता [[आनुपातिकता (गणित)]] है (<math display="inline">O(n)</math>). यदि किसी दिए गए एप्लिकेशन के लिए बड़ी सूचियों को उच्च गति से क्रमबद्ध किया जाना चाहिए, तो टाइमसोर्ट एक बेहतर विकल्प है; हालाँकि, यदि छँटाई की स्मृति पदचिह्न को कम करना अधिक महत्वपूर्ण है, तो बुलबुला छँटाई एक बेहतर विकल्प है।


== पृष्ठभूमि ==
== पृष्ठभूमि ==
Line 18: Line 19:
}}</ref>
}}</ref>


प्रारंभिक [[इलेक्ट्रॉनिक कंप्यूटर]]ों में सीमित [[घड़ी चक्र]] और सीमित [[रैंडम एक्सेस मेमोरी]] दोनों थे। इसलिए, स्पेस-टाइम ट्रेड-ऑफ हुआ। एक [[टास्क (कंप्यूटिंग)]] बहुत अधिक मेमोरी का उपयोग करके एक तेज़ एल्गोरिथम का उपयोग कर सकता है, या यह कम मेमोरी का उपयोग करके एक धीमी एल्गोरिथम का उपयोग कर सकता है। इंजीनियरिंग ट्रेड-ऑफ तब सबसे तेज़ एल्गोरिथम का उपयोग करना था जो उपलब्ध मेमोरी में फिट हो सके।
प्रारंभिक [[इलेक्ट्रॉनिक कंप्यूटर|इलेक्ट्रॉनिक कंप्यूटरों]] में सीमित [[घड़ी चक्र]] और सीमित [[रैंडम एक्सेस मेमोरी]] दोनों थे। इसलिए, स्पेस-टाइम ट्रेड-ऑफ हुआ। एक [[टास्क (कंप्यूटिंग)]] बहुत अधिक मेमोरी का उपयोग करके एक तेज़ कलन विधि का उपयोग कर सकता है, या यह कम मेमोरी का उपयोग करके एक धीमी कलन विधि का उपयोग कर सकता है। इंजीनियरिंग ट्रेड-ऑफ तब सबसे तेज़ कलन विधि का उपयोग करना था जो उपलब्ध मेमोरी में फिट हो सके।


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


  स्थापित इंजीनियरिंग विषयों में 12% सुधार, आसानी से प्राप्त, को कभी भी मामूली नहीं माना जाता है और मेरा मानना ​​है कि सॉफ्टवेयर इंजीनियरिंग में समान दृष्टिकोण होना चाहिए<ref name="Knuth1974">{{
  स्थापित इंजीनियरिंग विषयों में 12% सुधार, आसानी से प्राप्त, को कभी भी मामूली नहीं माना जाता है और मेरा मानना ​​है कि सॉफ्टवेयर इंजीनियरिंग में समान दृष्टिकोण होना चाहिए<ref name="Knuth1974">{{
Line 53: Line 54:
[[Category:Pages with script errors]]
[[Category:Pages with script errors]]


== सिंहावलोकन ==
== संक्षिप्त विवरण ==
एक एल्गोरिथम को कुशल माना जाता है यदि इसकी संसाधन खपत, जिसे कम्प्यूटेशनल लागत के रूप में भी जाना जाता है, कुछ स्वीकार्य स्तर पर या उससे कम है। मोटे तौर पर, 'स्वीकार्य' का अर्थ है: यह उपलब्ध कंप्यूटर पर उचित मात्रा में समय या स्थान में चलेगा, आमतौर पर इनपुट के आकार के एक फ़ंक्शन (गणित) के रूप में। 1950 के दशक के बाद से कंप्यूटरों ने उपलब्ध कम्प्यूटेशनल शक्ति और स्मृति की उपलब्ध मात्रा दोनों में नाटकीय वृद्धि देखी है, इसलिए वर्तमान स्वीकार्य स्तर 10 साल पहले भी अस्वीकार्य रहे होंगे। वास्तव में, मूर के कानून के लिए धन्यवाद, जो कार्य आधुनिक [[स्मार्टफोन]] और [[ अंतः स्थापित प्रणाली ]] पर स्वीकार्य रूप से कुशल हैं, वे 10 साल पहले औद्योगिक [[सर्वर (कंप्यूटिंग)]] के लिए अस्वीकार्य रूप से अक्षम हो सकते हैं।
एक कलन विधि को कुशल माना जाता है यदि इसकी संसाधन खपत, जिसे संगणनात्मक लागत के रूप में भी जाना जाता है, कुछ स्वीकार्य स्तर पर या उससे कम है। मोटे तौर पर, 'स्वीकार्य' का अर्थ है: यह उपलब्ध कंप्यूटर पर उचित मात्रा में समय या स्थान में चलेगा, आमतौर पर इनपुट के आकार के एक फ़ंक्शन (गणित) के रूप में। 1950 के दशक के बाद से कंप्यूटरों ने उपलब्ध संगणनात्मक शक्ति और स्मृति की उपलब्ध मात्रा दोनों में नाटकीय वृद्धि देखी है, इसलिए वर्तमान स्वीकार्य स्तर 10 साल पहले भी अस्वीकार्य रहे होंगे। वास्तव में, मूर के कानून के लिए धन्यवाद, जो कार्य आधुनिक [[स्मार्टफोन]] और [[ अंतः स्थापित प्रणाली ]] पर स्वीकार्य रूप से कुशल हैं, वे 10 साल पहले औद्योगिक [[सर्वर (कंप्यूटिंग)]] के लिए अस्वीकार्य रूप से अक्षम हो सकते हैं।


कंप्यूटर निर्माता अक्सर उच्च [[कंप्यूटर प्रदर्शन]] के साथ अक्सर नए मॉडल पेश करते हैं। सॉफ़्टवेयर की लागत काफी अधिक हो सकती है, इसलिए कुछ मामलों में उच्च प्रदर्शन प्राप्त करने का सबसे सरल और सस्ता तरीका केवल एक तेज़ कंप्यूटर खरीदना हो सकता है, बशर्ते यह मौजूदा कंप्यूटर के साथ बैकवर्ड संगतता हो।
कंप्यूटर निर्माता प्रायः उच्च [[कंप्यूटर प्रदर्शन]] के साथ प्रायः नए मॉडल पेश करते हैं। सॉफ़्टवेयर की लागत काफी अधिक हो सकती है, इसलिए कुछ मामलों में उच्च प्रदर्शन प्राप्त करने का सबसे सरल और सस्ता तरीका केवल एक तेज़ कंप्यूटर खरीदना हो सकता है, बशर्ते यह मौजूदा कंप्यूटर के साथ बैकवर्ड संगतता हो।


ऐसे कई तरीके हैं जिनसे किसी एल्गोरिद्म द्वारा उपयोग किए गए संसाधनों को मापा जा सकता है: दो सबसे आम उपाय गति और मेमोरी उपयोग हैं; अन्य उपायों में संचरण की गति, अस्थायी डिस्क उपयोग, दीर्घकालिक डिस्क उपयोग, बिजली की खपत, स्वामित्व की कुल लागत, बाहरी उत्तेजनाओं के लिए [[प्रतिक्रिया समय (प्रौद्योगिकी)]] आदि शामिल हो सकते हैं। इनमें से कई उपाय एल्गोरिथम के इनपुट के आकार पर निर्भर करते हैं। , यानी संसाधित किए जाने वाले डेटा की मात्रा। वे उस तरीके पर भी निर्भर हो सकते हैं जिसमें डेटा को व्यवस्थित किया जाता है; उदाहरण के लिए, कुछ सॉर्टिंग एल्गोरिदम डेटा पर खराब प्रदर्शन करते हैं जो पहले से ही सॉर्ट किया गया है, या जो रिवर्स ऑर्डर में सॉर्ट किया गया है।
ऐसे कई तरीके हैं जिनसे किसी एल्गोरिद्म द्वारा उपयोग किए गए संसाधनों को मापा जा सकता है: दो सबसे आम उपाय गति और मेमोरी उपयोग हैं; अन्य उपायों में संचरण की गति, अस्थायी डिस्क उपयोग, दीर्घकालिक डिस्क उपयोग, बिजली की खपत, स्वामित्व की कुल लागत, बाहरी उत्तेजनाओं के लिए [[प्रतिक्रिया समय (प्रौद्योगिकी)]] आदि शामिल हो सकते हैं। इनमें से कई उपाय कलन विधि के इनपुट के आकार पर निर्भर करते हैं। , यानी संसाधित किए जाने वाले डेटा की मात्रा। वे उस तरीके पर भी निर्भर हो सकते हैं जिसमें डेटा को व्यवस्थित किया जाता है; उदाहरण के लिए, कुछ सॉर्टिंग कलन विधि  डेटा पर खराब प्रदर्शन करते हैं जो पहले से ही सॉर्ट किया गया है, या जो रिवर्स ऑर्डर में सॉर्ट किया गया है।


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


=== सैद्धांतिक विश्लेषण ===
=== सैद्धांतिक विश्लेषण ===
एल्गोरिदम के सैद्धांतिक विश्लेषण में, सामान्य अभ्यास यह है कि उनकी जटिलता को विषमतापूर्ण अर्थों में अनुमान लगाया जाए। संसाधन खपत या जटिलता का वर्णन करने के लिए सबसे अधिक इस्तेमाल किया जाने वाला नोटेशन डोनाल्ड नुथ का बिग ओ नोटेशन है, जो इनपुट के आकार के एक समारोह के रूप में एल्गोरिदम की जटिलता का प्रतिनिधित्व करता है। <math display="inline">n</math>. बिग ओ नोटेशन फ़ंक्शन जटिलता का एक स्पर्शोन्मुख माप है, जहाँ <math display="inline">f(n) = O\bigl( g(n)\bigr)</math> मोटे तौर पर इसका मतलब है कि एल्गोरिदम के लिए समय की आवश्यकता आनुपातिक है <math>g(n)</math>, इससे कम योगदान देने वाले निचले-क्रम के शब्दों को छोड़ दें <math>g(n)</math> समारोह की वृद्धि के रूप में <math display="inline">n</math> [[सीमा (गणित)]]। यह अनुमान भ्रामक हो सकता है जब <math display="inline">n</math> छोटा है, लेकिन आम तौर पर पर्याप्त रूप से सटीक होता है <math display="inline">n</math> बड़ा है क्योंकि अंकन स्पर्शोन्मुख है। उदाहरण के लिए, बबल सॉर्ट [[ मर्ज़ सॉर्ट ]] की तुलना में तेज़ हो सकता है जब केवल कुछ आइटम्स को सॉर्ट करना हो; हालांकि या तो कार्यान्वयन एक छोटी सूची के लिए प्रदर्शन आवश्यकताओं को पूरा करने की संभावना रखता है। आमतौर पर, प्रोग्रामर एल्गोरिदम में रुचि रखते हैं जो कि बड़े इनपुट आकारों के लिए [[ अनुमापकता ]] कुशलता से होती है, और अधिकांश डेटा-गहन कार्यक्रमों में आने वाली लंबाई की सूचियों के लिए मर्ज सॉर्ट को बबल सॉर्ट पर प्राथमिकता दी जाती है।
कलन विधि  के सैद्धांतिक विश्लेषण में, सामान्य अभ्यास यह है कि उनकी जटिलता को विषमतापूर्ण अर्थों में अनुमान लगाया जाए। संसाधन खपत या जटिलता का वर्णन करने के लिए सबसे अधिक इस्तेमाल किया जाने वाला नोटेशन डोनाल्ड नुथ का बिग ओ नोटेशन है, जो इनपुट के आकार के एक समारोह के रूप में कलन विधि  की जटिलता का प्रतिनिधित्व करता है। <math display="inline">n</math>. बिग ओ नोटेशन फ़ंक्शन जटिलता का एक स्पर्शोन्मुख माप है, जहाँ <math display="inline">f(n) = O\bigl( g(n)\bigr)</math> मोटे तौर पर इसका मतलब है कि कलन विधि  के लिए समय की आवश्यकता आनुपातिक है <math>g(n)</math>, इससे कम योगदान देने वाले निचले-क्रम के शब्दों को छोड़ दें <math>g(n)</math> समारोह की वृद्धि के रूप में <math display="inline">n</math> [[सीमा (गणित)]]। यह अनुमान भ्रामक हो सकता है जब <math display="inline">n</math> छोटा है, लेकिन आम तौर पर पर्याप्त रूप से सटीक होता है <math display="inline">n</math> बड़ा है क्योंकि अंकन स्पर्शोन्मुख है। उदाहरण के लिए, बबल सॉर्ट [[ मर्ज़ सॉर्ट ]] की तुलना में तेज़ हो सकता है जब केवल कुछ आइटम्स को सॉर्ट करना हो; हालांकि या तो कार्यान्वयन एक छोटी सूची के लिए प्रदर्शन आवश्यकताओं को पूरा करने की संभावना रखता है। आमतौर पर, प्रोग्रामर कलन विधि  में रुचि रखते हैं जो कि बड़े इनपुट आकारों के लिए [[ अनुमापकता ]] कुशलता से होती है, और अधिकांश डेटा-गहन कार्यक्रमों में आने वाली लंबाई की सूचियों के लिए मर्ज सॉर्ट को बबल सॉर्ट पर प्राथमिकता दी जाती है।


एल्गोरिथम की स्पर्शोन्मुख समय जटिलता पर लागू बिग ओ नोटेशन के कुछ उदाहरणों में शामिल हैं:
कलन विधि की स्पर्शोन्मुख समय जटिलता पर लागू बिग ओ नोटेशन के कुछ उदाहरणों में शामिल हैं:


{| class="wikitable"
{| class="wikitable"
Line 86: Line 87:


=== बेंचमार्किंग: प्रदर्शन को मापना ===
=== बेंचमार्किंग: प्रदर्शन को मापना ===
सॉफ्टवेयर के नए संस्करणों के लिए या प्रतिस्पर्धी प्रणालियों के साथ तुलना प्रदान करने के लिए, कभी-कभी [[बेंचमार्क (कंप्यूटिंग)]] का उपयोग किया जाता है, जो एल्गोरिदम के सापेक्ष प्रदर्शन को मापने में सहायता करता है। उदाहरण के लिए, यदि एक नया छँटाई एल्गोरिथम तैयार किया जाता है, तो यह सुनिश्चित करने के लिए अपने पूर्ववर्तियों के साथ तुलना की जा सकती है कि कम से कम यह ज्ञात डेटा के साथ पहले की तरह कुशल है, किसी भी कार्यात्मक सुधार को ध्यान में रखते हुए। वैकल्पिक आपूर्तिकर्ताओं से विभिन्न उत्पादों की तुलना करते समय ग्राहकों द्वारा बेंचमार्क का उपयोग किया जा सकता है ताकि यह अनुमान लगाया जा सके कि कार्यक्षमता और प्रदर्शन के मामले में कौन सा उत्पाद उनकी विशिष्ट आवश्यकताओं के अनुरूप होगा। उदाहरण के लिए, [[ मेनफ़्रेम कंप्यूटर ]] की दुनिया में कुछ मालिकाना [[मेनफ्रेम सॉर्ट मर्ज]] उत्पाद स्वतंत्र सॉफ्टवेयर कंपनियों जैसे [[सिंकसॉर्ट]] जैसे [[आईबीएम]] जैसे प्रमुख आपूर्तिकर्ताओं के उत्पादों के साथ गति के लिए प्रतिस्पर्धा करते हैं।
सॉफ्टवेयर के नए संस्करणों के लिए या प्रतिस्पर्धी प्रणालियों के साथ तुलना प्रदान करने के लिए, कभी-कभी [[बेंचमार्क (कंप्यूटिंग)]] का उपयोग किया जाता है, जो कलन विधि  के सापेक्ष प्रदर्शन को मापने में सहायता करता है। उदाहरण के लिए, यदि एक नया छँटाई कलन विधि तैयार किया जाता है, तो यह सुनिश्चित करने के लिए अपने पूर्ववर्तियों के साथ तुलना की जा सकती है कि कम से कम यह ज्ञात डेटा के साथ पहले की तरह कुशल है, किसी भी कार्यात्मक सुधार को ध्यान में रखते हुए। वैकल्पिक आपूर्तिकर्ताओं से विभिन्न उत्पादों की तुलना करते समय ग्राहकों द्वारा बेंचमार्क का उपयोग किया जा सकता है ताकि यह अनुमान लगाया जा सके कि कार्यक्षमता और प्रदर्शन के मामले में कौन सा उत्पाद उनकी विशिष्ट आवश्यकताओं के अनुरूप होगा। उदाहरण के लिए, [[ मेनफ़्रेम कंप्यूटर ]] की दुनिया में कुछ मालिकाना [[मेनफ्रेम सॉर्ट मर्ज]] उत्पाद स्वतंत्र सॉफ्टवेयर कंपनियों जैसे [[सिंकसॉर्ट]] जैसे [[आईबीएम]] जैसे प्रमुख आपूर्तिकर्ताओं के उत्पादों के साथ गति के लिए प्रतिस्पर्धा करते हैं।


कुछ मानक उदाहरण के लिए विभिन्न संकलित और व्याख्या की गई भाषाओं की सापेक्ष गति की तुलना करने वाले विश्लेषण के उत्पादन के अवसर प्रदान करते हैं<ref name="fourmilab.ch" /><ref>{{cite web|url=http://www.roylongbottom.org.uk/whetstone.htm#anchorPC2 |title=वेटस्टोन बेंचमार्क इतिहास|publisher=Roylongbottom.org.uk |access-date=14 December 2011}}</ref>
कुछ मानक उदाहरण के लिए विभिन्न संकलित और व्याख्या की गई भाषाओं की सापेक्ष गति की तुलना करने वाले विश्लेषण के उत्पादन के अवसर प्रदान करते हैं<ref name="fourmilab.ch" /><ref>{{cite web|url=http://www.roylongbottom.org.uk/whetstone.htm#anchorPC2 |title=वेटस्टोन बेंचमार्क इतिहास|publisher=Roylongbottom.org.uk |access-date=14 December 2011}}</ref>
Line 95: Line 96:


===कार्यान्वयन संबंधी चिंताएं===
===कार्यान्वयन संबंधी चिंताएं===
कार्यान्वयन के मुद्दों का दक्षता पर भी प्रभाव पड़ सकता है, जैसे कि प्रोग्रामिंग भाषा का चुनाव, या जिस तरह से एल्गोरिथ्म को वास्तव में कोडित किया जाता है,<ref name="KriegelSchubert2016">{{cite journal|last1=Kriegel|first1=Hans-Peter|author-link=Hans-Peter Kriegel|last2=Schubert|first2=Erich|last3=Zimek|first3=Arthur|author-link3=Arthur Zimek|title=The (black) art of runtime evaluation: Are we comparing algorithms or implementations?|journal=Knowledge and Information Systems|volume=52|issue=2|year=2016|pages=341–378|issn=0219-1377|doi=10.1007/s10115-016-1004-2|s2cid=40772241}}</ref> या किसी विशेष भाषा के लिए कंपाइलर का चुनाव, या इस्तेमाल किए गए [[संकलक अनुकूलन]], या यहां तक ​​कि [[ऑपरेटिंग सिस्टम]] का इस्तेमाल किया जा रहा है। कई मामलों में एक [[दुभाषिया (कंप्यूटिंग)]] द्वारा कार्यान्वित भाषा एक [[संकलक]] द्वारा कार्यान्वित भाषा की तुलना में बहुत धीमी हो सकती है।<ref name="fourmilab.ch">{{cite web|url=http://www.fourmilab.ch/fourmilog/archives/2005-08/000567.html |title=Floating Point Benchmark: Comparing Languages (Fourmilog: None Dare Call It Reason) |publisher=Fourmilab.ch |date=4 August 2005 |access-date=14 December 2011}}</ref> [[समय-समय पर संकलन]] और [[व्याख्या की गई भाषा]]ओं पर लेख देखें।
कार्यान्वयन के मुद्दों का दक्षता पर भी प्रभाव पड़ सकता है, जैसे कि प्रोग्रामिंग भाषा का चुनाव, या जिस तरह से कलन विधि को वास्तव में कोडित किया जाता है,<ref name="KriegelSchubert2016">{{cite journal|last1=Kriegel|first1=Hans-Peter|author-link=Hans-Peter Kriegel|last2=Schubert|first2=Erich|last3=Zimek|first3=Arthur|author-link3=Arthur Zimek|title=The (black) art of runtime evaluation: Are we comparing algorithms or implementations?|journal=Knowledge and Information Systems|volume=52|issue=2|year=2016|pages=341–378|issn=0219-1377|doi=10.1007/s10115-016-1004-2|s2cid=40772241}}</ref> या किसी विशेष भाषा के लिए कंपाइलर का चुनाव, या इस्तेमाल किए गए [[संकलक अनुकूलन]], या यहां तक ​​कि [[ऑपरेटिंग सिस्टम]] का इस्तेमाल किया जा रहा है। कई मामलों में एक [[दुभाषिया (कंप्यूटिंग)]] द्वारा कार्यान्वित भाषा एक [[संकलक]] द्वारा कार्यान्वित भाषा की तुलना में बहुत धीमी हो सकती है।<ref name="fourmilab.ch">{{cite web|url=http://www.fourmilab.ch/fourmilog/archives/2005-08/000567.html |title=Floating Point Benchmark: Comparing Languages (Fourmilog: None Dare Call It Reason) |publisher=Fourmilab.ch |date=4 August 2005 |access-date=14 December 2011}}</ref> [[समय-समय पर संकलन]] और [[व्याख्या की गई भाषा]]ओं पर लेख देखें।


ऐसे अन्य कारक हैं जो समय या स्थान के मुद्दों को प्रभावित कर सकते हैं, लेकिन जो एक प्रोग्रामर के नियंत्रण से बाहर हो सकते हैं; इनमें [[डेटा संरेखण]], ग्रैन्युलैरिटी # डेटा ग्रैन्युलैरिटी, संदर्भ की स्थानीयता, [[कैश सुसंगतता]], [[कचरा संग्रह (कंप्यूटर विज्ञान)]], [[निर्देश-स्तर समानता]], [[मल्टीथ्रेडिंग (बहुविकल्पी)]] शामिल हैं।<!--Intentional link to DAB page--> (या तो एक हार्डवेयर या सॉफ्टवेयर स्तर पर), [[एक साथ मल्टीथ्रेडिंग]] और [[सबरूटीन]] कॉल।<ref name="steele1997">Guy Lewis Steele, Jr. "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO". MIT AI Lab. AI Lab Memo AIM-443. October 1977.[http://dspace.mit.edu/handle/1721.1/5753]</ref>
ऐसे अन्य कारक हैं जो समय या स्थान के मुद्दों को प्रभावित कर सकते हैं, लेकिन जो एक प्रोग्रामर के नियंत्रण से बाहर हो सकते हैं; इनमें [[डेटा संरेखण]], ग्रैन्युलैरिटी # डेटा ग्रैन्युलैरिटी, संदर्भ की स्थानीयता, [[कैश सुसंगतता]], [[कचरा संग्रह (कंप्यूटर विज्ञान)]], [[निर्देश-स्तर समानता]], [[मल्टीथ्रेडिंग (बहुविकल्पी)]] शामिल हैं।<!--Intentional link to DAB page--> (या तो एक हार्डवेयर या सॉफ्टवेयर स्तर पर), [[एक साथ मल्टीथ्रेडिंग]] और [[सबरूटीन]] कॉल।<ref name="steele1997">Guy Lewis Steele, Jr. "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO". MIT AI Lab. AI Lab Memo AIM-443. October 1977.[http://dspace.mit.edu/handle/1721.1/5753]</ref>
कुछ प्रोसेसरों में [[वेक्टर प्रोसेसर]] की क्षमता होती है, जो [[SIMD]] की अनुमति देता है; प्रोग्रामर या कंपाइलर के लिए इन क्षमताओं का उपयोग करना आसान हो भी सकता है और नहीं भी। [[समानांतर कंप्यूटिंग]] का उपयोग करने के लिए अनुक्रमिक प्रसंस्करण के लिए डिज़ाइन किए गए एल्गोरिदम को पूरी तरह से फिर से डिज़ाइन करने की आवश्यकता हो सकती है, या उन्हें आसानी से पुन: कॉन्फ़िगर किया जा सकता है। जैसा कि 2010 के अंत में समानांतर कंप्यूटिंग और [[कम शक्ति कंप्यूटिंग]] का महत्व बढ़ गया है, कुशल उच्च-स्तरीय प्रोग्रामिंग भाषा में अधिक निवेश किए जा रहे हैं। CUDA, [[TensorFlow]], [[Apache Hadoop]], [[OpenMP]] और समानांतर और वितरित कंप्यूटिंग सिस्टम के लिए उच्च-स्तरीय [[अप्लिकेशन प्रोग्रामिंग अंतरफलक]] [[संदेश पासिंग इंटरफ़ेस]]।
कुछ प्रोसेसरों में [[वेक्टर प्रोसेसर]] की क्षमता होती है, जो [[SIMD]] की अनुमति देता है; प्रोग्रामर या कंपाइलर के लिए इन क्षमताओं का उपयोग करना आसान हो भी सकता है और नहीं भी। [[समानांतर कंप्यूटिंग]] का उपयोग करने के लिए अनुक्रमिक प्रसंस्करण के लिए डिज़ाइन किए गए कलन विधि  को पूरी तरह से फिर से डिज़ाइन करने की आवश्यकता हो सकती है, या उन्हें आसानी से पुन: कॉन्फ़िगर किया जा सकता है। जैसा कि 2010 के अंत में समानांतर कंप्यूटिंग और [[कम शक्ति कंप्यूटिंग]] का महत्व बढ़ गया है, कुशल उच्च-स्तरीय प्रोग्रामिंग भाषा में अधिक निवेश किए जा रहे हैं। CUDA, [[TensorFlow]], [[Apache Hadoop]], [[OpenMP]] और समानांतर और वितरित कंप्यूटिंग सिस्टम के लिए उच्च-स्तरीय [[अप्लिकेशन प्रोग्रामिंग अंतरफलक]] [[संदेश पासिंग इंटरफ़ेस]]।


एक और समस्या जो प्रोग्रामिंग में उत्पन्न हो सकती है वह यह है कि समान निर्देश [[एआरएम वास्तुकला]] (जैसे [[x86-64]] या ARM आर्किटेक्चर) के साथ संगत प्रोसेसर [[अलग]]-अलग तरीकों से एक निर्देश को लागू कर सकते हैं, ताकि निर्देश जो कुछ मॉडलों पर अपेक्षाकृत तेज़ हों, वे अपेक्षाकृत धीमे हो सकते हैं। अन्य मॉडल। यह अक्सर कंपाइलर्स को अनुकूलित करने के लिए चुनौतियों को प्रस्तुत करता है, जिसमें प्रदर्शन के लिए प्रोग्राम को सर्वोत्तम रूप से अनुकूलित करने के लिए संकलन लक्ष्य पर उपलब्ध विशिष्ट [[सेंट्रल प्रोसेसिंग यूनिट]] और अन्य हार्डवेयर का ज्ञान होना चाहिए। चरम स्थिति में, एक कंपाइलर को [[सॉफ्टवेयर अनुकरण]] निर्देशों के लिए मजबूर किया जा सकता है जो एक संकलन लक्ष्य प्लेटफॉर्म पर समर्थित नहीं है, इसे [[ कोड जनरेशन (संकलक) ]] के लिए मजबूर किया जा सकता है या बाहरी [[ पुस्तकालय (कम्प्यूटिंग) ]] को लिंक करने के लिए एक परिणाम उत्पन्न करने के लिए जो अन्यथा अकल्पनीय है। वह प्लेटफ़ॉर्म, भले ही वह मूल रूप से समर्थित हो और अन्य प्लेटफ़ॉर्म पर हार्डवेयर में अधिक कुशल हो। [[फ़्लोटिंग-पॉइंट अंकगणित]] के संबंध में एम्बेडेड सिस्टम में अक्सर ऐसा होता है, जहाँ छोटे और कम-शक्ति वाले कंप्यूटिंग | कम-शक्ति वाले [[ microcontroller ]]्स में फ़्लोटिंग-पॉइंट अंकगणित के लिए अक्सर हार्डवेयर समर्थन की कमी होती है और इस प्रकार फ़्लोटिंग पॉइंट गणनाओं का उत्पादन करने के लिए कम्प्यूटेशनल रूप से महंगे सॉफ़्टवेयर रूटीन की आवश्यकता होती है।
एक और समस्या जो प्रोग्रामिंग में उत्पन्न हो सकती है वह यह है कि समान निर्देश [[एआरएम वास्तुकला]] (जैसे [[x86-64]] या ARM आर्किटेक्चर) के साथ संगत प्रोसेसर [[अलग]]-अलग तरीकों से एक निर्देश को लागू कर सकते हैं, ताकि निर्देश जो कुछ मॉडलों पर अपेक्षाकृत तेज़ हों, वे अपेक्षाकृत धीमे हो सकते हैं। अन्य मॉडल। यह प्रायः कंपाइलर्स को अनुकूलित करने के लिए चुनौतियों को प्रस्तुत करता है, जिसमें प्रदर्शन के लिए प्रोग्राम को सर्वोत्तम रूप से अनुकूलित करने के लिए संकलन लक्ष्य पर उपलब्ध विशिष्ट [[सेंट्रल प्रोसेसिंग यूनिट]] और अन्य हार्डवेयर का ज्ञान होना चाहिए। चरम स्थिति में, एक कंपाइलर को [[सॉफ्टवेयर अनुकरण]] निर्देशों के लिए मजबूर किया जा सकता है जो एक संकलन लक्ष्य प्लेटफॉर्म पर समर्थित नहीं है, इसे [[ कोड जनरेशन (संकलक) ]] के लिए मजबूर किया जा सकता है या बाहरी [[ पुस्तकालय (कम्प्यूटिंग) ]] को लिंक करने के लिए एक परिणाम उत्पन्न करने के लिए जो अन्यथा अकल्पनीय है। वह प्लेटफ़ॉर्म, भले ही वह मूल रूप से समर्थित हो और अन्य प्लेटफ़ॉर्म पर हार्डवेयर में अधिक कुशल हो। [[फ़्लोटिंग-पॉइंट अंकगणित]] के संबंध में एम्बेडेड सिस्टम में प्रायः ऐसा होता है, जहाँ छोटे और कम-शक्ति वाले कंप्यूटिंग | कम-शक्ति वाले [[ microcontroller ]]्स में फ़्लोटिंग-पॉइंट अंकगणित के लिए प्रायः हार्डवेयर समर्थन की कमी होती है और इस प्रकार फ़्लोटिंग पॉइंट गणनाओं का उत्पादन करने के लिए संगणनात्मक रूप से महंगे सॉफ़्टवेयर रूटीन की आवश्यकता होती है।


== संसाधन उपयोग के उपाय ==
== संसाधन उपयोग के उपाय ==
Line 107: Line 108:


दो सबसे आम उपाय हैं:
दो सबसे आम उपाय हैं:
* समय: एल्गोरिथम को पूरा होने में कितना समय लगता है?
* समय: कलन विधि को पूरा होने में कितना समय लगता है?
* अंतरिक्ष: एल्गोरिथ्म द्वारा कितनी कार्यशील मेमोरी (आमतौर पर RAM) की आवश्यकता होती है? इसके दो पहलू हैं: कोड द्वारा आवश्यक मेमोरी की मात्रा (सहायक स्थान उपयोग), और उस डेटा के लिए आवश्यक मेमोरी की मात्रा जिस पर कोड संचालित होता है (आंतरिक स्थान उपयोग)।
* अंतरिक्ष: कलन विधि द्वारा कितनी कार्यशील मेमोरी (आमतौर पर RAM) की आवश्यकता होती है? इसके दो पहलू हैं: कोड द्वारा आवश्यक मेमोरी की मात्रा (सहायक स्थान उपयोग), और उस डेटा के लिए आवश्यक मेमोरी की मात्रा जिस पर कोड संचालित होता है (आंतरिक स्थान उपयोग)।


उन कंप्यूटरों के लिए जिनकी शक्ति एक बैटरी (जैसे [[लैपटॉप]] और स्मार्टफोन) द्वारा आपूर्ति की जाती है, या बहुत लंबी/बड़ी गणनाओं (जैसे [[सुपर कंप्यूटर]]) के लिए, ब्याज के अन्य उपाय हैं:
उन कंप्यूटरों के लिए जिनकी शक्ति एक बैटरी (जैसे [[लैपटॉप]] और स्मार्टफोन) द्वारा आपूर्ति की जाती है, या बहुत लंबी/बड़ी गणनाओं (जैसे [[सुपर कंप्यूटर]]) के लिए, ब्याज के अन्य उपाय हैं:
* प्रत्यक्ष बिजली की खपत: कंप्यूटर को संचालित करने के लिए सीधे बिजली की आवश्यकता होती है।
* प्रत्यक्ष बिजली की खपत: कंप्यूटर को संचालित करने के लिए प्रत्यक्ष बिजली की आवश्यकता होती है।
* अप्रत्यक्ष बिजली की खपत: ठंडा करने, प्रकाश व्यवस्था आदि के लिए आवश्यक बिजली।
* अप्रत्यक्ष बिजली की खपत: ठंडा करने, प्रकाश व्यवस्था आदि के लिए आवश्यक बिजली।


{{As of|2018}}, एम्बेडेड सिस्टम [[चीजों की इंटरनेट]] डिवाइस से लेकर [[सिस्टम- on- चिप]] डिवाइस से लेकर [[सर्वर फार्म]] तक सभी प्रकार के कम्प्यूटेशनल कार्यों और सभी पैमानों पर बिजली की खपत एक महत्वपूर्ण मीट्रिक के रूप में बढ़ रही है। इस प्रवृत्ति को अक्सर [[ हरित संगणना ]] कहा जाता है।
{{As of|2018}}, एम्बेडेड सिस्टम [[चीजों की इंटरनेट]] डिवाइस से लेकर [[सिस्टम- on- चिप]] डिवाइस से लेकर [[सर्वर फार्म]] तक सभी प्रकार के संगणनात्मक कार्यों और सभी पैमानों पर बिजली की खपत एक महत्वपूर्ण मीट्रिक के रूप में बढ़ रही है। इस प्रवृत्ति को अक्सर [[ हरित संगणना ]] कहा जाता है।


कम्प्यूटेशनल दक्षता के कम सामान्य उपाय भी कुछ मामलों में प्रासंगिक हो सकते हैं:
संगणनात्मक दक्षता के कम सामान्य उपाय भी कुछ मामलों में प्रासंगिक हो सकते हैं:


*संचरण आकार: बैंडविड्थ एक सीमित कारक हो सकता है। [[आधार - सामग्री संकोचन]] can be used to reduce the amount of data to be transmitted. Displaying a picture or image (e.g. [[:File:Google.png|Google लोगो) टेक्स्ट Google के लिए छः बाइट्स ट्रांसमिट करने की तुलना में दसियों हज़ार बाइट्स (इस मामले में 48K) ट्रांसमिट कर सकता है। I/O बाउंड कंप्यूटिंग कार्यों के लिए यह महत्वपूर्ण है।
*संचरण आकार: बैंडविड्थ एक सीमित कारक हो सकता है। [[आधार - सामग्री संकोचन]] can be used to reduce the amount of data to be transmitted. Displaying a picture or image (e.g. [[:File:Google.png|Google लोगो) टेक्स्ट Google के लिए छः बाइट्स ट्रांसमिट करने की तुलना में दसियों हज़ार बाइट्स (इस मामले में 48K) ट्रांसमिट कर सकता है। I/O बाउंड कंप्यूटिंग कार्यों के लिए यह महत्वपूर्ण है।
*बाहरी स्थान: डिस्क या अन्य बाहरी मेमोरी डिवाइस पर आवश्यक स्थान; यह अस्थायी भंडारण के लिए हो सकता है जबकि एल्गोरिथ्म किया जा रहा है, या यह भविष्य के संदर्भ के लिए आगे बढ़ने के लिए आवश्यक दीर्घकालिक भंडारण हो सकता है।
*बाहरी स्थान: डिस्क या अन्य बाहरी मेमोरी डिवाइस पर आवश्यक स्थान; यह अस्थायी भंडारण के लिए हो सकता है जबकि कलन विधि किया जा रहा है, या यह भविष्य के संदर्भ के लिए आगे बढ़ने के लिए आवश्यक दीर्घकालिक भंडारण हो सकता है।
*प्रतिक्रिया समय ([[विलंबता (इंजीनियरिंग)]]): यह विशेष रूप से [[रीयल-टाइम कंप्यूटिंग]] में वास्तविक समय अनुप्रयोग में प्रासंगिक है जब कंप्यूटर सिस्टम को [[घटना-संचालित प्रोग्रामिंग]] करना चाहिए।
*प्रतिक्रिया समय ([[विलंबता (इंजीनियरिंग)]]): यह विशेष रूप से [[रीयल-टाइम कंप्यूटिंग]] में वास्तविक समय अनुप्रयोग में प्रासंगिक है जब कंप्यूटर सिस्टम को [[घटना-संचालित प्रोग्रामिंग]] करना चाहिए।
*स्वामित्व की कुल लागत: विशेष रूप से यदि एक कंप्यूटर एक विशेष एल्गोरिथम के लिए समर्पित है।
*स्वामित्व की कुल लागत: विशेष रूप से यदि एक कंप्यूटर एक विशेष कलन विधि के लिए समर्पित है।


=== समय ===
=== समय ===
Line 127: Line 128:
==== सिद्धांत ====
==== सिद्धांत ====


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


====अभ्यास====
====अभ्यास====


एल्गोरिदम के उपयोग के समय के लिए बेंचमार्क (कंप्यूटिंग) का उपयोग करें। कई प्रोग्रामिंग भाषाओं में एक उपलब्ध फ़ंक्शन होता है जो CPU समय प्रदान करता है। लंबे समय तक चलने वाले एल्गोरिदम के लिए बीता हुआ समय भी रुचि का हो सकता है। परिणाम आम तौर पर कई परीक्षणों पर औसत होना चाहिए।
कलन विधि  के उपयोग के समय के लिए बेंचमार्क (कंप्यूटिंग) का उपयोग करें। कई प्रोग्रामिंग भाषाओं में एक उपलब्ध फ़ंक्शन होता है जो CPU समय प्रदान करता है। लंबे समय तक चलने वाले कलन विधि  के लिए बीता हुआ समय भी रुचि का हो सकता है। परिणाम आम तौर पर कई परीक्षणों पर औसत होना चाहिए।


रन-आधारित प्रोफाइलिंग हार्डवेयर कॉन्फ़िगरेशन और [[ बहु प्रसंस्करण ]] और [[ बहु प्रोग्रामिंग ]] वातावरण में एक ही समय में अन्य प्रोग्राम या कार्यों के चलने की संभावना के प्रति बहुत संवेदनशील हो सकती है।
रन-आधारित प्रोफाइलिंग हार्डवेयर कॉन्फ़िगरेशन और [[ बहु प्रसंस्करण ]] और [[ बहु प्रोग्रामिंग ]] वातावरण में एक ही समय में अन्य प्रोग्राम या कार्यों के चलने की संभावना के प्रति बहुत संवेदनशील हो सकती है।


इस प्रकार का परीक्षण एक विशेष प्रोग्रामिंग भाषा, संकलक और संकलक विकल्पों के चयन पर भी बहुत अधिक निर्भर करता है, इसलिए तुलना किए जा रहे एल्गोरिदम को समान शर्तों के तहत लागू किया जाना चाहिए।
इस प्रकार का परीक्षण एक विशेष प्रोग्रामिंग भाषा, संकलक और संकलक विकल्पों के चयन पर भी बहुत अधिक निर्भर करता है, इसलिए तुलना किए जा रहे कलन विधि  को समान शर्तों के तहत लागू किया जाना चाहिए।


=== अंतरिक्ष ===
=== अंतरिक्ष ===
यह खंड मेमोरी संसाधनों ([[प्रोसेसर रजिस्टर]], [[कैश (कंप्यूटिंग)]], [[ रैंडम एक्सेस मेमोरी ]], [[ आभासी मेमोरी ]], सहायक मेमोरी) के उपयोग से संबंधित है, जबकि एल्गोरिथ्म निष्पादित किया जा रहा है। उपरोक्त समय विश्लेषण के लिए, एल्गोरिदम का विश्लेषण एल्गोरिथ्म, आम तौर पर इनपुट डेटा के आकार के रूप में एक फ़ंक्शन के रूप में आवश्यक रन-टाइम मेमोरी का अनुमान प्राप्त करने के लिए अंतरिक्ष जटिलता विश्लेषण का उपयोग करता है। परिणाम सामान्य रूप से बिग ओ नोटेशन का उपयोग करके व्यक्त किया जाता है।
यह खंड मेमोरी संसाधनों ([[प्रोसेसर रजिस्टर]], [[कैश (कंप्यूटिंग)]], [[ रैंडम एक्सेस मेमोरी ]], [[ आभासी मेमोरी ]], सहायक मेमोरी) के उपयोग से संबंधित है, जबकि कलन विधि निष्पादित किया जा रहा है। उपरोक्त समय विश्लेषण के लिए, कलन विधि  का विश्लेषण एल्गोरिथ्म, आम तौर पर इनपुट डेटा के आकार के रूप में एक फ़ंक्शन के रूप में आवश्यक रन-टाइम मेमोरी का अनुमान प्राप्त करने के लिए अंतरिक्ष जटिलता विश्लेषण का उपयोग करता है। परिणाम सामान्य रूप से बिग ओ नोटेशन का उपयोग करके व्यक्त किया जाता है।


स्मृति उपयोग के चार पहलुओं पर विचार किया जा सकता है:
स्मृति उपयोग के चार पहलुओं पर विचार किया जा सकता है:
* एल्गोरिथ्म के लिए कोड रखने के लिए आवश्यक मेमोरी की मात्रा।
* कलन विधि के लिए कोड रखने के लिए आवश्यक मेमोरी की मात्रा।
* [[इनपुट (कंप्यूटर विज्ञान)]] के लिए आवश्यक मेमोरी की मात्रा।
* [[इनपुट (कंप्यूटर विज्ञान)]] के लिए आवश्यक मेमोरी की मात्रा।
* किसी भी [[आउटपुट (कंप्यूटिंग)]] के लिए आवश्यक मेमोरी की मात्रा।
* किसी भी [[आउटपुट (कंप्यूटिंग)]] के लिए आवश्यक मेमोरी की मात्रा।
** कुछ एल्गोरिदम, जैसे सॉर्टिंग, अक्सर [[इन-प्लेस एल्गोरिदम]] और आउटपुट डेटा के लिए किसी अतिरिक्त स्थान की आवश्यकता नहीं होती है। इस संपत्ति को इन-प्लेस एल्गोरिथम | इन-प्लेस ऑपरेशन कहा जाता है।
** कुछ कलन विधि , जैसे सॉर्टिंग, प्रायः [[इन-प्लेस एल्गोरिदम|इन-प्लेस कलन विधि]] और आउटपुट डेटा के लिए किसी अतिरिक्त स्थान की आवश्यकता नहीं होती है। इस विशेषता को इन-प्लेस कलन विधि | इन-प्लेस ऑपरेशन कहा जाता है।
* गणना के दौरान कार्य स्थान के रूप में आवश्यक मेमोरी की मात्रा।
* गणना के दौरान कार्य स्थान के रूप में आवश्यक मेमोरी की मात्रा।
** इसमें गणना के दौरान [[समारोह कॉल]] द्वारा [[स्थानीय चर]] और किसी भी स्थानीय चर, पुनरावर्तन और पुनर्वित्त शामिल हैं; यह स्टैक स्पेस एल्गोरिदम के लिए महत्वपूर्ण हो सकता है जो [[रिकर्सन (कंप्यूटर विज्ञान)]] तकनीकों का उपयोग करता है।
** इसमें गणना के दौरान [[समारोह कॉल]] द्वारा [[स्थानीय चर]] और किसी भी स्थानीय चर, पुनरावर्तन और पुनर्वित्त शामिल हैं; यह स्टैक स्पेस कलन विधि  के लिए महत्वपूर्ण हो सकता है जो [[रिकर्सन (कंप्यूटर विज्ञान)]] तकनीकों का उपयोग करता है।


शुरुआती इलेक्ट्रॉनिक कंप्यूटर और शुरुआती घरेलू कंप्यूटरों में अपेक्षाकृत कम मात्रा में कार्यशील मेमोरी थी। उदाहरण के लिए, 1949 के [[ इलेक्ट्रॉनिक विलंब संग्रहण स्वचालित कैलक्यूलेटर ]] (EDSAC) में 1024 17-बिट शब्दों की अधिकतम कार्यशील मेमोरी थी, जबकि 1980 की सिंक्लेयर [[ZX80]] शुरू में 1024 8-बिट कार्यशील मेमोरी के साथ आई थी। 2010 के अंत में, व्यक्तिगत कंप्यूटरों के लिए 4 से 32 [[गीगाबाइट]] रैम के बीच होना विशिष्ट है, 300 मिलियन गुना अधिक मेमोरी की वृद्धि।
शुरुआती इलेक्ट्रॉनिक कंप्यूटर और शुरुआती घरेलू कंप्यूटरों में अपेक्षाकृत कम मात्रा में कार्यशील मेमोरी थी। उदाहरण के लिए, 1949 के [[ इलेक्ट्रॉनिक विलंब संग्रहण स्वचालित कैलक्यूलेटर ]] (EDSAC) में 1024 17-बिट शब्दों की अधिकतम कार्यशील मेमोरी थी, जबकि 1980 की सिंक्लेयर [[ZX80]] शुरू में 1024 8-बिट कार्यशील मेमोरी के साथ आई थी। 2010 के अंत में, व्यक्तिगत कंप्यूटरों के लिए 4 से 32 [[गीगाबाइट]] रैम के बीच होना विशिष्ट है, 300 मिलियन गुना अधिक मेमोरी की वृद्धि।
Line 152: Line 153:
==== कैशिंग और मेमोरी पदानुक्रम ====
==== कैशिंग और मेमोरी पदानुक्रम ====
{{Further|Memory hierarchy}}
{{Further|Memory hierarchy}}
वर्तमान कंप्यूटरों में अपेक्षाकृत बड़ी मात्रा में मेमोरी (संभवतः गीगाबाइट्स) हो सकती है, इसलिए सीमित मात्रा में मेमोरी में एक एल्गोरिथ्म को निचोड़ना एक समस्या से बहुत कम है जो पहले हुआ करती थी। लेकिन स्मृति की चार अलग-अलग श्रेणियों की उपस्थिति महत्वपूर्ण हो सकती है:
वर्तमान कंप्यूटरों में अपेक्षाकृत बड़ी मात्रा में मेमोरी (संभवतः गीगाबाइट्स) हो सकती है, इसलिए सीमित मात्रा में मेमोरी में एक कलन विधि को निचोड़ना एक समस्या से बहुत कम है जो पहले हुआ करती थी। लेकिन स्मृति की चार अलग-अलग श्रेणियों की उपस्थिति महत्वपूर्ण हो सकती है:


* प्रोसेसर रजिस्टर करता है, कम से कम भंडारण स्थान के साथ कंप्यूटर मेमोरी प्रौद्योगिकियों का सबसे तेज। आधुनिक कंप्यूटरों पर अधिकांश प्रत्यक्ष संगणना जरूरत पड़ने पर कैश, मुख्य मेमोरी और वर्चुअल मेमोरी में अपडेट होने से पहले रजिस्टरों में स्रोत और गंतव्य ऑपरेंड के साथ होती है। [[सीपीयू कोर]] पर, आमतौर पर सैकड़ों बाइट्स या कम रजिस्टर उपलब्धता के क्रम में होते हैं, हालांकि एक [[रजिस्टर फ़ाइल]] में इंस्ट्रक्शन सेट आर्किटेक्चर में परिभाषित इंस्ट्रक्शन सेट आर्किटेक्चर रजिस्टरों की तुलना में अधिक भौतिक रजिस्टर हो सकते हैं।
* प्रोसेसर रजिस्टर करता है, कम से कम भंडारण स्थान के साथ कंप्यूटर मेमोरी प्रौद्योगिकियों का सबसे तेज। आधुनिक कंप्यूटरों पर अधिकांश प्रत्यक्ष संगणना जरूरत पड़ने पर कैश, मुख्य मेमोरी और वर्चुअल मेमोरी में अपडेट होने से पहले रजिस्टरों में स्रोत और गंतव्य ऑपरेंड के साथ होती है। [[सीपीयू कोर]] पर, आमतौर पर सैकड़ों बाइट्स या कम रजिस्टर उपलब्धता के क्रम में होते हैं, हालांकि एक [[रजिस्टर फ़ाइल]] में इंस्ट्रक्शन सेट आर्किटेक्चर में परिभाषित इंस्ट्रक्शन सेट आर्किटेक्चर रजिस्टरों की तुलना में अधिक भौतिक रजिस्टर हो सकते हैं।
* [[सीपीयू कैश]] मेमोरी पदानुक्रम में उपलब्ध दूसरी सबसे तेज और दूसरी सबसे छोटी मेमोरी है। कैश सीपीयू, जीपीयू, हार्ड डिस्क ड्राइव और बाहरी बाह्य उपकरणों में मौजूद हैं, और आमतौर पर [[स्टेटिक रैंडम-एक्सेस मेमोरी]] में लागू होते हैं। [[कैश पदानुक्रम]]|मेमोरी कैश बहु-स्तरीय हैं; [[मल्टी-कोर प्रोसेसर]] में [[प्रोसेसर कोर]] के बीच निचले स्तर बड़े, धीमे और आम तौर पर [[साझा कैश]] होते हैं। कैश मेमोरी में ऑपरेंड को संसाधित करने के लिए, एक [[प्रोसेसर (कंप्यूटिंग)]] को कैश से डेटा प्राप्त करना होगा, रजिस्टरों में ऑपरेशन करना होगा और डेटा को कैश में वापस लिखना होगा। यह सीपीयू या जीपीयू की [[अंकगणितीय तर्क इकाई]] या [[एल 1 कैश]] में [[फ्लोटिंग-पॉइंट यूनिट]] के साथ तुलनीय गति (लगभग 2-10 गुना धीमी) पर संचालित होता है।<ref name="CompArc:QuantApp">{{cite book |last1=Hennessy |first1=John L |last2=Patterson |first2=David A |last3=Asanović |first3=Krste |last4=Bakos |first4=Jason D |last5=Colwell |first5=Robert P |last6=Bhattacharjee |first6=Abhishek |last7=Conte |first7=Thomas M |last8=Duato |first8=José |last9=Franklin |first9=Diana |last10=Goldberg |first10=David |author-link11=Norman Jouppi|last11=Jouppi |first11=Norman P |last12=Li |first12=Sheng |last13=Muralimanohar |first13=Naveen |last14=Peterson |first14=Gregory D |last15=Pinkston |first15=Timothy Mark |last16=Ranganathan |first16=Prakash |last17=Wood |first17=David Allen |last18=Young |first18=Clifford |last19=Zaky |first19=Amr |title=Computer Architecture: a Quantitative Approach |date=2011 |isbn=978-0128119051 |edition=Sixth |language=en|oclc=983459758 }}</ref> यह लगभग 10 गुना धीमा है यदि कोई L1 [[कैश मिस]] है और इसे L2 कैश से पुनर्प्राप्त और लिखा जाना चाहिए, और L2 कैश मिस होने पर और 10 गुना धीमा है और इसे L3 कैश से पुनर्प्राप्त किया जाना चाहिए, यदि वर्तमान।
* [[सीपीयू कैश]] मेमोरी पदानुक्रम में उपलब्ध दूसरी सबसे तेज और दूसरी सबसे छोटी मेमोरी है। कैश सीपीयू, जीपीयू, हार्ड डिस्क ड्राइव और बाहरी बाह्य उपकरणों में मौजूद हैं, और आमतौर पर [[स्टेटिक रैंडम-एक्सेस मेमोरी]] में लागू होते हैं। [[कैश पदानुक्रम]]|मेमोरी कैश बहु-स्तरीय हैं; [[मल्टी-कोर प्रोसेसर]] में [[प्रोसेसर कोर]] के बीच निचले स्तर बड़े, धीमे और आम तौर पर [[साझा कैश]] होते हैं। कैश मेमोरी में ऑपरेंड को संसाधित करने के लिए, एक [[प्रोसेसर (कंप्यूटिंग)]] को कैश से डेटा प्राप्त करना होगा, रजिस्टरों में ऑपरेशन करना होगा और डेटा को कैश में वापस लिखना होगा। यह सीपीयू या जीपीयू की [[अंकगणितीय तर्क इकाई]] या [[एल 1 कैश]] में [[फ्लोटिंग-पॉइंट यूनिट]] के साथ तुलनीय गति (लगभग 2-10 गुना धीमी) पर संचालित होता है।<ref name="CompArc:QuantApp">{{cite book |last1=Hennessy |first1=John L |last2=Patterson |first2=David A |last3=Asanović |first3=Krste |last4=Bakos |first4=Jason D |last5=Colwell |first5=Robert P |last6=Bhattacharjee |first6=Abhishek |last7=Conte |first7=Thomas M |last8=Duato |first8=José |last9=Franklin |first9=Diana |last10=Goldberg |first10=David |author-link11=Norman Jouppi|last11=Jouppi |first11=Norman P |last12=Li |first12=Sheng |last13=Muralimanohar |first13=Naveen |last14=Peterson |first14=Gregory D |last15=Pinkston |first15=Timothy Mark |last16=Ranganathan |first16=Prakash |last17=Wood |first17=David Allen |last18=Young |first18=Clifford |last19=Zaky |first19=Amr |title=Computer Architecture: a Quantitative Approach |date=2011 |isbn=978-0128119051 |edition=Sixth |language=en|oclc=983459758 }}</ref> यह लगभग 10 गुना धीमा है यदि कोई L1 [[कैश मिस]] है और इसे L2 कैश से पुनर्प्राप्त और लिखा जाना चाहिए, और L2 कैश मिस होने पर और 10 गुना धीमा है और इसे L3 कैश से पुनर्प्राप्त किया जाना चाहिए, यदि वर्तमान।
* मुख्य मेमोरी को अक्सर [[डायनेमिक रैंडम-एक्सेस मेमोरी]] (DRAM) में लागू किया जाता है। L3 CPU कैश की तुलना में मुख्य मेमोरी बहुत बड़ी होती है (आमतौर पर ≈8 [[मेगाबाइट]]्स की तुलना में गीगाबाइट्स), पढ़ने और लिखने की विलंबता आमतौर पर 10-100 गुना धीमी होती है।<ref name="CompArc:QuantApp" /> {{As of|2018}}, RAM तेजी से सिस्टम-ऑन-चिप | प्रोसेसर के ऑन-चिप, CPU या GPU मेमोरी के रूप में कार्यान्वित किया जाता है।
* मुख्य मेमोरी को प्रायः [[डायनेमिक रैंडम-एक्सेस मेमोरी]] (DRAM) में लागू किया जाता है। L3 CPU कैश की तुलना में मुख्य मेमोरी बहुत बड़ी होती है (आमतौर पर ≈8 [[मेगाबाइट]]्स की तुलना में गीगाबाइट्स), पढ़ने और लिखने की विलंबता आमतौर पर 10-100 गुना धीमी होती है।<ref name="CompArc:QuantApp" /> {{As of|2018}}, RAM तेजी से सिस्टम-ऑन-चिप | प्रोसेसर के ऑन-चिप, CPU या GPU मेमोरी के रूप में कार्यान्वित किया जाता है।
* वर्चुअल मेमोरी को अक्सर [[ द्वितीयक भंडारण युक्ति ]] जैसे [[हार्ड डिस्क ड्राइव]] के रूप में लागू किया जाता है, और मेमोरी पदानुक्रम का विस्तार होता है जिसमें बहुत अधिक स्टोरेज स्पेस होता है, लेकिन बहुत बड़ी लेटेंसी होती है, आमतौर पर एक कैश मिस की तुलना में लगभग 1000 गुना धीमी होती है। रैम में मूल्य।<ref name="CompArc:QuantApp" />जबकि मूल रूप से वास्तव में उपलब्ध होने की तुलना में अधिक मात्रा में मेमोरी उपलब्ध होने का आभास पैदा करने के लिए प्रेरित किया गया था, वर्चुअल मेमोरी अपने [[टाइम-स्पेस ट्रेडऑफ़]] और [[ आभासी मशीन ]]ों के उपयोग को सक्षम करने के लिए समकालीन उपयोग में अधिक महत्वपूर्ण है।<ref name="CompArc:QuantApp" />मुख्य मेमोरी से कैश की कमी को [[पृष्ठ दोष]] कहा जाता है, और कार्यक्रमों पर भारी प्रदर्शन दंड लगता है।
* वर्चुअल मेमोरी को अक्सर [[ द्वितीयक भंडारण युक्ति ]] जैसे [[हार्ड डिस्क ड्राइव]] के रूप में लागू किया जाता है, और मेमोरी पदानुक्रम का विस्तार होता है जिसमें बहुत अधिक स्टोरेज स्पेस होता है, लेकिन बहुत बड़ी लेटेंसी होती है, आमतौर पर एक कैश मिस की तुलना में लगभग 1000 गुना धीमी होती है। रैम में मूल्य।<ref name="CompArc:QuantApp" />जबकि मूल रूप से वास्तव में उपलब्ध होने की तुलना में अधिक मात्रा में मेमोरी उपलब्ध होने का आभास पैदा करने के लिए प्रेरित किया गया था, वर्चुअल मेमोरी अपने [[टाइम-स्पेस ट्रेडऑफ़]] और [[ आभासी मशीन ]]ों के उपयोग को सक्षम करने के लिए समकालीन उपयोग में अधिक महत्वपूर्ण है।<ref name="CompArc:QuantApp" />मुख्य मेमोरी से कैश की कमी को [[पृष्ठ दोष]] कहा जाता है, और कार्यक्रमों पर भारी प्रदर्शन दंड लगता है।


एक एल्गोरिथम जिसकी मेमोरी की जरूरत कैश मेमोरी में फिट होगी, एक एल्गोरिथम की तुलना में बहुत तेज होगी जो मुख्य मेमोरी में फिट होती है, जो बदले में एक एल्गोरिथम की तुलना में बहुत तेज होगी जिसे वर्चुअल मेमोरी का सहारा लेना पड़ता है। इस वजह से, [[कैश प्रतिस्थापन नीतियां]] उच्च-प्रदर्शन कंप्यूटिंग के लिए बेहद महत्वपूर्ण हैं, जैसे [[कैश-जागरूक मॉडल]]|कैश-जागरूक प्रोग्रामिंग और [[डेटा संरचना संरेखण]]। समस्या को और जटिल करने के लिए, कुछ सिस्टम में अलग-अलग प्रभावी गति के साथ कैश मेमोरी के तीन स्तर तक होते हैं। अलग-अलग प्रणालियों में इन विभिन्न प्रकार की मेमोरी की अलग-अलग मात्रा होगी, इसलिए एल्गोरिथम मेमोरी की ज़रूरतों का प्रभाव एक सिस्टम से दूसरे सिस्टम में बहुत भिन्न हो सकता है।
एक कलन विधि जिसकी मेमोरी की जरूरत कैश मेमोरी में फिट होगी, एक कलन विधि की तुलना में बहुत तेज होगी जो मुख्य मेमोरी में फिट होती है, जो बदले में एक कलन विधि की तुलना में बहुत तेज होगी जिसे वर्चुअल मेमोरी का सहारा लेना पड़ता है। इस वजह से, [[कैश प्रतिस्थापन नीतियां]] उच्च-प्रदर्शन कंप्यूटिंग के लिए बेहद महत्वपूर्ण हैं, जैसे [[कैश-जागरूक मॉडल]]|कैश-जागरूक प्रोग्रामिंग और [[डेटा संरचना संरेखण]]। समस्या को और जटिल करने के लिए, कुछ सिस्टम में अलग-अलग प्रभावी गति के साथ कैश मेमोरी के तीन स्तर तक होते हैं। अलग-अलग प्रणालियों में इन विभिन्न प्रकार की मेमोरी की अलग-अलग मात्रा होगी, इसलिए कलन विधि मेमोरी की ज़रूरतों का प्रभाव एक सिस्टम से दूसरे सिस्टम में बहुत भिन्न हो सकता है।


इलेक्ट्रॉनिक कंप्यूटिंग के शुरुआती दिनों में, यदि एक एल्गोरिथम और उसका डेटा मुख्य मेमोरी में फिट नहीं होगा, तो एल्गोरिथम का उपयोग नहीं किया जा सकता था। आजकल वर्चुअल मेमोरी का उपयोग अधिक मेमोरी प्रदान करता प्रतीत होता है, लेकिन प्रदर्शन की कीमत पर। यदि एक एल्गोरिथम और उसका डेटा कैश मेमोरी में फिट हो जाएगा, तो बहुत तेज गति प्राप्त की जा सकती है; इस मामले में जगह कम करने से समय कम करने में भी मदद मिलेगी। इसे [[स्थानीयता का सिद्धांत]] कहा जाता है, और इसे संदर्भ के इलाके, स्थानिक इलाके और लौकिक इलाके में विभाजित किया जा सकता है। एक एल्गोरिथ्म जो पूरी तरह से कैश मेमोरी में फिट नहीं होगा, लेकिन जो संदर्भ की स्थानीयता प्रदर्शित करता है, यथोचित अच्छा प्रदर्शन कर सकता है।
इलेक्ट्रॉनिक कंप्यूटिंग के शुरुआती दिनों में, यदि एक कलन विधि और उसका डेटा मुख्य मेमोरी में फिट नहीं होगा, तो कलन विधि का उपयोग नहीं किया जा सकता था। आजकल वर्चुअल मेमोरी का उपयोग अधिक मेमोरी प्रदान करता प्रतीत होता है, लेकिन प्रदर्शन की कीमत पर। यदि एक कलन विधि और उसका डेटा कैश मेमोरी में फिट हो जाएगा, तो बहुत तेज गति प्राप्त की जा सकती है; इस मामले में जगह कम करने से समय कम करने में भी मदद मिलेगी। इसे [[स्थानीयता का सिद्धांत]] कहा जाता है, और इसे संदर्भ के इलाके, स्थानिक इलाके और लौकिक इलाके में विभाजित किया जा सकता है। एक कलन विधि जो पूरी तरह से कैश मेमोरी में फिट नहीं होगा, लेकिन जो संदर्भ की स्थानीयता प्रदर्शित करता है, यथोचित अच्छा प्रदर्शन कर सकता है।


== प्रोग्रामिंग की वर्तमान स्थिति की आलोचना ==
== प्रोग्रामिंग की वर्तमान स्थिति की आलोचना ==
Line 172: Line 173:


<ब्लॉककोट>
<ब्लॉककोट>
सर्वव्यापी प्रणालियों में, निष्पादित निर्देशों को आधा करने से बैटरी जीवन दोगुना हो सकता है और बड़े डेटा सेट बेहतर सॉफ्टवेयर और एल्गोरिदम के लिए बड़े अवसर लाते हैं: एन से संचालन की संख्या कम करना{{times}}एन से एन{{times}}log(N) का एक नाटकीय प्रभाव होता है जब N बड़ा होता है ... N = 30 बिलियन के लिए, यह परिवर्तन 50 वर्षों के तकनीकी सुधार के बराबर है।
सर्वव्यापी प्रणालियों में, निष्पादित निर्देशों को आधा करने से बैटरी जीवन दोगुना हो सकता है और बड़े डेटा सेट बेहतर सॉफ्टवेयर और कलन विधि  के लिए बड़े अवसर लाते हैं: एन से संचालन की संख्या कम करना{{times}}एन से एन{{times}}log(N) का एक नाटकीय प्रभाव होता है जब N बड़ा होता है ... N = 30 बिलियन के लिए, यह परिवर्तन 50 वर्षों के तकनीकी सुधार के बराबर है।
</ब्लॉककोट>
</ब्लॉककोट>


* सॉफ्टवेयर लेखक एडम एन. रोसेनबर्ग ने अपने ब्लॉग द फेलियर ऑफ द डिजिटल कंप्यूटर में प्रोग्रामिंग की वर्तमान स्थिति को सॉफ्टवेयर इवेंट क्षितिज के करीब बताया है, ([[डगलस एडम्स]] द्वारा अपने हिचहाइकर गाइड टू द गैलेक्सी में वर्णित काल्पनिक शू इवेंट क्षितिज की ओर इशारा करते हुए) किताब<ref>{{Cite web | url=http://www.the-adam.com/adam/rantrave/computers.htm | title=The Failure of the Digital Computer}}</ref>). उनका अनुमान है कि 1980 के दशक से उत्पादकता में 70 dB कारक हानि या माल वितरित करने की इसकी क्षमता का 99.99999 प्रतिशत रहा है— जब आर्थर सी. क्लार्क ने 2001 में अपनी पुस्तक 2001 में कंप्यूटर [[HAL 9000]] से कंप्यूटिंग की वास्तविकता की तुलना की: एक स्पेस ओडिसी, उन्होंने बताया कि कितने आश्चर्यजनक रूप से छोटे और शक्तिशाली कंप्यूटर थे लेकिन कंप्यूटर प्रोग्रामिंग कितनी निराशाजनक हो गई थी।
* सॉफ्टवेयर लेखक एडम एन. रोसेनबर्ग ने अपने ब्लॉग द फेलियर ऑफ द डिजिटल कंप्यूटर में प्रोग्रामिंग की वर्तमान स्थिति को सॉफ्टवेयर इवेंट क्षितिज के करीब बताया है, ([[डगलस एडम्स]] द्वारा अपने हिचहाइकर गाइड टू द गैलेक्सी में वर्णित काल्पनिक शू इवेंट क्षितिज की ओर इशारा करते हुए) किताब<ref>{{Cite web | url=http://www.the-adam.com/adam/rantrave/computers.htm | title=The Failure of the Digital Computer}}</ref>). उनका अनुमान है कि 1980 के दशक से उत्पादकता में 70 dB कारक हानि या माल वितरित करने की इसकी क्षमता का 99.99999 प्रतिशत रहा है— जब आर्थर सी. क्लार्क ने 2001 में अपनी पुस्तक 2001 में कंप्यूटर [[HAL 9000]] से कंप्यूटिंग की वास्तविकता की तुलना की: एक स्पेस ओडिसी, उन्होंने बताया कि कितने आश्चर्यजनक रूप से छोटे और शक्तिशाली कंप्यूटर थे लेकिन कंप्यूटर प्रोग्रामिंग कितनी निराशाजनक हो गई थी।


==सर्वश्रेष्ठ एल्गोरिदम के लिए प्रतियोगिताएं==
==सर्वश्रेष्ठ कलन विधि  के लिए प्रतियोगिताएं==
निम्नलिखित प्रतियोगिताओं में न्यायाधीशों द्वारा तय किए गए कुछ मनमाने मानदंडों के आधार पर सर्वश्रेष्ठ एल्गोरिदम के लिए प्रविष्टियां आमंत्रित की जाती हैं:
निम्नलिखित प्रतियोगिताओं में न्यायाधीशों द्वारा तय किए गए कुछ मनमाने मानदंडों के आधार पर सर्वश्रेष्ठ कलन विधि  के लिए प्रविष्टियां आमंत्रित की जाती हैं:
* [[वायर्ड पत्रिका]]<ref>{{cite magazine| url=https://www.wired.com/magazine/2010/11/mf_algorithmolympics/all/1 | magazine=Wired | first=Jason | last=Fagone | title=एल्गोरिथम ओलंपिक में टीन मैथलेट्स का मुकाबला| date=29 November 2010}}</ref>
* [[वायर्ड पत्रिका]]<ref>{{cite magazine| url=https://www.wired.com/magazine/2010/11/mf_algorithmolympics/all/1 | magazine=Wired | first=Jason | last=Fagone | title=एल्गोरिथम ओलंपिक में टीन मैथलेट्स का मुकाबला| date=29 November 2010}}</ref>




== यह भी देखें ==
== यह भी देखें ==
* एल्गोरिदम का विश्लेषण- एल्गोरिदम द्वारा आवश्यक संसाधनों का निर्धारण कैसे करें
* कलन विधि  का विश्लेषण- कलन विधि  द्वारा आवश्यक संसाधनों का निर्धारण कैसे करें
* [[अंकगणितीय कोडिंग]]- [[चर-लंबाई कोड]] का एक रूप | कुशल डेटा संपीड़न के लिए चर-लंबाई [[एंट्रॉपी एन्कोडिंग]]
* [[अंकगणितीय कोडिंग]]- [[चर-लंबाई कोड]] का एक रूप | कुशल डेटा संपीड़न के लिए चर-लंबाई [[एंट्रॉपी एन्कोडिंग]]
* [[साहचर्य सरणी]]—एक डेटा संरचना जिसे [[पेट्रीसिया का पेड़]] या जूडी सरणियों का उपयोग करके अधिक कुशल बनाया जा सकता है
* [[साहचर्य सरणी]]—एक डेटा संरचना जिसे [[पेट्रीसिया का पेड़]] या जूडी सरणियों का उपयोग करके अधिक कुशल बनाया जा सकता है
Line 189: Line 190:
* सबसे अच्छा, सबसे खराब और औसत मामला- तीन परिदृश्यों में निष्पादन समय का अनुमान लगाने के लिए विचार
* सबसे अच्छा, सबसे खराब और औसत मामला- तीन परिदृश्यों में निष्पादन समय का अनुमान लगाने के लिए विचार
* [[बाइनरी सर्च एल्गोरिथम]]- सॉर्ट की गई सरणियों को खोजने के लिए एक सरल और कुशल तकनीक
* [[बाइनरी सर्च एल्गोरिथम]]- सॉर्ट की गई सरणियों को खोजने के लिए एक सरल और कुशल तकनीक
* [[शाखा तालिका]] - निर्देश पथ-लंबाई, [[मशीन कोड]] का आकार, (और अक्सर स्मृति भी) को कम करने के लिए एक तकनीक
* [[शाखा तालिका]] - निर्देश पथ-लंबाई, [[मशीन कोड]] का आकार, (और प्रायः स्मृति भी) को कम करने के लिए एक तकनीक
* [[प्रोग्रामिंग प्रतिमानों की तुलना]]-प्रतिमान विशिष्ट प्रदर्शन विचार
* [[प्रोग्रामिंग प्रतिमानों की तुलना]]-प्रतिमान विशिष्ट प्रदर्शन विचार
* संकलक अनुकूलन—संकलक-व्युत्पन्न अनुकूलन
* संकलक अनुकूलन—संकलक-व्युत्पन्न अनुकूलन
* [[गणितीय कार्यों की कम्प्यूटेशनल जटिलता]]
* [[गणितीय कार्यों की कम्प्यूटेशनल जटिलता|गणितीय कार्यों की संगणनात्मक जटिलता]]
* [[कम्प्यूटेशनल जटिलता सिद्धांत]]
* [[कम्प्यूटेशनल जटिलता सिद्धांत|संगणनात्मक जटिलता सिद्धांत]]
* कंप्यूटर प्रदर्शन-कंप्यूटर हार्डवेयर मेट्रिक्स
* कंप्यूटर प्रदर्शन-कंप्यूटर हार्डवेयर मेट्रिक्स
* डेटा कंप्रेशन- ट्रांसमिशन बैंडविड्थ और डिस्क स्टोरेज को कम करना
* डेटा कंप्रेशन- ट्रांसमिशन बैंडविड्थ और डिस्क स्टोरेज को कम करना
Line 200: Line 201:
* कचरा संग्रह (कंप्यूटर विज्ञान) - उपयोग के बाद स्मृति को स्वत: मुक्त करना
* कचरा संग्रह (कंप्यूटर विज्ञान) - उपयोग के बाद स्मृति को स्वत: मुक्त करना
* हरित कंप्यूटिंग- कम संसाधनों की खपत वाली 'हरित' तकनीकों को लागू करने का एक कदम
* हरित कंप्यूटिंग- कम संसाधनों की खपत वाली 'हरित' तकनीकों को लागू करने का एक कदम
* [[हफ़मैन एल्गोरिथम]] डेटा एन्कोडिंग के लिए एक एल्गोरिद्म
* [[हफ़मैन एल्गोरिथम|हफ़मैन]] कलन विधि डेटा एन्कोडिंग के लिए एक एल्गोरिद्म
* [http://msdn.microsoft.com/en-us/library/ff647790.aspx प्रबंधित कोड प्रदर्शन में सुधार]—माइक्रोसॉफ्ट MSDN लाइब्रेरी
* [http://msdn.microsoft.com/en-us/library/ff647790.aspx प्रबंधित कोड प्रदर्शन में सुधार]—माइक्रोसॉफ्ट MSDN लाइब्रेरी
* संदर्भ की लोकैलिटी- गैर-स्थानीय मेमोरी एक्सेस के कारण सीपीयू कैश देरी से बचने के लिए
* संदर्भ की लोकैलिटी- गैर-स्थानीय मेमोरी एक्सेस के कारण सीपीयू कैश देरी से बचने के लिए
Line 206: Line 207:
* [[स्मृति प्रबंधन]]
* [[स्मृति प्रबंधन]]
* अनुकूलन (कंप्यूटर विज्ञान)
* अनुकूलन (कंप्यूटर विज्ञान)
* [[ रूपरेखा (कंप्यूटर प्रोग्रामिंग) ]] - रन-टाइम पर एक एल्गोरिथ्म के वास्तविक प्रदर्शन को मापने के तरीके
* [[ रूपरेखा (कंप्यूटर प्रोग्रामिंग) ]] - रन-टाइम पर एक कलन विधि के वास्तविक प्रदर्शन को मापने के तरीके
* रीयल-टाइम कंप्यूटिंग- समय-महत्वपूर्ण अनुप्रयोगों के और उदाहरण
* रीयल-टाइम कंप्यूटिंग- समय-महत्वपूर्ण अनुप्रयोगों के और उदाहरण
* [[रन-टाइम विश्लेषण]]-अपेक्षित रन-टाइम का अनुमान और एल्गोरिथम की मापनीयता
* [[रन-टाइम विश्लेषण]]-अपेक्षित रन-टाइम का अनुमान और कलन विधि की मापनीयता
* एक साथ मल्टीथ्रेडिंग
* एक साथ मल्टीथ्रेडिंग
* {{section link|Sorting algorithm|Comparison of algorithms}}
* {{section link|Sorting algorithm|Comparison of algorithms}}

Revision as of 11:12, 10 May 2023

Not to be confused with optimization, which is discussed in program optimization, optimizing compiler, loop optimization, object code optimizer, etc..

कंप्यूटर विज्ञान में, कलन विधि दक्षता कलन विधि की एक विशेषता है जो कलन विधि द्वारा उपयोग किए जाने वाले संगणनात्मक संसाधनों की मात्रा से संबंधित है। एक कलन विधि को अपने संसाधन के उपयोग को निर्धारित करने के लिए कलन विधि का विश्लेषण करना चाहिए, और एक कलन विधि की दक्षता को विभिन्न संसाधनों के उपयोग के आधार पर मापा जा सकता है। एक पुनरावृत्ति की जाने वाली या सतत प्रक्रिया के लिए कलनविधीय दक्षता को इंजीनियरिंग उत्पादकता के अनुरूप माना जा सकता है।

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

उदाहरण के लिए, बुलबुले सॉर्ट और टाइमसॉर्ट दोनों ही छोटे से बड़े आइटम की छँटाई कलन विधि हैं जो वस्तुओं की सूची को सबसे छोटे से सबसे बड़े तक क्रमबद्ध करते हैं। बबल सॉर्ट समय में सूची को चुकता तत्वों की संख्या के अनुपात में क्रमबद्ध करता है (, बिग ओ नोटेशन देखें), लेकिन केवल थोड़ी मात्रा में अतिरिक्त मेमोरी की आवश्यकता होती है जो सूची की लंबाई के संबंध में स्थिर होती है (). टिम्सोर्ट सूची को समय के अनुसार क्रमबद्ध करता है (इसके लघुगणक की मात्रा के गुणन के अनुपात में) सूची की लंबाई में (), लेकिन सूची की लंबाई में एक स्थान की आवश्यकता आनुपातिकता (गणित) है (). यदि किसी दिए गए एप्लिकेशन के लिए बड़ी सूचियों को उच्च गति से क्रमबद्ध किया जाना चाहिए, तो टाइमसोर्ट एक बेहतर विकल्प है; हालाँकि, यदि छँटाई की स्मृति पदचिह्न को कम करना अधिक महत्वपूर्ण है, तो बुलबुला छँटाई एक बेहतर विकल्प है।

पृष्ठभूमि

1843 में चार्ल्स बैबेज के यांत्रिक विश्लेषणात्मक इंजन के लिए लवलेस है द्वारा समय के संबंध में दक्षता के महत्व पर जोर दिया गया था: 

लगभग हर संगणना में प्रक्रियाओं के उत्तराधिकार के लिए एक महान विविधता की व्यवस्था संभव है, और विभिन्न विचारों को गणना इंजन के प्रयोजनों के लिए उनके बीच चयन को प्रभावित करना चाहिए। एक आवश्यक वस्तु उस व्यवस्था को चुनना है जो गणना को पूरा करने के लिए आवश्यक न्यूनतम समय को कम करने की ओर अग्रसर हो[1]

प्रारंभिक इलेक्ट्रॉनिक कंप्यूटरों में सीमित घड़ी चक्र और सीमित रैंडम एक्सेस मेमोरी दोनों थे। इसलिए, स्पेस-टाइम ट्रेड-ऑफ हुआ। एक टास्क (कंप्यूटिंग) बहुत अधिक मेमोरी का उपयोग करके एक तेज़ कलन विधि का उपयोग कर सकता है, या यह कम मेमोरी का उपयोग करके एक धीमी कलन विधि का उपयोग कर सकता है। इंजीनियरिंग ट्रेड-ऑफ तब सबसे तेज़ कलन विधि का उपयोग करना था जो उपलब्ध मेमोरी में फिट हो सके।

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

स्थापित इंजीनियरिंग विषयों में 12% सुधार, आसानी से प्राप्त, को कभी भी मामूली नहीं माना जाता है और मेरा मानना ​​है कि सॉफ्टवेयर इंजीनियरिंग में समान दृष्टिकोण होना चाहिए[2]</ब्लॉककोट>

संक्षिप्त विवरण

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

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

ऐसे कई तरीके हैं जिनसे किसी एल्गोरिद्म द्वारा उपयोग किए गए संसाधनों को मापा जा सकता है: दो सबसे आम उपाय गति और मेमोरी उपयोग हैं; अन्य उपायों में संचरण की गति, अस्थायी डिस्क उपयोग, दीर्घकालिक डिस्क उपयोग, बिजली की खपत, स्वामित्व की कुल लागत, बाहरी उत्तेजनाओं के लिए प्रतिक्रिया समय (प्रौद्योगिकी) आदि शामिल हो सकते हैं। इनमें से कई उपाय कलन विधि के इनपुट के आकार पर निर्भर करते हैं। , यानी संसाधित किए जाने वाले डेटा की मात्रा। वे उस तरीके पर भी निर्भर हो सकते हैं जिसमें डेटा को व्यवस्थित किया जाता है; उदाहरण के लिए, कुछ सॉर्टिंग कलन विधि डेटा पर खराब प्रदर्शन करते हैं जो पहले से ही सॉर्ट किया गया है, या जो रिवर्स ऑर्डर में सॉर्ट किया गया है।

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

सैद्धांतिक विश्लेषण

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

कलन विधि की स्पर्शोन्मुख समय जटिलता पर लागू बिग ओ नोटेशन के कुछ उदाहरणों में शामिल हैं:

Notation Name Examples
constant Finding the median from a sorted list of measurements; Using a constant-size lookup table; Using a suitable hash function for looking up an item.
logarithmic Finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a Binomial heap.
linear Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; Adding two n-bit integers by ripple carry.
linearithmic, loglinear, or quasilinear Performing a Fast Fourier transform; heapsort, quicksort (best and average case), or merge sort
quadratic Multiplying two n-digit numbers by a simple algorithm; bubble sort (worst case or naive implementation), Shell sort, quicksort (worst case), selection sort or insertion sort
exponential Finding the optimal (non-approximate) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search


बेंचमार्किंग: प्रदर्शन को मापना

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

कुछ मानक उदाहरण के लिए विभिन्न संकलित और व्याख्या की गई भाषाओं की सापेक्ष गति की तुलना करने वाले विश्लेषण के उत्पादन के अवसर प्रदान करते हैं[3][4] कंप्यूटर भाषा बेंचमार्क गेम कई प्रोग्रामिंग भाषाओं में विशिष्ट प्रोग्रामिंग समस्याओं के कार्यान्वयन के प्रदर्शन की तुलना करता है।

यहां तक ​​कि यह अपने आप करो बनाना बेंचमार्क विभिन्न प्रकार के उपयोगकर्ता निर्दिष्ट मानदंडों का उपयोग करके विभिन्न प्रोग्रामिंग भाषाओं के सापेक्ष प्रदर्शन को प्रदर्शित कर सकता है। यह काफी सरल है, जैसा कि क्रिस्टोफर डब्ल्यू. कॉवेल-शाह द्वारा नौ भाषा प्रदर्शन राउंडअप उदाहरण द्वारा प्रदर्शित करता है।[5]


कार्यान्वयन संबंधी चिंताएं

कार्यान्वयन के मुद्दों का दक्षता पर भी प्रभाव पड़ सकता है, जैसे कि प्रोग्रामिंग भाषा का चुनाव, या जिस तरह से कलन विधि को वास्तव में कोडित किया जाता है,[6] या किसी विशेष भाषा के लिए कंपाइलर का चुनाव, या इस्तेमाल किए गए संकलक अनुकूलन, या यहां तक ​​कि ऑपरेटिंग सिस्टम का इस्तेमाल किया जा रहा है। कई मामलों में एक दुभाषिया (कंप्यूटिंग) द्वारा कार्यान्वित भाषा एक संकलक द्वारा कार्यान्वित भाषा की तुलना में बहुत धीमी हो सकती है।[3] समय-समय पर संकलन और व्याख्या की गई भाषाओं पर लेख देखें।

ऐसे अन्य कारक हैं जो समय या स्थान के मुद्दों को प्रभावित कर सकते हैं, लेकिन जो एक प्रोग्रामर के नियंत्रण से बाहर हो सकते हैं; इनमें डेटा संरेखण, ग्रैन्युलैरिटी # डेटा ग्रैन्युलैरिटी, संदर्भ की स्थानीयता, कैश सुसंगतता, कचरा संग्रह (कंप्यूटर विज्ञान), निर्देश-स्तर समानता, मल्टीथ्रेडिंग (बहुविकल्पी) शामिल हैं। (या तो एक हार्डवेयर या सॉफ्टवेयर स्तर पर), एक साथ मल्टीथ्रेडिंग और सबरूटीन कॉल।[7] कुछ प्रोसेसरों में वेक्टर प्रोसेसर की क्षमता होती है, जो SIMD की अनुमति देता है; प्रोग्रामर या कंपाइलर के लिए इन क्षमताओं का उपयोग करना आसान हो भी सकता है और नहीं भी। समानांतर कंप्यूटिंग का उपयोग करने के लिए अनुक्रमिक प्रसंस्करण के लिए डिज़ाइन किए गए कलन विधि को पूरी तरह से फिर से डिज़ाइन करने की आवश्यकता हो सकती है, या उन्हें आसानी से पुन: कॉन्फ़िगर किया जा सकता है। जैसा कि 2010 के अंत में समानांतर कंप्यूटिंग और कम शक्ति कंप्यूटिंग का महत्व बढ़ गया है, कुशल उच्च-स्तरीय प्रोग्रामिंग भाषा में अधिक निवेश किए जा रहे हैं। CUDA, TensorFlow, Apache Hadoop, OpenMP और समानांतर और वितरित कंप्यूटिंग सिस्टम के लिए उच्च-स्तरीय अप्लिकेशन प्रोग्रामिंग अंतरफलक संदेश पासिंग इंटरफ़ेस।

एक और समस्या जो प्रोग्रामिंग में उत्पन्न हो सकती है वह यह है कि समान निर्देश एआरएम वास्तुकला (जैसे x86-64 या ARM आर्किटेक्चर) के साथ संगत प्रोसेसर अलग-अलग तरीकों से एक निर्देश को लागू कर सकते हैं, ताकि निर्देश जो कुछ मॉडलों पर अपेक्षाकृत तेज़ हों, वे अपेक्षाकृत धीमे हो सकते हैं। अन्य मॉडल। यह प्रायः कंपाइलर्स को अनुकूलित करने के लिए चुनौतियों को प्रस्तुत करता है, जिसमें प्रदर्शन के लिए प्रोग्राम को सर्वोत्तम रूप से अनुकूलित करने के लिए संकलन लक्ष्य पर उपलब्ध विशिष्ट सेंट्रल प्रोसेसिंग यूनिट और अन्य हार्डवेयर का ज्ञान होना चाहिए। चरम स्थिति में, एक कंपाइलर को सॉफ्टवेयर अनुकरण निर्देशों के लिए मजबूर किया जा सकता है जो एक संकलन लक्ष्य प्लेटफॉर्म पर समर्थित नहीं है, इसे कोड जनरेशन (संकलक) के लिए मजबूर किया जा सकता है या बाहरी पुस्तकालय (कम्प्यूटिंग) को लिंक करने के लिए एक परिणाम उत्पन्न करने के लिए जो अन्यथा अकल्पनीय है। वह प्लेटफ़ॉर्म, भले ही वह मूल रूप से समर्थित हो और अन्य प्लेटफ़ॉर्म पर हार्डवेयर में अधिक कुशल हो। फ़्लोटिंग-पॉइंट अंकगणित के संबंध में एम्बेडेड सिस्टम में प्रायः ऐसा होता है, जहाँ छोटे और कम-शक्ति वाले कंप्यूटिंग | कम-शक्ति वाले microcontroller ्स में फ़्लोटिंग-पॉइंट अंकगणित के लिए प्रायः हार्डवेयर समर्थन की कमी होती है और इस प्रकार फ़्लोटिंग पॉइंट गणनाओं का उत्पादन करने के लिए संगणनात्मक रूप से महंगे सॉफ़्टवेयर रूटीन की आवश्यकता होती है।

संसाधन उपयोग के उपाय

उपाय आम तौर पर इनपुट के आकार के एक समारोह के रूप में व्यक्त किए जाते हैं .

दो सबसे आम उपाय हैं:

  • समय: कलन विधि को पूरा होने में कितना समय लगता है?
  • अंतरिक्ष: कलन विधि द्वारा कितनी कार्यशील मेमोरी (आमतौर पर RAM) की आवश्यकता होती है? इसके दो पहलू हैं: कोड द्वारा आवश्यक मेमोरी की मात्रा (सहायक स्थान उपयोग), और उस डेटा के लिए आवश्यक मेमोरी की मात्रा जिस पर कोड संचालित होता है (आंतरिक स्थान उपयोग)।

उन कंप्यूटरों के लिए जिनकी शक्ति एक बैटरी (जैसे लैपटॉप और स्मार्टफोन) द्वारा आपूर्ति की जाती है, या बहुत लंबी/बड़ी गणनाओं (जैसे सुपर कंप्यूटर) के लिए, ब्याज के अन्य उपाय हैं:

  • प्रत्यक्ष बिजली की खपत: कंप्यूटर को संचालित करने के लिए प्रत्यक्ष बिजली की आवश्यकता होती है।
  • अप्रत्यक्ष बिजली की खपत: ठंडा करने, प्रकाश व्यवस्था आदि के लिए आवश्यक बिजली।

As of 2018, एम्बेडेड सिस्टम चीजों की इंटरनेट डिवाइस से लेकर सिस्टम- on- चिप डिवाइस से लेकर सर्वर फार्म तक सभी प्रकार के संगणनात्मक कार्यों और सभी पैमानों पर बिजली की खपत एक महत्वपूर्ण मीट्रिक के रूप में बढ़ रही है। इस प्रवृत्ति को अक्सर हरित संगणना कहा जाता है।

संगणनात्मक दक्षता के कम सामान्य उपाय भी कुछ मामलों में प्रासंगिक हो सकते हैं:

  • संचरण आकार: बैंडविड्थ एक सीमित कारक हो सकता है। आधार - सामग्री संकोचन can be used to reduce the amount of data to be transmitted. Displaying a picture or image (e.g. [[:File:Google.png|Google लोगो) टेक्स्ट Google के लिए छः बाइट्स ट्रांसमिट करने की तुलना में दसियों हज़ार बाइट्स (इस मामले में 48K) ट्रांसमिट कर सकता है। I/O बाउंड कंप्यूटिंग कार्यों के लिए यह महत्वपूर्ण है।
  • बाहरी स्थान: डिस्क या अन्य बाहरी मेमोरी डिवाइस पर आवश्यक स्थान; यह अस्थायी भंडारण के लिए हो सकता है जबकि कलन विधि किया जा रहा है, या यह भविष्य के संदर्भ के लिए आगे बढ़ने के लिए आवश्यक दीर्घकालिक भंडारण हो सकता है।
  • प्रतिक्रिया समय (विलंबता (इंजीनियरिंग)): यह विशेष रूप से रीयल-टाइम कंप्यूटिंग में वास्तविक समय अनुप्रयोग में प्रासंगिक है जब कंप्यूटर सिस्टम को घटना-संचालित प्रोग्रामिंग करना चाहिए।
  • स्वामित्व की कुल लागत: विशेष रूप से यदि एक कंप्यूटर एक विशेष कलन विधि के लिए समर्पित है।

समय

सिद्धांत

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

अभ्यास

कलन विधि के उपयोग के समय के लिए बेंचमार्क (कंप्यूटिंग) का उपयोग करें। कई प्रोग्रामिंग भाषाओं में एक उपलब्ध फ़ंक्शन होता है जो CPU समय प्रदान करता है। लंबे समय तक चलने वाले कलन विधि के लिए बीता हुआ समय भी रुचि का हो सकता है। परिणाम आम तौर पर कई परीक्षणों पर औसत होना चाहिए।

रन-आधारित प्रोफाइलिंग हार्डवेयर कॉन्फ़िगरेशन और बहु प्रसंस्करण और बहु प्रोग्रामिंग वातावरण में एक ही समय में अन्य प्रोग्राम या कार्यों के चलने की संभावना के प्रति बहुत संवेदनशील हो सकती है।

इस प्रकार का परीक्षण एक विशेष प्रोग्रामिंग भाषा, संकलक और संकलक विकल्पों के चयन पर भी बहुत अधिक निर्भर करता है, इसलिए तुलना किए जा रहे कलन विधि को समान शर्तों के तहत लागू किया जाना चाहिए।

अंतरिक्ष

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

स्मृति उपयोग के चार पहलुओं पर विचार किया जा सकता है:

  • कलन विधि के लिए कोड रखने के लिए आवश्यक मेमोरी की मात्रा।
  • इनपुट (कंप्यूटर विज्ञान) के लिए आवश्यक मेमोरी की मात्रा।
  • किसी भी आउटपुट (कंप्यूटिंग) के लिए आवश्यक मेमोरी की मात्रा।
    • कुछ कलन विधि , जैसे सॉर्टिंग, प्रायः इन-प्लेस कलन विधि और आउटपुट डेटा के लिए किसी अतिरिक्त स्थान की आवश्यकता नहीं होती है। इस विशेषता को इन-प्लेस कलन विधि | इन-प्लेस ऑपरेशन कहा जाता है।
  • गणना के दौरान कार्य स्थान के रूप में आवश्यक मेमोरी की मात्रा।

शुरुआती इलेक्ट्रॉनिक कंप्यूटर और शुरुआती घरेलू कंप्यूटरों में अपेक्षाकृत कम मात्रा में कार्यशील मेमोरी थी। उदाहरण के लिए, 1949 के इलेक्ट्रॉनिक विलंब संग्रहण स्वचालित कैलक्यूलेटर (EDSAC) में 1024 17-बिट शब्दों की अधिकतम कार्यशील मेमोरी थी, जबकि 1980 की सिंक्लेयर ZX80 शुरू में 1024 8-बिट कार्यशील मेमोरी के साथ आई थी। 2010 के अंत में, व्यक्तिगत कंप्यूटरों के लिए 4 से 32 गीगाबाइट रैम के बीच होना विशिष्ट है, 300 मिलियन गुना अधिक मेमोरी की वृद्धि।

कैशिंग और मेमोरी पदानुक्रम

Further information: Memory hierarchy

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

  • प्रोसेसर रजिस्टर करता है, कम से कम भंडारण स्थान के साथ कंप्यूटर मेमोरी प्रौद्योगिकियों का सबसे तेज। आधुनिक कंप्यूटरों पर अधिकांश प्रत्यक्ष संगणना जरूरत पड़ने पर कैश, मुख्य मेमोरी और वर्चुअल मेमोरी में अपडेट होने से पहले रजिस्टरों में स्रोत और गंतव्य ऑपरेंड के साथ होती है। सीपीयू कोर पर, आमतौर पर सैकड़ों बाइट्स या कम रजिस्टर उपलब्धता के क्रम में होते हैं, हालांकि एक रजिस्टर फ़ाइल में इंस्ट्रक्शन सेट आर्किटेक्चर में परिभाषित इंस्ट्रक्शन सेट आर्किटेक्चर रजिस्टरों की तुलना में अधिक भौतिक रजिस्टर हो सकते हैं।
  • सीपीयू कैश मेमोरी पदानुक्रम में उपलब्ध दूसरी सबसे तेज और दूसरी सबसे छोटी मेमोरी है। कैश सीपीयू, जीपीयू, हार्ड डिस्क ड्राइव और बाहरी बाह्य उपकरणों में मौजूद हैं, और आमतौर पर स्टेटिक रैंडम-एक्सेस मेमोरी में लागू होते हैं। कैश पदानुक्रम|मेमोरी कैश बहु-स्तरीय हैं; मल्टी-कोर प्रोसेसर में प्रोसेसर कोर के बीच निचले स्तर बड़े, धीमे और आम तौर पर साझा कैश होते हैं। कैश मेमोरी में ऑपरेंड को संसाधित करने के लिए, एक प्रोसेसर (कंप्यूटिंग) को कैश से डेटा प्राप्त करना होगा, रजिस्टरों में ऑपरेशन करना होगा और डेटा को कैश में वापस लिखना होगा। यह सीपीयू या जीपीयू की अंकगणितीय तर्क इकाई या एल 1 कैश में फ्लोटिंग-पॉइंट यूनिट के साथ तुलनीय गति (लगभग 2-10 गुना धीमी) पर संचालित होता है।[8] यह लगभग 10 गुना धीमा है यदि कोई L1 कैश मिस है और इसे L2 कैश से पुनर्प्राप्त और लिखा जाना चाहिए, और L2 कैश मिस होने पर और 10 गुना धीमा है और इसे L3 कैश से पुनर्प्राप्त किया जाना चाहिए, यदि वर्तमान।
  • मुख्य मेमोरी को प्रायः डायनेमिक रैंडम-एक्सेस मेमोरी (DRAM) में लागू किया जाता है। L3 CPU कैश की तुलना में मुख्य मेमोरी बहुत बड़ी होती है (आमतौर पर ≈8 मेगाबाइट्स की तुलना में गीगाबाइट्स), पढ़ने और लिखने की विलंबता आमतौर पर 10-100 गुना धीमी होती है।[8] As of 2018, RAM तेजी से सिस्टम-ऑन-चिप | प्रोसेसर के ऑन-चिप, CPU या GPU मेमोरी के रूप में कार्यान्वित किया जाता है।
  • वर्चुअल मेमोरी को अक्सर द्वितीयक भंडारण युक्ति जैसे हार्ड डिस्क ड्राइव के रूप में लागू किया जाता है, और मेमोरी पदानुक्रम का विस्तार होता है जिसमें बहुत अधिक स्टोरेज स्पेस होता है, लेकिन बहुत बड़ी लेटेंसी होती है, आमतौर पर एक कैश मिस की तुलना में लगभग 1000 गुना धीमी होती है। रैम में मूल्य।[8]जबकि मूल रूप से वास्तव में उपलब्ध होने की तुलना में अधिक मात्रा में मेमोरी उपलब्ध होने का आभास पैदा करने के लिए प्रेरित किया गया था, वर्चुअल मेमोरी अपने टाइम-स्पेस ट्रेडऑफ़ और आभासी मशीन ों के उपयोग को सक्षम करने के लिए समकालीन उपयोग में अधिक महत्वपूर्ण है।[8]मुख्य मेमोरी से कैश की कमी को पृष्ठ दोष कहा जाता है, और कार्यक्रमों पर भारी प्रदर्शन दंड लगता है।

एक कलन विधि जिसकी मेमोरी की जरूरत कैश मेमोरी में फिट होगी, एक कलन विधि की तुलना में बहुत तेज होगी जो मुख्य मेमोरी में फिट होती है, जो बदले में एक कलन विधि की तुलना में बहुत तेज होगी जिसे वर्चुअल मेमोरी का सहारा लेना पड़ता है। इस वजह से, कैश प्रतिस्थापन नीतियां उच्च-प्रदर्शन कंप्यूटिंग के लिए बेहद महत्वपूर्ण हैं, जैसे कैश-जागरूक मॉडल|कैश-जागरूक प्रोग्रामिंग और डेटा संरचना संरेखण। समस्या को और जटिल करने के लिए, कुछ सिस्टम में अलग-अलग प्रभावी गति के साथ कैश मेमोरी के तीन स्तर तक होते हैं। अलग-अलग प्रणालियों में इन विभिन्न प्रकार की मेमोरी की अलग-अलग मात्रा होगी, इसलिए कलन विधि मेमोरी की ज़रूरतों का प्रभाव एक सिस्टम से दूसरे सिस्टम में बहुत भिन्न हो सकता है।

इलेक्ट्रॉनिक कंप्यूटिंग के शुरुआती दिनों में, यदि एक कलन विधि और उसका डेटा मुख्य मेमोरी में फिट नहीं होगा, तो कलन विधि का उपयोग नहीं किया जा सकता था। आजकल वर्चुअल मेमोरी का उपयोग अधिक मेमोरी प्रदान करता प्रतीत होता है, लेकिन प्रदर्शन की कीमत पर। यदि एक कलन विधि और उसका डेटा कैश मेमोरी में फिट हो जाएगा, तो बहुत तेज गति प्राप्त की जा सकती है; इस मामले में जगह कम करने से समय कम करने में भी मदद मिलेगी। इसे स्थानीयता का सिद्धांत कहा जाता है, और इसे संदर्भ के इलाके, स्थानिक इलाके और लौकिक इलाके में विभाजित किया जा सकता है। एक कलन विधि जो पूरी तरह से कैश मेमोरी में फिट नहीं होगा, लेकिन जो संदर्भ की स्थानीयता प्रदर्शित करता है, यथोचित अच्छा प्रदर्शन कर सकता है।

प्रोग्रामिंग की वर्तमान स्थिति की आलोचना

<ब्लॉककोट> मूर के नियम की भरपाई करते हुए सॉफ्टवेयर दक्षता हर 18 महीने में आधी हो जाती है </ब्लॉककोट>

मई आगे कहता है:

<ब्लॉककोट> सर्वव्यापी प्रणालियों में, निष्पादित निर्देशों को आधा करने से बैटरी जीवन दोगुना हो सकता है और बड़े डेटा सेट बेहतर सॉफ्टवेयर और कलन विधि के लिए बड़े अवसर लाते हैं: एन से संचालन की संख्या कम करना × एन से एन × log(N) का एक नाटकीय प्रभाव होता है जब N बड़ा होता है ... N = 30 बिलियन के लिए, यह परिवर्तन 50 वर्षों के तकनीकी सुधार के बराबर है। </ब्लॉककोट>

  • सॉफ्टवेयर लेखक एडम एन. रोसेनबर्ग ने अपने ब्लॉग द फेलियर ऑफ द डिजिटल कंप्यूटर में प्रोग्रामिंग की वर्तमान स्थिति को सॉफ्टवेयर इवेंट क्षितिज के करीब बताया है, (डगलस एडम्स द्वारा अपने हिचहाइकर गाइड टू द गैलेक्सी में वर्णित काल्पनिक शू इवेंट क्षितिज की ओर इशारा करते हुए) किताब[10]). उनका अनुमान है कि 1980 के दशक से उत्पादकता में 70 dB कारक हानि या माल वितरित करने की इसकी क्षमता का 99.99999 प्रतिशत रहा है— जब आर्थर सी. क्लार्क ने 2001 में अपनी पुस्तक 2001 में कंप्यूटर HAL 9000 से कंप्यूटिंग की वास्तविकता की तुलना की: एक स्पेस ओडिसी, उन्होंने बताया कि कितने आश्चर्यजनक रूप से छोटे और शक्तिशाली कंप्यूटर थे लेकिन कंप्यूटर प्रोग्रामिंग कितनी निराशाजनक हो गई थी।

सर्वश्रेष्ठ कलन विधि के लिए प्रतियोगिताएं

निम्नलिखित प्रतियोगिताओं में न्यायाधीशों द्वारा तय किए गए कुछ मनमाने मानदंडों के आधार पर सर्वश्रेष्ठ कलन विधि के लिए प्रविष्टियां आमंत्रित की जाती हैं:


यह भी देखें

संदर्भ

  1. ↑ Green, Christopher, Classics in the History of Psychology, retrieved 19 May 2013
  2. ↑ Knuth, Donald (1974), "Structured Programming with go-to Statements" (PDF), Computing Surveys, 6 (4): 261–301, CiteSeerX 10.1.1.103.6084, doi:10.1145/356635.356640, S2CID 207630080, archived from the original (PDF) on 24 August 2009, retrieved 19 May 2013
  3. ↑ 3.0 3.1 "Floating Point Benchmark: Comparing Languages (Fourmilog: None Dare Call It Reason)". Fourmilab.ch. 4 August 2005. Retrieved 14 December 2011.
  4. ↑ "वेटस्टोन बेंचमार्क इतिहास". Roylongbottom.org.uk. Retrieved 14 December 2011.
  5. ↑ OSNews Staff. "Nine Language Performance Round-up: Benchmarking Math & File I/O". osnews.com. Retrieved 18 September 2018.
  6. ↑ Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur (2016). "The (black) art of runtime evaluation: Are we comparing algorithms or implementations?". Knowledge and Information Systems. 52 (2): 341–378. doi:10.1007/s10115-016-1004-2. ISSN 0219-1377. S2CID 40772241.
  7. ↑ Guy Lewis Steele, Jr. "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO". MIT AI Lab. AI Lab Memo AIM-443. October 1977.[1]
  8. ↑ 8.0 8.1 8.2 8.3 Hennessy, John L; Patterson, David A; Asanović, Krste; Bakos, Jason D; Colwell, Robert P; Bhattacharjee, Abhishek; Conte, Thomas M; Duato, José; Franklin, Diana; Goldberg, David; Jouppi, Norman P; Li, Sheng; Muralimanohar, Naveen; Peterson, Gregory D; Pinkston, Timothy Mark; Ranganathan, Prakash; Wood, David Allen; Young, Clifford; Zaky, Amr (2011). Computer Architecture: a Quantitative Approach (in English) (Sixth ed.). ISBN 978-0128119051. OCLC 983459758.
  9. ↑ "संग्रहीत प्रति" (PDF). Archived from the original (PDF) on 3 March 2016. Retrieved 23 February 2009.
  10. ↑ "The Failure of the Digital Computer".
  11. ↑ Fagone, Jason (29 November 2010). "एल्गोरिथम ओलंपिक में टीन मैथलेट्स का मुकाबला". Wired.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=एल्गोरिथम_दक्षता&oldid=159482’