मर्ज सॉर्ट के इस कार्यान्वयन को अच्छा है?

Question

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

बस मुझे सब कुछ बताएं जो मैं यहां सुधार सकता हूं। मैं अपने आप से यह एक सुंदर स्पष्ट और सरल कार्यान्वयन सोचता हूं। आपकी सलाह के लिए धन्यवाद, यहाँ कोड :)

merge [] ys = ys 
merge xs [] = xs 
merge xs ys = sorted : merge left right 
       where 
        sorted = if head(xs) < head(ys) then head(xs) else head(ys) 
        left = if head(xs) <= head(ys) then tail(xs) else xs 
        right = if head(xs) > head(ys) then tail(ys) else ys 

msort [] = [] 
msort [x] = [x] 
msort xs = merge (msort left) (msort right) 
      where 
       left = take (div (length xs) 2) xs 
       right = drop (div (length xs) 2) xs 

Answer 1

ठीक है, सब से पहले है, हम मर्ज पुनर्लेखन कर सकते हैं का उपयोग कर से बचना चाहिए मिलान

merge [] ys = ys 
merge xs [] = xs 
merge xs@(x:xs1) ys@(y:ys1) 
    | x <= y = x : merge xs1 ys 
    | otherwise = y : merge xs ys1 

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

msort का कार्यान्वयन बहुत अधिक जगह है, सिवाय इसके कि हम सूची को एक अधिक कुशल तरीके से विभाजित कर सकते हैं। ऐसा इसलिए है क्योंकि length xs - पूरा करने के लिए ओ (एन) लेता है। संकलक आपको बचा सकता है और length कॉल के परिणाम को कैश कर सकता है ताकि length पर दूसरी कॉल सूची को फिर से पार न करे। लेकिन take और drop इस तरह से एक और दो ट्रैवर्सल का कारण बनता है जिससे इस प्रकार 3 ट्रैवर्सल का उपयोग करके सूची को विभाजित किया जा सकता है जो महंगा साबित हो सकता है।

msort [] = [] 
msort [x] = [x] 
msort xs = merge (msort first) (msort second) 
    where 
     (first, second) = splitInHalves xs 
     splitInHalves [] = ([], []) 
     splitInHalves [x] = ([x], []) 
     splitInHalves (x:y:xs) = 
      let (xs1, ys1) = splitInHalves xs 
      in (x:xs1, y:ys1) 

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

संपादित करें 1: वाक्य रचना थोड़ा ज्यादा है

, तो यहां कुछ संसाधन हैं:

• Pattern Matching - @ प्रतीक के साथ बिट कहा जाता है एक के रूप में पैटर्न। आप इसे वहां पाएंगे
• let एक ऐसा कीवर्ड है जो एक वैरिएबल घोषित करने के लिए प्रयोग किया जाता है जो इसके बाद अभिव्यक्ति में उपयोग किया जाता है (जबकि where उस अभिव्यक्ति में एक चर को बांधता है जो इसके पहले होता है)।गार्ड (| condition = value साथ बातें) सहित हास्केल वाक्य रचना, पर अधिक यहां पाया जा सकता, Learn You a Haskell

संपादित की इस अध्याय में 2:

@ is7s splitInHalves के एक दूर अधिक संक्षिप्त संस्करण प्रस्तावित का उपयोग कर foldrfunction:

splitInHalves = foldr (\x (l,r) -> (x:r,l)) ([],[]) 

संपादित करें 3:

012,351,641

Lazy Evaluation and Time Complexity

आशा इस मदद करता है और कार्यात्मक प्रोग्रामिंग की अद्भुत दुनिया में आपका स्वागत है:

यहाँ एक और सवाल का जवाब जो मर्ज तरह का एक वैकल्पिक कार्यान्वयन है, जो भी stable होने का गुण प्रदान करता है!