लघु सर्किटिंग तरह

Question

मैं समझता हूँ कि:

head (map (2**) [1..999999]) 

केवल वास्तव में मूल्यांकन करेंगे 2 ** 1, और बाकी में से कोई भी, लेकिन पुस्तक मैं पढ़ रहा हूँ कहना है कि:

head (sort somelist) 

केवल विल सूची में सबसे छोटी वस्तु को खोजने की आवश्यकता है, क्योंकि यह सब कुछ उपयोग किया जाता है। यह कैसे काम करता है? जहां तक ​​मैं कह सकता हूं, सॉर्टिंग एल्गोरिदम के साथ यह असंभव होगा (जैसे बबल सॉर्टिंग)।

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

क्या यह सॉर्ट फ़ंक्शन कैसे काम करता है, या क्या कोई और सॉर्टिंग एल्गोरिदम है जिसके बारे में मुझे पता नहीं है, जो कि इस तरह की छोटी सर्किटिंग की अनुमति देगा?

Answer 1

यह:

केवल सूची में सबसे छोटी आइटम खोजने की जरूरत होगी, क्योंकि यह है कि यह सब किया जाता है।

... वास्तव में कहना चाहिए समारोह केवल काम की न्यूनतम राशि है कि छँटाई एल्गोरिथ्म की आवश्यकता है सबसे छोटा तत्व को खोजने के लिए क्या करने की जरूरत है।

उदाहरण के लिए, अगर हम हमारे अंतर्निहित छँटाई कलन विधि के रूप में quicksort उपयोग कर रहे हैं, तो head . quicksortइष्टतम (!) चयन के रूप में 'quickselect' नाम से जाना जाता एल्गोरिथ्म, जो बुरी से बुरी हालत रेखीय है के बराबर है। इसके अलावा, हम के लागू कर सकते हैं - केवल take k . quicksort द्वारा चयन करें।

क्योंकि छँटाई के लिए भाषा का समर्थन अधिक सर्वव्यापी है, अनुक्रमण के बाद छँटाई के साधारण दृष्टिकोण कई वातावरण में अपने नुकसान के बावजूद पसंद किया जाता है:

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

quicksort जबकि हास्केल (तरह विलय) में डिफ़ॉल्ट सॉर्ट काफी के रूप में अच्छी रचना नहीं है, के रूप में यह हल कर सूची के प्रत्येक तत्व वापस जाने के लिए सख्ती से आवश्यकता से अधिक काम करता है, इस परिदृश्य में अच्छी तरह से काम करता है। this post on the Haskell mailing list नोटों के रूप में:

आलसी quicksort

हे में पहले कश्मीर छोटी से छोटी तत्वों के बैच उत्पादन करने में सक्षम है (एन + K लॉग ट) कुल समय [1]

जबकि आलसी mergesort जरूरत

O (n + K लॉग एन) कुल समय [2]

अधिक आप 0 को पढ़ने के लिए पसंद कर सकते हैं के लिए।

Answer 2

आपके द्वारा अभी वर्णित एल्गोरिदम का एक विशिष्ट नाम है: "चयन क्रम"। यह ओ (एन) इसलिए यह सबसे तेज़ चीज नहीं है जो आप कर सकते हैं। हालांकि, अगर आप सॉर्ट किए गए सरणी में पहले "के" तत्व चाहते हैं, तो जटिलता ओ (एन) होगी जो अच्छा है अगर "के" पर्याप्त छोटा है (उदाहरण के लिए)।

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

Answer 3

आप एक तुलना समारोह है कि GHCi के कमांड लाइन में इस तरह अपने तर्कों के निशान बनाते हैं:

> :module + Data.List Debug.Trace 
> let myCompare x y = trace ("\tCmp " ++ show x ++ " " ++ show y) $ compare x y 

तो आप व्यवहार अपने आप को देख सकते हैं:

> sortBy myCompare "foobar" 

"  Cmp 'f' 'o' 
     Cmp 'o' 'b' 
     Cmp 'f' 'b' 
     Cmp 'a' 'r' 
     Cmp 'b' 'a' 
a  Cmp 'b' 'r' 
b  Cmp 'f' 'o' 
     Cmp 'f' 'r' 
f  Cmp 'o' 'o' 
     Cmp 'o' 'r' 
o  Cmp 'o' 'r' 
or" 

हास्केल lazily स्ट्रिंग मूल्यांकन कर रही है , एक समय में एक चरित्र। बाएं हाथ कॉलम को मुद्रित किया जा रहा है क्योंकि प्रत्येक चरित्र पाया जाता है, दाएं हाथ कॉलम को "ट्रेस" द्वारा मुद्रित तुलना की तुलना में आवश्यक तुलना रिकॉर्डिंग के साथ।

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

फिर

> head $ sortBy myCompare "foobar" 

     Cmp 'f' 'o' 
     Cmp 'o' 'b' 
     Cmp 'f' 'b' 
     Cmp 'a' 'r' 
     Cmp 'b' 'a' 
'a' 

कोशिश आप को समझने के लिए कि यह कैसे काम करता है, तरह समारोह के लिए स्रोत कोड को देखने और मूल्यांकन 'प्रकार "foobar"' मैन्युअल कागज पर चाहते हैं।

qsort [] = [] 
qsort (x:xs) = qsort less ++ [x] ++ qsort greater 
    where (less, greater) = partition (< x) xs 

तो

qsort ('f':"oobar") 
= qsort ('b':"a") ++ "f" ++ qsort ('o':"or") 
= ("a" ++ "b") ++ "f" ++ qsort ('o':"or") 

और अब हम पर्याप्त किया है खोजने के लिए 'एक' अन्य कॉल करने के लिए "qsort" मूल्यांकन करने के लिए बिना परिणाम में पहले आइटम है। मैंने वास्तविक तुलना को छोड़ दिया है क्योंकि यह कॉल के अंदर "विभाजन" में छिपा हुआ है। असल में "विभाजन" भी आलसी है, इसलिए वास्तव में अन्य "qsort" के लिए तर्क का मूल्यांकन नहीं किया गया है, जहां तक ​​मैंने इसे दिखाया है।