प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिदम): Difference between revisions

From Vigyanwiki
(Created page with "प्रतिस्पर्धी विश्लेषण ऑनलाइन एल्गोरिदम का विश्लेषण करने के लिए...")
 
No edit summary
 
(8 intermediate revisions by 3 users not shown)
Line 1: Line 1:
प्रतिस्पर्धी विश्लेषण [[ऑनलाइन एल्गोरिदम]] का विश्लेषण करने के लिए आविष्कार की गई एक विधि है, जिसमें एक ऑनलाइन एल्गोरिदम का प्रदर्शन (जिसे अनुरोधों के अप्रत्याशित अनुक्रम को पूरा करना होगा, भविष्य को देखने में सक्षम हुए बिना प्रत्येक अनुरोध को पूरा करना होगा) की तुलना एक इष्टतम '' के प्रदर्शन से की जाती है। ऑफ़लाइन एल्गोरिदम'' जो अनुरोधों के अनुक्रम को पहले से देख सकता है। एक एल्गोरिथम ''प्रतिस्पर्धी'' है यदि इसका ''प्रतिस्पर्धी अनुपात'' - इसके प्रदर्शन और ऑफ़लाइन एल्गोरिदम के प्रदर्शन के बीच का अनुपात - सीमित है। पारंपरिक सर्वश्रेष्ठ, सबसे खराब और औसत मामले | सबसे खराब स्थिति विश्लेषण के विपरीत, जहां एक एल्गोरिदम का प्रदर्शन केवल कठिन इनपुट के लिए मापा जाता है, प्रतिस्पर्धी विश्लेषण के लिए आवश्यक है कि एक एल्गोरिदम कठिन और आसान इनपुट दोनों पर अच्छा प्रदर्शन करे, जहां कठिन और आसान को इनपुट द्वारा परिभाषित किया जाता है। इष्टतम ऑफ़लाइन एल्गोरिदम का प्रदर्शन।
'''प्रतिस्पर्धी विश्लेषण [[ऑनलाइन एल्गोरिदम]]''' का विश्लेषण करने के लिए आविष्कार की गई विधि है, जिसमें ऑनलाइन एल्गोरिदम का प्रदर्शन (जिसे अनुरोधों के अप्रत्याशित अनुक्रम को पूरा करना होता है, भविष्य को देखने में सक्षम हुए अतिरिक्त प्रत्येक अनुरोध को पूरा करना होगा) की तुलना इष्टतम के प्रदर्शन से की जाती है। इस प्रकार ऑफ़लाइन एल्गोरिदम जो अनुरोधों के अनुक्रम को पहले से देख सकता है। एल्गोरिथम प्रतिस्पर्धी है यदि इसका प्रतिस्पर्धी अनुपात इसके प्रदर्शन और ऑफ़लाइन एल्गोरिदम के प्रदर्शन के बीच का अनुपात सीमित है। पारंपरिक सर्वश्रेष्ठ, सबसे व्यर्थ और औसत स्थिति या सबसे व्यर्थ स्थिति विश्लेषण के विपरीत है, जहां एल्गोरिदम का प्रदर्शन केवल कठिन इनपुट के लिए मापा जाता है, इस प्रकार प्रतिस्पर्धी विश्लेषण के लिए आवश्यक है कि एल्गोरिदम कठिन और सरल इनपुट दोनों पर अच्छा प्रदर्शन करे, जहां कठिन और सरल को इनपुट द्वारा परिभाषित किया जाता है। इष्टतम ऑफ़लाइन एल्गोरिदम का प्रदर्शन होता है।


कई एल्गोरिदम के लिए, प्रदर्शन न केवल इनपुट के आकार पर निर्भर करता है, बल्कि उनके मूल्यों पर भी निर्भर करता है। उदाहरण के लिए, प्रारंभिक क्रम के आधार पर तत्वों की एक सरणी को क्रमबद्ध करने में कठिनाई भिन्न होती है। ऐसे डेटा-निर्भर एल्गोरिदम का विश्लेषण औसत-मामले और सबसे खराब स्थिति वाले डेटा के लिए किया जाता है। प्रतिस्पर्धी विश्लेषण ऑन-लाइन और [[यादृच्छिक एल्गोरिदम]] के लिए सबसे खराब स्थिति का विश्लेषण करने का एक तरीका है, जो आमतौर पर डेटा पर निर्भर होते हैं।
कई एल्गोरिदम के लिए, प्रदर्शन न केवल इनपुट के आकार पर निर्भर करता है, किन्तु उनके मान पर भी निर्भर करता है। उदाहरण के लिए, प्रारंभिक क्रम के आधार पर अवयवो की सरणी को क्रमबद्ध करने में कठिनाई भिन्न होती है। ऐसे डेटा-निर्भर एल्गोरिदम का विश्लेषण औसत-स्थिति और सबसे व्यर्थ स्थिति वाले डेटा के लिए किया जाता है। ''इस प्रकार'' प्रतिस्पर्धी विश्लेषण ऑन-लाइन और [[यादृच्छिक एल्गोरिदम]] के लिए सबसे व्यर्थ स्थिति का विश्लेषण करने का विधि है, जो सामान्यतः डेटा पर निर्भर होते हैं।


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


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


क्लासिक ऑनलाइन समस्या का सबसे पहले प्रतिस्पर्धी विश्लेषण के साथ विश्लेषण किया गया {{harv|Sleator|Tarjan|1985}} [[सूची अद्यतन समस्या]] है: वस्तुओं की एक सूची और विभिन्न वस्तुओं के लिए अनुरोधों के अनुक्रम को देखते हुए, सूची तक पहुंचने की लागत को कम करें जहां सूची के सामने वाले तत्वों तक पहुंचने की लागत कम होती है। (आमतौर पर, किसी आइटम तक पहुंचने की लागत सूची में उसकी स्थिति के बराबर होती है।) एक्सेस के बाद, सूची को पुनर्व्यवस्थित किया जा सकता है। अधिकांश पुनर्व्यवस्थाओं की एक लागत होती है। मूव-टू-फ्रंट एल्गोरिदम बिना किसी लागत के एक्सेस के बाद अनुरोधित आइटम को सामने ले जाता है। ट्रांसपोज़ एल्गोरिदम एक्सेस किए गए आइटम को उसके ठीक पहले वाले आइटम के साथ स्वैप करता है, वह भी बिना किसी कीमत के। विश्लेषण के शास्त्रीय तरीकों से पता चला कि ट्रांसपोज़ कुछ संदर्भों में इष्टतम है। व्यवहार में, मूव-टू-फ्रंट ने बहुत बेहतर प्रदर्शन किया। प्रतिस्पर्धी विश्लेषण का उपयोग यह दिखाने के लिए किया गया था कि एक प्रतिद्वंद्वी एक इष्टतम एल्गोरिदम की तुलना में ट्रांसपोज़ को मनमाने ढंग से खराब प्रदर्शन कर सकता है, जबकि मूव-टू-फ्रंट को कभी भी एक इष्टतम एल्गोरिदम की लागत से दोगुने से अधिक खर्च करने के लिए नहीं बनाया जा सकता है।
क्लासिक ऑनलाइन समस्या का सबसे पहले प्रतिस्पर्धी विश्लेषण के साथ विश्लेषण किया गया {{harv|स्लीटर|टारजन|1985}} [[सूची अद्यतन समस्या]] है: वस्तुओं की सूची और विभिन्न वस्तुओं के लिए अनुरोधों के अनुक्रम को देखते हुए, सूची तक पहुंचने की सामान्यतः को कम करें जहां सूची के सामने वाले अवयवो तक पहुंचने की सामान्यतः कम होती है। (सामान्यतः, किसी आइटम तक पहुंचने की सामान्यतः सूची में उसकी स्थिति के सामान होती है।) ''इस प्रकार'' एक्सेस के पश्चात्, सूची को पुनर्व्यवस्थित किया जा सकता है। अधिकांश पुनर्व्यवस्थाओं की सामान्यतः होती है। मूव-टू-फ्रंट एल्गोरिदम अतिरिक्त किसी सामान्यतः के एक्सेस के पश्चात् अनुरोधित आइटम को सामने ले जाता है। ट्रांसपोज़ एल्गोरिदम एक्सेस किए गए आइटम को उसके ठीक पहले वाले आइटम के साथ स्वैप करता है, वह भी अतिरिक्त किसी मूल्य के विश्लेषण मौलिक विधियों से पता चला कि ट्रांसपोज़ कुछ संदर्भों में इष्टतम है। ''इस प्रकार'' व्यवहार में, मूव-टू-फ्रंट ने बहुत बेहतर प्रदर्शन किया था। प्रतिस्पर्धी विश्लेषण का उपयोग यह दिखाने के लिए किया गया था कि प्रतिद्वंद्वी इष्टतम एल्गोरिदम की तुलना में ट्रांसपोज़ को अनैतिक विधि से व्यर्थ प्रदर्शन कर सकता है, जबकि मूव-टू-फ्रंट को कभी भी इष्टतम एल्गोरिदम की सामान्यतः से दोगुने से अधिक व्यय करने के लिए नहीं बनाया जा सकता है।


सर्वर से ऑनलाइन अनुरोधों के मामले में, भविष्य के बारे में अनिश्चितताओं को दूर करने के लिए प्रतिस्पर्धी एल्गोरिदम का उपयोग किया जाता है। अर्थात्, एल्गोरिथम भविष्य नहीं जानता, जबकि काल्पनिक प्रतिद्वंद्वी (प्रतिद्वंद्वी) जानता है। इसी तरह, वितरित प्रणालियों के लिए प्रतिस्पर्धी एल्गोरिदम विकसित किए गए थे, जहां एल्गोरिदम को एक स्थान पर आने वाले अनुरोध पर प्रतिक्रिया करनी होती है, बिना यह जाने कि किसी दूरस्थ स्थान पर क्या हुआ है। यह सेटिंग प्रस्तुत की गई थी {{harv|Awerbuch|Kutten|Peleg|1992}}.
सर्वर से ऑनलाइन अनुरोधों के स्थिति में, भविष्य के बारे में अनिश्चितताओं को दूर करने के लिए प्रतिस्पर्धी एल्गोरिदम का उपयोग किया जाता है। अर्थात्, एल्गोरिथम भविष्य नहीं जानता है, जबकि काल्पनिक प्रतिद्वंद्वी (प्रतिद्वंद्वी) जानता है। इसी तरह, वितरित प्रणालियों के लिए प्रतिस्पर्धी एल्गोरिदम विकसित किए गए थे, ''इस प्रकार'' जहां एल्गोरिदम को स्थान पर आने वाले अनुरोध पर प्रतिक्रिया करनी होती है, अतिरिक्त यह जाने कि किसी दूरस्थ स्थान पर क्या हुआ है। यह सेटिंग प्रस्तुत की गई थी {{harv|एवरबुच|कुटेन|पेलेग|1992}}.


==यह भी देखें==
==यह भी देखें==
Line 18: Line 18:
* ऑनलाइन एल्गोरिदम
* ऑनलाइन एल्गोरिदम


==संदर्भ==
==संदर्भ                                                             ==
*{{citation|title=Amortized efficiency of list update and paging rules|first1=D.|last1=Sleator|author1-link=Daniel Sleator|first2=R.|last2=Tarjan|author2-link=Robert Tarjan|journal=Communications of the ACM|year=1985|doi=10.1145/2786.2793|volume=28|issue=2|pages=202–208}}.
*{{citation|title=Amortized efficiency of list update and paging rules|first1=D.|last1=Sleator|author1-link=Daniel Sleator|first2=R.|last2=Tarjan|author2-link=Robert Tarjan|journal=Communications of the ACM|year=1985|doi=10.1145/2786.2793|volume=28|issue=2|pages=202–208}}.
*{{citation|contribution=Competitive analysis of distributed algorithms|first=James|last=Aspnes|year=1998|doi=10.1007/BFb0029567|title=Online Algorithms: The State of the Art|series=Lecture Notes in Computer Science|volume=1442|pages=118–146|editor1-first=A.|editor1-last=Fiat|editor1-link=Amos Fiat|editor2-first=G. J.|editor2-last=Woeginger|editor2-link= Gerhard J. Woeginger}}.
*{{citation|contribution=Competitive analysis of distributed algorithms|first=James|last=Aspnes|year=1998|doi=10.1007/BFb0029567|title=Online Algorithms: The State of the Art|series=Lecture Notes in Computer Science|volume=1442|pages=118–146|editor1-first=A.|editor1-last=Fiat|editor1-link=Amos Fiat|editor2-first=G. J.|editor2-last=Woeginger|editor2-link= Gerhard J. Woeginger}}.
*{{citation|last1=Borodin|first1=A.|author1-link=Allan Borodin|last2=El-Yaniv|first2=R.|year=1998|title=Online Computation and Competitive Analysis|publisher=Cambridge University Press|isbn=0-521-56392-5}}.
*{{citation|last1=Borodin|first1=A.|author1-link=Allan Borodin|last2=El-Yaniv|first2=R.|year=1998|title=Online Computation and Competitive Analysis|publisher=Cambridge University Press|isbn=0-521-56392-5}}.
*{{citation|last1=Awerbuch|first1=B.|last2=Kutten|first2=S.|last3=Peleg|first3=D.|authorlink2=Shay Kutten|year=1992|contribution=Competitive Distributed Job Scheduling|title=ACM STOC, Victoria, BC, Canada}}.
*{{citation|last1=Awerbuch|first1=B.|last2=Kutten|first2=S.|last3=Peleg|first3=D.|authorlink2=Shay Kutten|year=1992|contribution=Competitive Distributed Job Scheduling|title=ACM STOC, Victoria, BC, Canada}}.
[[Category: एल्गोरिदम का विश्लेषण]] [[Category: ऑनलाइन एल्गोरिदम]]


[[Category: Machine Translated Page]]
[[Category:Created On 27/07/2023]]
[[Category:Created On 27/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Templates Vigyan Ready]]
[[Category:एल्गोरिदम का विश्लेषण]]
[[Category:ऑनलाइन एल्गोरिदम]]

Latest revision as of 11:38, 14 August 2023

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

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

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

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

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

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

यह भी देखें

संदर्भ

  • Sleator, D.; Tarjan, R. (1985), "Amortized efficiency of list update and paging rules", Communications of the ACM, 28 (2): 202–208, doi:10.1145/2786.2793.
  • Aspnes, James (1998), "Competitive analysis of distributed algorithms", in Fiat, A.; Woeginger, G. J. (eds.), Online Algorithms: The State of the Art, Lecture Notes in Computer Science, vol. 1442, pp. 118–146, doi:10.1007/BFb0029567.
  • Borodin, A.; El-Yaniv, R. (1998), Online Computation and Competitive Analysis, Cambridge University Press, ISBN 0-521-56392-5.
  • Awerbuch, B.; Kutten, S.; Peleg, D. (1992), "Competitive Distributed Job Scheduling", ACM STOC, Victoria, BC, Canada.