सैंपलसॉर्ट

सैंपलसॉर्ट, डिवाइड एंड कंकर एल्गोरिथ्म पर आधारित एक सॉर्टिंग एल्गोरिथ्म है, जिसका उपयोग प्रायः पैरलेल प्रोसेसिंग सिस्टम में किया जाता है। पारंपरिक डिवाइड एंड कंकर एल्गोरिथ्म, ऐरे को सब-इंटरवल या बकेट में विभाजित करता है। फिर इस बकेट को अलग-अलग क्रमबद्ध किया जाता है और एक साथ जोड़ दिया जाता है। यद्यपि, यदि ये ऐरे गैर-समान रूप से वितरित किए गए है, तो इन सॉर्टिंग एल्गोरिदम का प्रदर्शन अत्यधिक सीमा तक कम हो सकता है। सैंपलसॉर्ट इस समस्या का समाधान करने में सक्षम है जिसमें n-एलिमेंट सीक्वन्स के लिए एक s आकार का सैम्पल चुनकर तथा उस सैंपल को सॉर्ट करने के उपरांत p-1 < s एलेमेन्ट को परिणाम से चुनकर बकेट की रेंज निर्धारित की जाती है। ये एलमेंट (जिन्हें स्प्लिटर्स कहा जाता है) फिर ऐरे को लगभग p समान बकेट में विभाजित करते हैं। सैंपलसॉर्ट का वर्णन 1970 के लेख, सैंपलसॉर्ट: ए सैंपलिंग अप्रोच टू मिनिमल स्टोरेज ट्री सॉर्टिंग में डब्ल्यू. डी. फ्रेज़र और ए. सी. मैककेलर द्वारा किया गया है।

एल्गोरिथम

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

सैंपलसॉर्ट कार्यान्वयन तैयार करने के लिए, हमें p बकेट की संख्या तय करने की आवश्यकता होती है। जब यह किया जाता है, तो वास्तविक एल्गोरिदम तीन चरणों में संचालित होता है:

1. सैम्पल p−1 इनपुट से तत्व (स्प्लिटर्स)। सॉर्ट करें; आसन्न स्प्लिटर्स का प्रत्येक युग्म फिर एक बकेट को परिभाषित करता है।
2. डेटा लूप करें, प्रत्येक तत्व को उपयुक्त बकेट में रखें। (इसका तात्पर्य यह हो सकता है: इसे मल्टीप्रोसेसर सिस्टम में एक प्रोसेसर को भेजें।)
3. प्रत्येक बकेट को क्रमबद्ध करें.

पूर्ण क्रमबद्ध आउटपुट बकेट का संयोजन है।

एक सामान्य रणनीति है कि p को उपलब्ध प्रोसेसरों के संख्या के बराबर रखा जाता है। फिर डेटा प्रोसेसरों के बीच वितरित किया जाता है, जो कुछ अन्य, अनुक्रमशील, सॉर्टिंग एल्गोरिदम का उपयोग करके बकेटों को क्रमबद्ध करते हैं।

स्यूडोकोड

निम्नलिखित सूची उपर्युक्त तीन चरण वाले एल्गोरिदम को छद्मकोड के रूप में दिखाती है और दिखाती है कि एल्गोरिदम सिद्धांत रूप में कैसे काम करता है। निम्नांकित में, A अवर्गीकृत डेटा है, k ओवरसैंपलिंग कारक है, जिस पर बाद में चर्चा की गई है, और p स्प्लिटर्स की संख्या है.

फ़ंक्शन सैम्पलसॉर्ट(ए[1..एन], k, p)
    // यदि औसत बकेट का आकार सीमा से नीचे है तो उदाहरण के लिए स्विच करें। जल्दी से सुलझाएं
    यदि एन / के <थ्रेसहोल्ड तो स्मॉलसॉर्ट(ए)
    /* स्टेप 1 */
    एस = [एस चुनें1, ..., एस(p−1)k] यादृच्छिक रूप से // से नमूने चुनें
    क्रम से लगाना S // सॉर्ट सैम्पल
    [एस0, एस1, ..., एसp−1, एसp] <- [-∞, एसk, एस2k, ..., एस(p−1)k, ∞] // स्प्लिटर्स का चयन करें
    /* चरण दो */
    ए में प्रत्येक ए के लिए
        पाना j ऐसा कि एसj−1 <ए <= एसj

जगह a बकेट में बी_j /* चरण 3 और संयोजन */

    रिटर्न कॉन्टेनेट(सैम्पलसॉर्ट(बी1), ..., सैम्पल सॉर्ट (बीk))

छद्म कोड मूल फ्रेज़र और मैककेलर एल्गोरिदम से अलग है। छद्म कोड में, सैंपलसॉर्ट को पुनरावर्ती रूप से कहा जाता है। फ़्रेज़र और मैककेलर ने केवल एक बार सैंपलसॉर्ट कहा और निम्नलिखित सभी पुनरावृत्तियों में क्विकसॉर्ट का उपयोग किया।

जटिलता

समानांतर कार्यान्वयन के लिए बिग ओ अंकन में दी गई जटिलता $p$ प्रोसेसर:

स्प्लिटर्स खोजें.

$O\left({\frac {n}{p}}+\log(p)\right)$

बाल्टियों को भेजें.

$O(p)$ सभी नोड्स को पढ़ने के लिए

$O(\log(p))$ प्रसारण के लिए

$O\left({\frac {n}{p}}\log(p)\right)$ सभी कुंजियों के लिए बाइनरी खोज के लिए

$O\left({\frac {n}{p}}\right)$ बकेट में चाबियाँ भेजने के लिए

बाल्टियाँ क्रमबद्ध करें.

$O\left(c\left({\frac {n}{p}}\right)\right)$ कहाँ $c(n)$ अंतर्निहित अनुक्रमिक छँटाई पद्धति की जटिलता है।अक्सर $c(n)=n\log(n)$.

इस एल्गोरिथम द्वारा की गई तुलनाओं की संख्या, सूचना सैद्धांतिक इष्टतम के करीब पहुंचती है $\log _{2}(n!)$ बड़े इनपुट अनुक्रमों के लिए. फ़्रेज़र और मैककेलर द्वारा किए गए प्रयोगों में, एल्गोरिदम को क्विकॉर्ट की तुलना में 15% कम तुलना की आवश्यकता थी।

डेटा का सैम्पल लेना

डेटा का सैम्पल विभिन्न तरीकों से लिया जा सकता है। कुछ विधियों में शामिल हैं:

1. समान दूरी वाले नमूने चुनें.
2. बेतरतीब ढंग से चयनित नमूने चुनें.

oversampling

ओवरसैंपलिंग अनुपात यह निर्धारित करता है कि स्प्लिटर्स को निर्धारित करने से पहले नमूने के रूप में कितनी बार अधिक डेटा तत्वों को खींचना है। लक्ष्य डेटा के वितरण का अच्छा प्रतिनिधित्व प्राप्त करना है। यदि डेटा मान व्यापक रूप से वितरित हैं, जिसमें कई डुप्लिकेट मान नहीं हैं, तो एक छोटा सैम्पल अनुपात पर्याप्त है। अन्य मामलों में जहां वितरण में कई डुप्लिकेट हैं, एक बड़ा ओवरसैंपलिंग अनुपात आवश्यक होगा। आदर्श स्थिति में, चरण 2 के बाद, प्रत्येक बकेट में शामिल होता है $n/p$ तत्व. इस मामले में, किसी भी बकेट को सॉर्ट करने में अन्य की तुलना में अधिक समय नहीं लगता है, क्योंकि सभी बकेट समान आकार की होती हैं।

खींचने के बाद $k$ आवश्यकता से कई गुना अधिक नमूनों को क्रमबद्ध किया जाता है। इसके बाद, बकेट सीमाओं के रूप में उपयोग किए जाने वाले स्प्लिटर्स स्थिति में नमूने हैं $k,2k,3k,\dots ,(p-1)k$ सैम्पल अनुक्रम का (साथ में) $-\infty$ और $\infty$ क्रमशः सबसे बायीं और दायीं ओर की बाल्टियों के लिए बायीं और दायीं सीमाओं के रूप में)। यह केवल चयन करने की तुलना में अच्छे स्प्लिटर्स के लिए बेहतर अनुमान प्रदान करता है $p$ बेतरतीब ढंग से विभाजित हो जाता है।

बकेट आकार अनुमान

परिणामी सैम्पल आकार के साथ, अपेक्षित बकेट आकार और विशेष रूप से एक निश्चित आकार से अधिक बकेट की संभावना का अनुमान लगाया जा सकता है। निम्नलिखित यह दिखाएगा कि ओवरसैंपलिंग कारक के लिए $S\in \Theta \left({\dfrac {\log n}{\epsilon ^{2}}}\right)$ किसी भी बकेट में इससे अधिक न होने की प्रायिकता $(1+\epsilon )\cdot {\dfrac {n}{p}}$ तत्व से बड़ा है $1-{\dfrac {1}{n}}$.

यह दिखाने के लिए चलो $\langle e_{1},\dots ,e_{n}\rangle$ एक क्रमबद्ध अनुक्रम के रूप में इनपुट बनें। एक प्रोसेसर के लिए इससे अधिक प्राप्त करना $(1+\epsilon )\cdot n/p$ तत्वों, लंबाई के इनपुट का एक क्रम मौजूद होना चाहिए $(1+\epsilon )\cdot n/p$, जिनमें से अधिकतम S नमूने उठाए गए हैं। ये मामले संभाव्यता का गठन करते हैं $P_{\text{fail}}$. इसे यादृच्छिक चर के रूप में दर्शाया जा सकता है:

$$X_{i}:={\begin{cases}1,&{\text{if }}s_{i}\in \left\langle e_{j},\dots ,e_{j}+(1+\epsilon )\cdot {\dfrac {n}{p}}\right\rangle \\0,&{\text{otherwise}}\end{cases}},X:=\sum _{i=0}^{S\cdot p-1}X_{i}$$

के अपेक्षित मूल्य के लिए $X_{i}$ धारण करता है:

$$E$$