नमस्ते भटकना। हम, हमारे विचारों में यात्रियों के रूप में, और हमारी स्थिति के विश्लेषणकर्ताओं के रूप में, यह समझना चाहिए कि यह कहाँ अच्छा है, और कहाँ अन्यथा, जहाँ हम वास्तव में हैं, और मैं पाठकों को इस ओर आकर्षित करना चाहता हूं।

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

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

खैर, परिचय घसीटा…।

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

स्प्लिट ऑपरेशन को सूची को दो सब्लिस्ट में बदलने में सक्षम होना चाहिए, उनमें से एक में सभी तत्व कम मूल हैं, और दूसरी सूची में केवल बड़े तत्व शामिल हैं। इसे व्यक्त करते हुए, एरलांग पर केवल दो पंक्तियाँ लिखी गई हैं:

qsort([])->[]; qsort([H|T])->qsort([X||X<-T,X<H])++[H|qsort([X||X<-T,X>=H])]. 

विचार प्रक्रिया के परिणाम के ये भाव मेरे लिए रूचि के हैं।

एक अनिवार्य रूप में छंटनी सिद्धांत का विवरण प्रदान करना अधिक कठिन है। प्रोग्रामिंग की इस पद्धति का एक फायदा कैसे हो सकता है, और फिर आप इसे नहीं बुलाते हैं, भले ही एक एस-जगह-जगह हो, कम से कम एक फोरट्रान। क्या यह है क्योंकि जावास्क्रिप्ट, और सभी भाषाओं के नए मानकों में लैम्ब्डा के सभी रुझान, एल्गोरिदम की असुविधा की पुष्टि है।

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

मैं प्रदर्शन के लिए पायथन का उपयोग करूंगा, क्योंकि इसमें कई प्रतिमान हैं, और यह C ++ बिल्कुल भी नहीं है और अब बिल्कुल भी सटीक नहीं है। आप एक अलग प्रतिमान में एक स्पष्ट कार्यक्रम लिख सकते हैं:

क्रमबद्ध 1

 def qsort(S): if S==[]:return [] H,T=S[0],S[1:] return qsort([X for X in T if X<T])+[H]+qsort([X for X in T if X>=T]) 

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

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

क्रमबद्ध करें २

इसे पुन: पेश करने के लिए, मुझे साहित्य की ओर मुड़ना पड़ा, यह होर का एक बयान है, मैं इसे पायथन में बदलने की कोशिश करता हूं:

 def quicksort(A, lo, hi): if lo < hi: p = partition(A, lo, hi) quicksort(A, lo, p - 1) quicksort(A, p + 1, hi) return A def partition(A, lo, hi): pivot = A[lo] i = lo - 1 j = hi + 1 while True do: i= i + 1 while A[i] < pivot do : j= j - 1 while A[j] > pivot if i >= j: return j A[i],A[j]=A[j],A[i] 

मैं विचार की प्रशंसा करता हूं, यहां एक अंतहीन चक्र की आवश्यकता है, उन्होंने एक जाना-वहाँ डाला होगा)), कुछ जोकर थे।

के विश्लेषण

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

 def qsort(S): if S==[]:return [] H,T=S[0],S[1:] return qsort([X for X in T if X<H])+[H]+qsort([X for X in T if X>=H]) import random def test(len): list=[random.randint(-100, 100) for r in range(0,len)] from time import monotonic start = monotonic() slist=qsort(list) print('qsort='+str(monotonic() - start)) ##print(slist) 

यहां दिए गए माप हैं:

 >>> test(10000) qsort=0.046999999998661224 >>> test(10000) qsort=0.0629999999946449 >>> test(10000) qsort=0.046999999998661224 >>> test(100000) qsort=4.0789999999979045 >>> test(100000) qsort=3.6560000000026776 >>> test(100000) qsort=3.7340000000040163 >>> 

अब मैं एल्गोरिथ्म के निर्माण में इसे दोहराता हूं:

 def quicksort(A, lo, hi): if lo < hi: p = partition(A, lo, hi) quicksort(A, lo, p ) quicksort(A, p + 1, hi) return A def partition(A, lo, hi): pivot = A[lo] i = lo-1 j = hi+1 while True: while True: i=i+1 if(A[i]>=pivot) or (i>=hi): break while True: j=j-1 if(A[j]<=pivot) or (j<=lo): break if i >= j: return max(j,lo) A[i],A[j]=A[j],A[i] import random def test(len): list=[random.randint(-100, 100) for r in range(0,len)] from time import monotonic start = monotonic() slist=quicksort(list,0,len-1) print('quicksort='+str(monotonic() - start)) 

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

कुल मिलाकर

आइए देखें कि एक ही सूची के लिए समय का अंतर क्या होगा, जो बदले में दो तरीकों से हल होता है। हम 100 प्रयोग करेंगे, और एक ग्राफ बनाएंगे:

 import random def test(len): t1,t2=[],[] for n in range(1,100): list=[random.randint(-100, 100) for r in range(0,len)] list2=list[:] from time import monotonic start = monotonic() slist=qsort(list) t1+=[monotonic() - start] #print('qsort='+str(monotonic() - start)) start = monotonic() slist=quicksort(list2,0,len-1) t2+=[monotonic() - start] #print('quicksort='+str(monotonic() - start)) import matplotlib.pyplot as plt fig = plt.figure() ax = fig.add_subplot(111) ax.plot(range(1,100),t1,label='qsort') ax.plot(range(1,100),t2,label='quicksort') ax.legend() ax.grid(True) plt.show() test(10000) 

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

खैर, विचार की छंटाई की क्या अभिव्यक्ति अधिक सचेत है?

प्रदर्शन में एक छोटे अंतर के साथ, हमें कोड की मात्रा और जटिलता में ऐसा अंतर मिलता है।

हो सकता है कि सच्चाई अनिवार्य भाषाओं को सीखने के लिए पर्याप्त हो, लेकिन आपके लिए अधिक आकर्षक क्या है?

पुनश्च। और यहाँ प्रस्ताव है:

 qsort([],[]). qsort([H|T],Res):- findall(X,(member(X,T),X<H),L1), findall(X,(member(X,T),X>=H),L2), qsort(L1,S1), qsort(L2,S2), append(S1,[H|S2],Res).