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

Not to be confused with ऑप्टिमाइज़ेशन, जिसकी चर्चा प्रोग्राम ऑप्टिमाइज़ेशन, ऑप्टिमाइज़िंग कंपाइलर, लूप ऑप्टिमाइज़ेशन, ऑब्जेक्ट कोड ऑप्टिमाइज़र, आदि में की जाती है।.

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

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

उदाहरण के लिए, बुलबुले सॉर्ट और टाइमसॉर्ट दोनों ही छोटे से बड़े आइटम की छँटाई कलन विधि हैं जो वस्तुओं की सूची को सबसे छोटे से सबसे बड़े तक क्रमबद्ध करते हैं। बबल सॉर्ट समय में सूची को चुकता तत्वों की संख्या के अनुपात में क्रमबद्ध करता है (${\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

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

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

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

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

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

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

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

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

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

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

Further information: मेमोरी पदानुक्रम

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

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

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

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

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

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

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

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

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

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

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

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

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

यह भी देखें

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