विलय - क्या नीचे-ऊपर की तुलना में तेज़ी से ऊपर है?

Question

मैं सेडगेविक & वेन द्वारा "एल्गोरिदम, चौथा एड" पढ़ रहा हूं, और जिस तरह से मैं जावास्क्रिप्ट में चर्चा की गई एल्गोरिदम लागू कर रहा हूं।

मैंने हाल ही में शीर्ष-नीचे और नीचे-अप दृष्टिकोण की तुलना करने के लिए पुस्तक में प्रदान किए गए विलयोर्ट उदाहरणों को लिया है ... लेकिन मुझे लगता है कि नीचे-नीचे तेजी से चल रहा है (मुझे लगता है)। मेरे ब्लॉग पर मेरा विश्लेषण देखें। - http://www.akawebdesign.com/2012/04/13/javascript-mergesort-top-down-vs-bottom-up/

मुझे कोई भी चर्चा नहीं मिली है जो कहती है कि विलय का एक तरीका दूसरे की तुलना में तेज़ होना चाहिए। क्या मेरा कार्यान्वयन (या विश्लेषण) त्रुटिपूर्ण है?

नोट: मेरा विश्लेषण एल्गोरिदम के पुनरावृत्त लूप को मापता है, कड़ाई से सरणी तुलना/चाल नहीं। शायद यह दोषपूर्ण या अप्रासंगिक है?

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

Answer 1

यदि तेज़ी से आप कम "पुनरावृत्तियों" का मतलब है तो हाँ। यदि आप शायद निष्पादन समय के बारे में सोच रहे हैं।

कारण 21,513 पुनरावृत्तियों में से कुछ 22,527 पुनरावृत्तियों से अधिक कर रहे हैं।

स्रोत को देखने से ऐसा लगता है कि आपके आरेख में कुछ पत्ते नोड्स को व्यक्तिगत रूप से अलग नहीं किया जा रहा है जिसके परिणामस्वरूप कम विलय और प्रकार होते हैं लेकिन उन्हें अधिक समय लगता है।

Answer 2

मुझे कोई चर्चा नहीं मिली है जो कहती है कि विलय का एक तरीका दूसरे की तुलना में तेज़ होना चाहिए।

नीचे-ऊपर और ऊपर-नीचे मर्ज प्रकार, साथ ही साथ अन्य रूपों, 90 के दशक के दौरान अच्छी तरह से अध्ययन किया गया है। संक्षेप में, यदि आप अलग-अलग चाबियों की तुलना की लागत को मापते हैं, तो सर्वोत्तम लागत एक ही होती है (~ (एन एलजी एन)/2), टॉप-डाउन की सबसे खराब लागत सबसे खराब से कम या बराबर होती है तल-अप का मामला (लेकिन दोनों ~ एन एलजी एन) और टॉप-डाउन की औसत लागत नीचे-अप के औसत मामले से कम या बराबर होती है (लेकिन दोनों ~ एन एलजी एन), जहां "एलजी एन" है बाइनरी लॉगरिदम। मतभेद रैखिक शर्तों से स्टेम। बेशक, अगर एन = 2^पी, तो दो प्रकार वास्तव में वही हैं। इसका मतलब है कि, तुलनात्मक रूप से, टॉप-डाउन हमेशा नीचे की तुलना में बेहतर होता है। इसके अलावा, यह साबित कर दिया गया है कि शीर्ष-डाउन विलय प्रकार की "आधा आधा" विभाजन रणनीति इष्टतम है। शोध पत्र फ्लोज़लेट, गोलिन, पैनी, प्रोडिंगर, चेन, ह्वांग और सेडगेविक से हैं।

यहाँ मैं अपनी पुस्तक डिजाइन और पूरी तरह कार्यात्मक कार्यक्रम (कॉलेज प्रकाशन, ब्रिटेन) के विश्लेषण में आया था, Erlang में है:

tms([X|T=[_|U]]) -> cutr([X],T,U); 
tms(T)   -> T. 

cutr(S,[Y|T],[_,_|U]) -> cutr([Y|S],T,U); 
cutr(S, T,  U) -> mrg(tms(S),tms(T)). 

mrg( [], T)   -> T; 
mrg(  S, [])   -> S; 
mrg(S=[X|_],[Y|T]) when X > Y -> [Y|mrg(S,T)]; 
mrg( [X|S], T)   -> [X|mrg(S,T)]. 

ध्यान दें कि यह नहीं एक स्थिर प्रकार है। इसके अलावा, Erlang (और OCaml) में, यदि आप स्मृति को सहेजना चाहते हैं तो आपको पैटर्न में उपनाम (ALIAS = ...) का उपयोग करने की आवश्यकता है। यहां की चाल सूची के मध्य को इसकी लंबाई जानने के बिना ढूंढना है। यह कटर/3 द्वारा किया जाता है जो दो पॉइंटर्स को इनपुट सूची में संभालता है: एक को एक और दूसरे से बढ़ाया जाता है, इसलिए जब दूसरा अंत तक पहुंच जाता है, तो पहला मध्य में होता है। (मैंने ओलिवियर डेनवी द्वारा एक पेपर से यह सीखा।) इस तरह, आपको लंबाई का ट्रैक रखने की आवश्यकता नहीं है और आप सूची के दूसरे भाग की कोशिकाओं को डुप्लिकेट नहीं करते हैं, इसलिए आपको केवल (1/2) एन एलजी एन अतिरिक्त स्थान की आवश्यकता है, बनाम एन एलजी एन । यह अच्छी तरह से जाना जाता है।

अक्सर दावा किया जाता है कि नीचे-अप संस्करण कार्यात्मक भाषाओं या लिंक्ड सूची (Knuth, Panny, Prodinger) के लिए बेहतर है, लेकिन मुझे नहीं लगता कि यह सच है।

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

वैसे, अन्य प्रकार भी हैं: कतार विलय सॉर्ट और ऑनलाइन विलय सॉर्ट (मैं बाद में अपनी पुस्तक में चर्चा करता हूं)।

[संपादित करें: लागत के लिए उपाय तुलना की संख्या है, एक लिंक्ड सूची बनाम सरणी चुनने के बीच कोई अंतर नहीं है। बेशक, यदि आप लिंक्ड सूचियों के साथ टॉप-डाउन वेरिएंट को कार्यान्वित करते हैं, तो आपको चालाक होना चाहिए, क्योंकि आपको जरूरी चाबियों की संख्या नहीं पता है, लेकिन आपको प्रत्येक बार कम से कम चाबियों को पार करने की आवश्यकता होगी, और कुल (1/2) एन एलजी एन कोशिकाओं में पुन: आवंटित करें (यदि आप चालाक हैं)। लिंक्ड सूचियों के साथ नीचे-अप विलय सॉर्ट को वास्तव में अधिक अतिरिक्त मेमोरी, एन एलजी एन + एन कोशिकाओं की आवश्यकता होती है। तो, यहां तक ​​कि लिंक्ड सूचियों के साथ, टॉप-डाउन संस्करण सबसे अच्छा विकल्प है। जहां तक ​​कार्यक्रम की लंबाई बढ़ जाती है, आपका माइलेज भिन्न हो सकता है, लेकिन एक कार्यात्मक भाषा में, स्थिरता की आवश्यकता नहीं होने पर, ऊपर-नीचे मर्ज सॉर्ट को नीचे-नीचे से छोटा बनाया जा सकता है। ऐसे कुछ कागजात हैं जो मर्ज सॉर्ट के कार्यान्वयन के मुद्दों पर चर्चा करते हैं, जैसे जगह (जैसे आपको एरे की आवश्यकता होती है), या स्थिरता इत्यादि। उदाहरण के लिए, कार्गजेन और लार्सन ट्रैफ (1 99 7) द्वारा विलय कार्यक्रमों का एक सावधानीपूर्वक विश्लेषण।]

Answer 3

मैंने 201212 संस्करण के लिए this course के कोरसरा कक्षा मंचों पर एक ही प्रश्न पूछा था। प्रोफेसर केविन वेने (प्रिंसटन के) ने जवाब दिया कि कई मामलों में रिकर्सन बेहतर प्रदर्शनों को कैशिंग के कारण पुनरावृत्ति से तेज है।

तो उस समय मुझे जो छोटा जवाब मिला वह यह था कि शीर्ष डाउन मर्ज सॉर्ट कैशिंग कारणों के कारण नीचे विलय प्रकार से तेज होगा।

कृपया ध्यान दें कि कक्षा जावा प्रोग्रामिंग भाषा (जावास्क्रिप्ट नहीं) में पढ़ाया गया था।