एल्गोरिदम छंटनी?

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

तो मेरा सवाल यह है कि क्या कोई सॉर्टिंग एल्गोरिदम है जो उस तरह की जानकारी को ध्यान में रखता है? वे कितने अच्छे हैं?

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

संपादित करें # 2: मुझे आश्चर्य है कि उत्तर इस मुद्दे पर चर्चा करने वाले एक कठिन पृष्ठ के विकी लिंक नहीं है। क्या यह एक बहुत ही आम मामला नहीं है (उदाहरण के लिए गॉसियन केस)?

संपादित करें # 3: मैं इस प्रश्न के लिए एक बाउंटी जोड़ रहा हूं, क्योंकि मैं स्रोतों के साथ निश्चित उत्तरों की तलाश कर रहा हूं, अनुमान नहीं। कुछ ऐसा है जैसे "गाऊशियन वितरित डेटा के मामले में, एक्सवाईजेड एल्गोरिदम औसत पर सबसे तेज़ है, जैसा कि स्मिथ एट अल द्वारा साबित किया गया था। [1]"। हालांकि किसी भी अतिरिक्त जानकारी का स्वागत है।

नोट: मैं उच्चतम वोट वाले उत्तर में बक्षीस का पुरस्कार दूंगा। बुद्धिमानी से वोट दें!

स्रोत

2011-05-29 static_rtti

कई एल्गोरिदम हैं जो डेटा पर जानकारी लेते हैं और कुछ जवाबों में पहले से ही उल्लेख किए गए हैं। असली सवाल यह है कि आपके पास विशेष रूप से किस प्रकार की जानकारी है। कोई 'जेनेरिक' एल्गोरिदम नहीं है जो आपके पास किसी भी प्रकार की जानकारी का लाभ उठाता है। – Elad

आप अपने वितरण का प्रतिनिधित्व कैसे करेंगे? - वैकल्पिक रूप से - क्या आप गाऊशियन वितरण के लिए एक विशिष्ट समाधान की तलाश में हैं? –

"मैं स्रोतों के साथ निश्चित जवाब ढूंढ रहा हूं, अनुमान नहीं।" - अगर कोई स्रोत नहीं दिया जाता है - इसका मतलब यह नहीं है कि यह एक अटकलें है। एक उत्तर मूल विचारों को प्रतिबिंबित कर सकता है और अभी भी सही हो सकता है ... –

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

एक ज्ञात वितरण होने और इस तरह से मानक बाल्टी क्रमबद्ध एल्गोरिथ्म को संशोधित करके, आप शायद Histogram Sort एल्गोरिथ्म या इसे करने के लिए कुछ बंद मिलेगा।बेशक, आपका एल्गोरिदम हिस्टोग्राम सॉर्ट एल्गोरिदम की तुलना में कम्प्यूटेशनल रूप से तेज़ होगा क्योंकि संभवतः पहले से ही वितरण को जानने के लिए पहले पास (लिंक में वर्णित) करने की आवश्यकता नहीं होगी।

संपादित करें: आपके प्रश्न के अपने नए मानदंडों को देखते हुए (हालांकि अपने पिछले जवाब सम्मानजनक NIST के हिस्टोग्राम क्रमबद्ध लिंक और प्रदर्शन के विषय में जानकारी शामिल है), यहाँ समानांतर प्रसंस्करण पर अंतर्राष्ट्रीय सम्मेलन से एक सहकर्मी की समीक्षा पत्रिका लेख है:

Adaptive Data Partition for Sorting Using Probability Distribution

लेखकों का दावा है इस एल्गोरिथ्म बेहतर प्रदर्शन (30% बेहतर है) लोकप्रिय त्वरित क्रमबद्ध एल्गोरिथ्म से।

स्रोत

2011-05-29 19:42:28

संदर्भ सॉर्टिंग एल्गोरिदम के रूप में त्वरित क्रमबद्ध विचार करना काफी तिरछा है। IntroSort फ्लाई पर पैटर्न (आरोही/अवरोही ब्लॉक) का पता लगाने के द्वारा रिकर्सन में होने वाले छोटे सरणी के विशेष-आवरण से टिमसॉर्ट (और कुछ अन्य विविधता) में भी सुधार करता है। दिलचस्प पेपर अभी भी :) –

डेटा स्रोत वितरण को जानना, कोई भी एक अच्छा हैश फ़ंक्शन बना सकता है। वितरण को अच्छी तरह से जानना, हैश फ़ंक्शन एक पूर्ण हैश फ़ंक्शन साबित हो सकता है, या कई इनपुट वैक्टरों के लिए बिल्कुल सही है।

इस तरह का फ़ंक्शन आकार एन के इनपुट को एन डिब्बे में विभाजित करेगा, जैसे कि सबसे छोटी वस्तु पहले बिन में मैप करेगी, और सबसे बड़ी वस्तु अंतिम बिन पर मैप करेगी। जब हैश सही है- हम बस सभी वस्तुओं को डिब्बे में डालने के प्रकार प्राप्त करेंगे।

एक हैश तालिका में सभी आइटम सम्मिलित करना, फिर उन्हें आदेश हे (एन) होगा जब हैश एकदम सही है द्वारा निकालने (यह मानते हुए हैश फंक्शन गणना लागत हे है (1), और रेखांकन हैश डेटा संरचना के संचालन कर रहे हैं हे (1))।

मैं हैश-टेबल को लागू करने के लिए फाइबोनैकी ढेर की एक सरणी का उपयोग करूंगा।

इनपुट वेक्टर के लिए हैश फ़ंक्शन सही नहीं होगा (लेकिन अभी भी सही के करीब), यह अभी भी ओ (nlogn) से बेहतर होगा। जब यह सही होता है - यह ओ (एन) होगा। मुझे यकीन नहीं है कि औसत जटिलता की गणना कैसे करें, लेकिन अगर मजबूर हो, तो मैं ओ (nloglogn) पर शर्त लगाऊंगा।

स्रोत

2011-05-29 07:51:52

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

सही। नोट हटा दिया गया। –

डाउनवोट हटा दिया गया :) –

आप पिवट मूल्य का चयन करने के लिए उस जानकारी का उपयोग त्वरित रूप से कर सकते हैं। मुझे लगता है कि यह ओ (एन ** 2) सबसे खराब केस जटिलता से दूर रहने वाले एल्गोरिदम की संभावना में सुधार करेगा।

स्रोत

2011-05-29 08:24:43 salva

ध्वनि आप Self-Improving Algorithms पढ़ने के लिए चाहते हो सकता है जैसे: वे मनमाना इनपुट वितरण के लिए एक अंतिम इष्टतम उम्मीद प्रसारण समय को प्राप्त। (I) संख्या का एक अनुक्रम छँटाई और (ii) कंप्यूटिंग एक समतल बिंदु सेट के डेलॉनाय ट्राईऐन्ग्युलेशंस:

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

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

स्रोत

2011-05-31 13:02:14

बहुत रोचक, धन्यवाद! –

कंप्यूटर सॉर्टिंग एल्गोरिदम को में दो श्रेणियों, तुलना-आधारित सॉर्टिंग और गैर-तुलना-आधारित सॉर्टिंग में वर्गीकृत किया जा सकता है। तुलना-आधारित सॉर्टिंग के लिए, इसके सर्वोत्तम-मामले प्रदर्शन में सॉर्टिंग समय Ω (nlogn) है, जबकि इसके सबसे खराब मामले प्रदर्शन में सॉर्टिंग समय O (n2) तक बढ़ सकता है। हाल के वर्षों में, कुछ बेहतर एल्गोरिदम को को तुलनात्मक रूप से तुलनात्मक रूप से क्रमबद्ध किया गया है, जैसे उन्नत डेटा वितरण विशेषताओं के अनुसार त्वरित क्रमबद्ध करें। हालांकि, इन एल्गोरिदम के लिए औसत सॉर्टिंग समय केवल Ω (nlog2n) है, और केवल सर्वोत्तम मामले में यह ओ (एन) तक पहुंच सकता है। तुलना-आधारित सॉर्टिंग से अलग, गिनती सॉर्टिंग, बाल्टी सॉर्टिंग और रेडिक्स सॉर्टिंग जैसी गैर-तुलना-आधारित सॉर्टिंग मुख्य रूप से कुंजी और पता गणना पर निर्भर करती है। जब चाबियों के मान 1 से मीटर तक परिमित होते हैं, तो कम्प्यूटेशनल गैर-तुलना-आधारित सॉर्टिंग की जटिलता ओ (एम + एन) है। विशेष रूप से, जब एम = ओ (एन), सॉर्टिंग समय ओ (एन) तक पहुंच सकता है। हालांकि, जब एम = एन 2, एन 3, ...।, रैखिक सॉर्टिंग समय की ऊपरी सीमा प्राप्त नहीं की जा सकती है। गैर-तुलना-आधारित सॉर्टिंग के बीच, बाल्टी सॉर्टिंग उचित "बाल्टी" में समान कुंजी वाले रिकॉर्ड के समूह को वितरित करता है, फिर एक और सॉर्टिंग एल्गोरिदम प्रत्येक बाल्टी में रिकॉर्ड पर लागू होता है।बाल्टी सॉर्टिंग के साथ, एम बाल्टी में रिकॉर्ड का विभाजन कम समय लेने वाला है, जबकि केवल कुछ रिकॉर्ड प्रत्येक बाल्टी में निहित होंगे ताकि "क्लीनअप सॉर्टिंग" एल्गोरिदम बहुत तेज़ लागू किया जा सके। इसलिए, बाल्टी सॉर्टिंग में 12 (nlogn) एल्गोरिदम की तुलना में सॉर्टिंग समय को असम्बद्ध रूप से सहेजने की क्षमता है। जाहिर है, बाल्टी में सभी रिकॉर्ड समान रूप से वितरित करने के लिए बाल्टी सॉर्टिंग में महत्वपूर्ण भूमिका निभाते हैं। इसलिए आपको डेटा वितरण के अनुसार हैश फ़ंक्शन बनाने के लिए एक विधि है, जिसका उपयोग पर किया जाता है, प्रत्येक रिकॉर्ड की कुंजी पर आधारित एन बाल्टी में एन रिकॉर्ड समान रूप से वितरित करता है। इसलिए, प्रस्तावित बाल्टी सॉर्टिंग एल्गोरिदम का सॉर्टिंग समय किसी भी परिस्थिति में ओ (एन) तक पहुंच जाएगा।

जांच इस पत्र: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5170434&tag=1

स्रोत

2011-05-31 23:38:50 AhmadAssaf

बाल्टी तरह आप एक रेखीय समय है, जब तक आप हे (1) समय में प्रत्येक बिंदु के CDF गणना कर सकता है के रूप में देना होगा एल्गोरिथ्म छँटाई।

a = array(0, n - 1, [])   // create an empty list for each bucket 
for x in input: 
    a[floor(n * cdf(x))].append(x) // O(1) time for each x 
input.clear() 
for i in {0,...,n - 1}: 
    // this sorting step costs O(|a[i]|^2) time for each bucket 
    // but most buckets are small and the cost is O(1) per bucket in expectation 
    insertion_sort(a[i]) 
    input.concatenate(a[i])

चलने का समय उम्मीद में हे (एन) है, क्योंकि उम्मीद में वहाँ हे (एन) जोड़े (एक्स, वाई हैं:

एल्गोरिथ्म, जो आप भी कहीं और देख सकते हैं, इस प्रकार है) जैसे कि एक्स और वाई एक ही बाल्टी में गिरते हैं, और सम्मिलन प्रकार का चलने का समय बिल्कुल ठीक है (उसी बाल्टी में एन + # जोड़े)। विश्लेषण FKS static perfect hashing के समान है।

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

स्रोत

2011-06-02 13:44:03 jonderry

मुझे लगता है कि cycle sort इस श्रेणी में आता है। जब आप उस सटीक स्थिति को जानते हैं जिसे आप प्रत्येक तत्व को समाप्त करना चाहते हैं तो आप इसका उपयोग करते हैं।

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

स्रोत

2011-06-03 20:57:24 MatrixFrog

यदि आप अपने डेटा के वितरण को जानते हैं तो आपको केवल अंतिम स्थिति का अनुमान पता है। इस मामले में चक्र क्रम अभी भी उपयोगी है? –

अपने आप से नहीं, नहीं। लेकिन शायद आप "लगभग" सॉर्ट करने के लिए चक्र प्रकार का उपयोग कर सकते हैं और फिर इसे समाप्त करने के लिए किसी अन्य विधि का उपयोग कर सकते हैं। दूसरी विधि एक होगी जो अच्छी तरह से काम करती है जब हर तत्व इसकी सही स्थिति के अपेक्षाकृत निकट होता है। – MatrixFrog

ऐसा लगता है कि किसी के पास इस सवाल से एक समान विचार था: http://stackoverflow.com/questions/6265525/contest-fastest-way-to-sort-a-big-array-of-gaussian -distributed-डाटा/6269933 # 6269933 – MatrixFrog

उत्तर

संबंधित मुद्दे