एल्गोरिथम दक्षता

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

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

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

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

पृष्ठभूमि

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

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

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

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

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

सिंहावलोकन

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

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

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

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

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

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

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

Notation	Name	Examples
$O(1)$	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.
$O(\log n)$	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.
$O(n)$	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.
$O(n\log n)$	linearithmic, loglinear, or quasilinear	Performing a Fast Fourier transform; heapsort, quicksort (best and average case), or merge sort
$O(n^{2})$	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
$O(c^{n}),\;c>1$	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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• वायर्ड पत्रिका

यह भी देखें

• एल्गोरिदम का विश्लेषण- एल्गोरिदम द्वारा आवश्यक संसाधनों का निर्धारण कैसे करें
• अंकगणितीय कोडिंग- चर-लंबाई कोड का एक रूप | कुशल डेटा संपीड़न के लिए चर-लंबाई एंट्रॉपी एन्कोडिंग
• साहचर्य सरणी—एक डेटा संरचना जिसे पेट्रीसिया का पेड़ या जूडी सरणियों का उपयोग करके अधिक कुशल बनाया जा सकता है
• बेंचमार्क (कंप्यूटिंग) - परिभाषित मामलों में तुलनात्मक निष्पादन समय मापने की एक विधि
• सबसे अच्छा, सबसे खराब और औसत मामला- तीन परिदृश्यों में निष्पादन समय का अनुमान लगाने के लिए विचार
• बाइनरी सर्च एल्गोरिथम- सॉर्ट की गई सरणियों को खोजने के लिए एक सरल और कुशल तकनीक
• शाखा तालिका - निर्देश पथ-लंबाई, मशीन कोड का आकार, (और अक्सर स्मृति भी) को कम करने के लिए एक तकनीक
• प्रोग्रामिंग प्रतिमानों की तुलना-प्रतिमान विशिष्ट प्रदर्शन विचार
• संकलक अनुकूलन—संकलक-व्युत्पन्न अनुकूलन
• गणितीय कार्यों की कम्प्यूटेशनल जटिलता
• कम्प्यूटेशनल जटिलता सिद्धांत
• कंप्यूटर प्रदर्शन-कंप्यूटर हार्डवेयर मेट्रिक्स
• डेटा कंप्रेशन- ट्रांसमिशन बैंडविड्थ और डिस्क स्टोरेज को कम करना
• डाटाबेस इंडेक्स - एक डेटा संरचना जो डेटाबेस टेबल पर डेटा पुनर्प्राप्ति संचालन की गति में सुधार करती है
• एन्ट्रापी एन्कोडिंग - प्रतिस्थापन के लिए एक मानदंड के रूप में स्ट्रिंग्स की घटना की आवृत्ति का कुशलतापूर्वक उपयोग करके डेटा को एनकोड करना
• कचरा संग्रह (कंप्यूटर विज्ञान) - उपयोग के बाद स्मृति को स्वत: मुक्त करना
• हरित कंप्यूटिंग- कम संसाधनों की खपत वाली 'हरित' तकनीकों को लागू करने का एक कदम
• हफ़मैन एल्गोरिथम डेटा एन्कोडिंग के लिए एक एल्गोरिद्म
• प्रबंधित कोड प्रदर्शन में सुधार—माइक्रोसॉफ्ट MSDN लाइब्रेरी
• संदर्भ की लोकैलिटी- गैर-स्थानीय मेमोरी एक्सेस के कारण सीपीयू कैश देरी से बचने के लिए
• लूप अनुकूलन
• स्मृति प्रबंधन
• अनुकूलन (कंप्यूटर विज्ञान)
• रूपरेखा (कंप्यूटर प्रोग्रामिंग) - रन-टाइम पर एक एल्गोरिथ्म के वास्तविक प्रदर्शन को मापने के तरीके
• रीयल-टाइम कंप्यूटिंग- समय-महत्वपूर्ण अनुप्रयोगों के और उदाहरण
• रन-टाइम विश्लेषण-अपेक्षित रन-टाइम का अनुमान और एल्गोरिथम की मापनीयता
• एक साथ मल्टीथ्रेडिंग
• Sorting algorithm § Comparison of algorithms
• सट्टा निष्पादन या उत्सुक निष्पादन
• शाखा भविष्यवाणी
• सुपर-थ्रेडिंग
  • हाइपर थ्रेडिंग
• थ्रेडेड कोड- आभासी विधि तालिका या ब्रांच टेबल के समान
• वर्चुअल मेथड टेबल- ब्रांच टेबल डिस्पैचिंग के लिए डायनामिक रूप से असाइन किए गए पॉइंटर्स के साथ

संदर्भ