यदि मेरे पास एक क्रमबद्ध सूची है (सॉर्ट करने के लिए क्विकॉर्ट कहें), यदि मेरे पास जोड़ने के लिए बहुत सारे मूल्य हैं, तो सॉर्टिंग को निलंबित करना बेहतर है, और उन्हें अंत में जोड़ें, फिर सॉर्ट करें, या बाइनरी काट का उपयोग करें ताकि उन्हें जोड़ने के दौरान आइटम सही तरीके से रखें। यदि आइटम यादृच्छिक हैं, या पहले से ही कम या कम हैं तो इससे कोई फर्क पड़ता है?क्या आइटम डालने या उन्हें क्रमबद्ध सूची में जोड़ने के बाद सूची को क्रमबद्ध करना तेज़ है
यदि आप पर्याप्त आइटम जोड़ते हैं जो आप प्रभावी रूप से स्क्रैच से सूची बना रहे हैं, तो आपको बाद में सूची को सॉर्ट करके बेहतर प्रदर्शन प्राप्त करने में सक्षम होना चाहिए।
यदि आइटम अधिकतर क्रम में हैं, तो आप इसका लाभ उठाने के लिए दोनों वृद्धिशील अपडेट और नियमित सॉर्टिंग को ट्विक कर सकते हैं, लेकिन स्पष्ट रूप से, यह आमतौर पर परेशानी के लायक नहीं है। (आप भी ले यकीन है कि कुछ अप्रत्याशित आदेश अपने एल्गोरिथ्म नहीं कर सकता बनाने जैसी बातों से सावधान रहने की जरूरत ज्यादा अब, qv अनुभवहीन quicksort)
दोनों वृद्धिशील अद्यतन और नियमित रूप से सूची प्रकार हैं हे (एन लॉग ऑन एन), लेकिन आप बाद में सबकुछ क्रमबद्ध करने के लिए एक बेहतर निरंतर कारक प्राप्त कर सकते हैं (मुझे लगता है कि आपको कुछ सहायक डेटास्ट्रक्चर मिला है, इसलिए आपका वृद्धिशील अद्यतन ओ (एन) से तेज़ी से सूची आइटम तक पहुंच सकता है ...)। आम तौर पर, एक बार में सॉर्टिंग में क्रमशः ऑर्डरिंग को बनाए रखने की तुलना में बहुत अधिक डिज़ाइन स्वतंत्रता होती है, क्योंकि वृद्धिशील अद्यतन को हर समय एक पूर्ण क्रम बनाए रखना होता है, लेकिन एक बार-बार-बार थोक प्रकार नहीं होता है।
यदि कुछ और नहीं है, तो याद रखें कि बहुत सारे अनुकूलित-अनुकूलित थोक प्रकार उपलब्ध हैं।
आमतौर पर heap का उपयोग करना बेहतर होता है। संक्षेप में, यह पुशर और पिकर के बीच आदेश बनाए रखने की लागत को विभाजित करता है। दोनों ऑपरेशन ओ (लॉग एन) हैं, ओ (एन लॉग एन) की बजाय, अधिकांश अन्य समाधानों की तरह।
यह सूची विशेष रूप से अच्छी सलाह है यदि सूची किसी प्रकार की प्राथमिकता कतार है। उस मामले में कमजोर ढेर के लिए Google। –
एक क्रमबद्ध सूची में एक आइटम सम्मिलित करना है हे (लॉग एन) है, जबकि एक सूची छँटाई O (n लॉग ऑन एन) कौन सा सुझाव है कि यह हमेशा पहले सॉर्ट करने के लिए बेहतर है और फिर सम्मिलित है
लेकिन याद बड़ा 'ओ' केवल वस्तुओं की संख्या के साथ गति की स्केलिंग से संबंधित है, हो सकता है कि आपके आवेदन के लिए मध्य में एक डालने महंगा हो (उदाहरण के लिए यदि यह एक वेक्टर था) और इसलिए आगे बढ़ना और सॉर्ट करना बेहतर हो सकता है।
एक क्रमबद्ध सूची में सम्मिलित करना ओ (लॉग एन) है। एक हैश में सम्मिलित करना ओ (1) है। – bmdhacks
ठीक है, आपने अपना नोटेशन तय किया है, लेकिन अब आपका पहला कथन गलत है। छंटनी और डालने एक ही गति है। सॉर्टिंग ओ (एन लॉग एन) है, और सम्मिलन ओ ओ (लॉग एन) ऑपरेशन एन बार कर रहा है, इस प्रकार ओ (एन लॉग एन) है। – bmdhacks
लेकिन यह अलग एन है, अगर आपको केवल 10 आइटम एक लाख में डालने की आवश्यकता है तो 10 * (लॉग 1 एम) 10 + (1 एम लॉग 1 एम) ps धड़कता है। क्षमा करें मैंने आपको एक टिप्पणी छोड़ दी, टाइपो को ढूंढने के लिए धन्यवाद, लेकिन ऐसा लगता है कि ऐसा हुआ है? –
यह वही है। किसी क्रमबद्ध सूची में किसी आइटम को सम्मिलित करना ओ (लॉग एन) है, और सूची में प्रत्येक तत्व के लिए ऐसा करना, एन, (इस प्रकार सूची बनाना) ओ (एन लॉग एन) होगा जो कि quicksort की गति है (या विलय सॉर्ट करें जो इस दृष्टिकोण के करीब है)।
यदि आप उन्हें मोर्चे पर डालें तो यह ओ (1) होगा, लेकिन बाद में एक क्विकॉर्ट कर रहा है, यह अभी भी ओ (एन लॉग एन) होगा।
मैं पहले दृष्टिकोण के साथ जाऊंगा, क्योंकि इसमें थोड़ा तेज होने की संभावना है। यदि आपकी सूची का प्रारंभिक आकार, एन, डालने के लिए तत्वों की संख्या से अधिक है, एक्स, तो सम्मिलित दृष्टिकोण ओ (एक्स लॉग एन) है। सूची के शीर्ष पर डालने के बाद छंटनी ओ (एन लॉग एन) है। यदि एन = 0 (आईई: आपकी सूची प्रारंभ में खाली है), सॉर्ट किए गए क्रम में डालने की गति, या बाद में सॉर्टिंग समान है।
पिक्य नहीं होना चाहिए, लेकिन एन तत्वों की संख्या है, इसलिए आपके उत्तर का अंतिम अनुच्छेद मुझे बहुत अधिक समझ में नहीं आता है! क्या आपका मतलब था, "यदि एन बहुत बड़ा नहीं है"? –
Remo.D की टिप्पणी के बाद स्पष्टीकरण के लिए संपादित किया गया। कुछ मामलों में – bmdhacks
अनुच्छेद 2 गलत है। लगभग क्रमबद्ध सूची पर त्वरित प्रकार से करना ओ (एन लॉग एन) के बजाय ओ (एन^2) दृष्टिकोण करता है। –
यदि सूची ए है) पहले से क्रमबद्ध है, और बी) प्रकृति में गतिशील, फिर एक क्रमबद्ध सूची में डालना हमेशा तेज होना चाहिए (सही जगह (ओ (एन)) ढूंढें और डालें (ओ (1))) ।
हालांकि, यदि सूची स्थैतिक है, तो शेष सूची का एक शफल होना चाहिए (ओ (एन) सही जगह खोजने के लिए और ओ (एन) चीजों को नीचे स्लाइड करने के लिए)।
किसी भी तरह से, एक क्रमबद्ध सूची में डालने (या बाइनरी खोज वृक्ष की तरह कुछ) तेजी से होना चाहिए।
ओ (एन) + ओ (एन) हमेशा ओ (एन लॉग एन) से तेज होना चाहिए।
एक लिखित सूची जैसे गतिशील निर्माण में डालने अभी भी ओ (1) * प्रति डालने * है। तो हाँ, कुल मिलाकर जो ओ (एन) तक जोड़ता है - लेकिन यह गुणात्मक नहीं है, यह additive (यानी 2 बार ओ (एन), ओ (एन^2) नहीं है)। – warren
डालने से ओ (लॉग (एन)) होना चाहिए यदि आप इसे सही करते हैं और अपेक्षाकृत समान रूप से वितरित डेटा – tloach
आपका पहला अनुच्छेद दो क्रमबद्ध लिंक्ड सूचियों के एक विलय का वर्णन कर रहा है। यदि एक विलय ओ (एन) है, तो आपका कुल प्रकार ओ (एनएलओएनएन) होगा, जब तक कि आप ओ (एनएलओएनएन) समय से कम समय में सॉर्ट किए गए हिस्सों की ओ (1) संख्या प्राप्त नहीं कर लेते। प्रत्येक तत्व को बाइनरी खोज पेड़ में डालने से बढ़ते क्रमशः सॉर्टिंग ओ (एन लॉग एन) है, क्योंकि सम्मिलन ऑपरेशन ओ (लॉगएन) है, और आपको इसे एन बार करना है। (साधारण द्विआधारी पेड़ों में ओ (एन) एक तत्व के लिए सबसे खराब मामला सम्मिलन होता है।) वैसे भी, पिछले दो अनुच्छेद बकवास हैं। इनमें से कोई भी आपको O (NlogN) को हरा करने में मदद करता है, या यहां तक कि qsort को हरा देता है। –
सिद्धांत रूप में, सूची को सॉर्ट करने के बजाय पेड़ बनाने के लिए तेज़ है। प्रत्येक सम्मिलन के लिए वृक्ष आवेषण ओ (लॉग (एन)) होते हैं, जिससे समग्र ओ (एन लॉग (एन)) होता है। ओ में छंटनी (एन लॉग (एन))।
क्यों जावा ट्री-मैप, है है कि (एक सूची के TreeSet, TreeList, ArrayList और LinkedList कार्यान्वयन के अलावा।)
एक TreeSet वस्तु तुलना क्रम में बातें रहता है। कुंजी तुलनात्मक इंटरफ़ेस द्वारा परिभाषित किया गया है।
एक लिंक्डलिस्ट प्रविष्टि आदेश में चीजें रखता है।
एक ऐरेलिस्ट अधिक मेमोरी का उपयोग करता है, कुछ परिचालनों के लिए तेज़ है।
एक वृक्षारोपण, इसी तरह, एक कुंजी द्वारा क्रमबद्ध करने की आवश्यकता को हटा देता है। नक्शा आवेषण के दौरान मुख्य क्रम में बनाया गया है और क्रमबद्ध क्रम में बनाए रखा गया है।
हालांकि, किसी कारण से, ट्रीसेट का जावा कार्यान्वयन एक ऐरेलिस्ट और एक प्रकार का उपयोग करने से काफी धीमा है।
[अनुमान लगाया जाना मुश्किल है कि यह नाटकीय रूप से धीमा क्यों होगा, लेकिन यह है। डेटा के माध्यम से एक पास से थोड़ा तेज़ होना चाहिए। बात इस तरह की अक्सर एल्गोरिथम विश्लेषण trumping स्मृति प्रबंधन की लागत है।]
पर एक अज्ञात क्रमबद्ध क्रम की वस्तुओं को जोड़ने का वर्णन कर रहा हूं, मैं सावधान रहूंगा कि एक पेड़ एक सूची से तेज़ है। यह वास्तव में इनपुट के आकार और पेड़ कार्यान्वयन के आकार पर निर्भर करता है। – hazzen
कुछ गति परीक्षण चलाएं और आप देखेंगे कि यह मामला नहीं है। ट्रीसेट बनाम ऐरेलिस्ट, ऐरेलिस्ट 500k यादृच्छिक संख्या जोड़ने, क्रमबद्ध करने और उन्हें दूसरी सूची में डंप करने के लिए ~ 2x तेज था। अगर हम उन्हें किसी अन्य सूची में डंप नहीं करते हैं, तो ArrayList ~ 1.6x से जीतता है। – hazzen
ट्रीसेट और ट्रीमैप अनिवार्य रूप से एक ही कक्षा हैं; एक ट्रीसेट
आप उन्हें पहले जोड़ने और फिर चाहिए एक मूलांक प्रकार का उपयोग इस इष्टतम होना चाहिए
यदि यह नेट है और आइटम पूर्णांक हैं, उन्हें एक शब्दकोश में जोड़ना तेज़ है (या यदि आप .NET 3.0 या ऊपर हैं तो हैशसेट का उपयोग करें यदि आपको डुप्लिकेट खोने में कोई फर्क नहीं पड़ता) यह आपको ऑटोमैटिक सॉर्टिंग देता है।
मुझे लगता है कि स्ट्रिंग भी वैसे ही काम करेंगे। सौंदर्य आपको ओ (1) सम्मिलन और इस तरह से छंटाई मिलती है।
शब्दकोश
(यदि आप जिस सूची के बारे में बात कर रहे हैं वह सी # List<T> की तरह है।) कुछ मूल्यों के साथ एक क्रमबद्ध सूची में सही स्थिति में कुछ मान जोड़ना कम संचालन की आवश्यकता होगी। लेकिन यदि मूल्यों की संख्या बढ़ाई जा रही है, तो इसे और अधिक की आवश्यकता होगी।
मैं एक सूची का उपयोग करने का सुझाव नहीं दूंगा लेकिन आपके मामले में कुछ और अधिक उपयुक्त डेटा संरचना का सुझाव दूंगा। एक बाइनरी पेड़ की तरह, उदाहरण के लिए। कम से कम सम्मिलन समय के साथ एक क्रमबद्ध डेटा संरचना।
किसी क्रमबद्ध सूची में किसी आइटम को सम्मिलित करना O(n) समय लेता है, O(log n) समय नहीं। O(log n) समय लेते हुए आपको इसे रखने के लिए जगह मिलनी है। लेकिन फिर आपको सभी तत्वों पर स्थानांतरित करना होगा - O(n) समय लेना। इसलिए सॉर्टेड-नेस को बनाए रखने के दौरान डालने O(n^2) है, जहां उन्हें सभी डालने और फिर सॉर्टिंग O(n log n) है।
आपके सॉर्ट कार्यान्वयन के आधार पर, यदि आप प्रविष्टियों की संख्या सूची आकार से बहुत छोटी हैं तो आप O(n log n) से भी बेहतर हो सकते हैं।लेकिन अगर ऐसा है, तो इससे कोई फर्क नहीं पड़ता।
तो सम्मिलित होने की संख्या बड़ी है, तो सम्मिलित करें और अन्यथा सॉर्ट करें, अन्यथा यह कोई फर्क नहीं पड़ता।
मुझे लगता है कि आपके पास ओ नोटेशन का पूरी तरह गलत विचार है। किसी सूची में किसी आइटम को सम्मिलित करना ओ (एन) नहीं है, यह हमेशा ए (1) एल्गोरिदम प्रमेय में होता है। स्मृति में लाखों बाइट को स्थानांतरित करना निरंतर संचालन नहीं हो सकता है, लेकिन ओ नोटेशन उस समय के बारे में नहीं है, लेकिन जटिलता के बारे में, जो 1 – Mecki
है यदि यह निरंतर संचालन नहीं है, तो यह ओ (1) नहीं है। अवधि। सूची में डालने के लिए कोड (सरणी-आधारित सूची के लिए) है: (i = last; i> idx; --i) { सूची [i + 1] = list [i]; } सूची [idx] = item; मुझे नहीं लगता कि आप बहस करेंगे कि ओ (एन) है। आप बिग ओ – hazzen
में अपने कोड के हिस्से को अनदेखा नहीं कर सकते हैं यह ओ (1) है यदि यह किसी भी एन के लिए कुछ स्थिरांक से घिरा हुआ है। एक सरणी को व्यवस्थित करने के तरीके हैं इसलिए सम्मिलन कुशल है, जैसे इसे बाहर निकालना उन रिक्त स्थान जिनमें रिक्त स्थान की एक निश्चित मात्रा है। –
यदि आप बंच में जोड़ रहे हैं, तो आप मर्ज सॉर्ट का उपयोग कर सकते हैं। वस्तुओं को जोड़ने के लिए क्रमबद्ध करें, फिर दोनों सूचियों से कॉपी करें, यह निर्धारित करने के लिए कि कौन सी प्रतिलिपि बनाई गई है, इसकी तुलना करें। यदि आप अपनी गंतव्य सरणी का आकार बदलते हैं और पीछे की तरफ से काम करते हैं तो आप इन-प्लेस भी कॉपी कर सकते हैं।
इस समाधान की दक्षता ओ (एन + एम) + ओ (एम लॉग एम) है जहां एन मूल सूची का आकार है, और एम डालने वाली वस्तुओं की संख्या है।
संपादित करें: चूंकि इस उत्तर को कोई प्यार नहीं मिल रहा है, मैंने सोचा कि मैं इसे कुछ सी ++ नमूना कोड के साथ मांस दूंगा। मुझे लगता है कि क्रमबद्ध सूची को सरणी के बजाय एक लिंक्ड सूची में रखा जाता है। यह एल्गोरिदम को विलय की तुलना में सम्मिलन की तरह दिखने के लिए बदलता है, लेकिन सिद्धांत समान है।
// Note that itemstoadd is modified as a side effect of this function
template<typename T>
void AddToSortedList(std::list<T> & sortedlist, std::vector<T> & itemstoadd)
{
std::sort(itemstoadd.begin(), itemstoadd.end());
std::list<T>::iterator listposition = sortedlist.begin();
std::vector<T>::iterator nextnewitem = itemstoadd.begin();
while ((listposition != sortedlist.end()) || (nextnewitem != itemstoadd.end()))
{
if ((listposition == sortedlist.end()) || (*nextnewitem < *listposition))
sortedlist.insert(listposition, *nextnewitem++);
else
++listposition;
}
}
ओ (एन + एम) + ओ (एम लॉग एम) ओ (एन + एम) –
@ माइल्स रूट, बिल्कुल सही नहीं है। मैं लॉग एम> एम', तो सबसे अच्छा आप इसे सरल बना सकते हैं 'ओ (एन + (एम लॉग एम)) '। –
ओह, लॉग एम से पहले एम नहीं देखा। मुझपर ध्यान मत दो! –
मैं कहूंगा, चलिए इसका परीक्षण करें! :)
मैंने क्विकॉर्ट के साथ प्रयास किया, लेकिन क्विकॉर्ट के साथ लगभग सॉर्टिंग सरणी को सॉर्ट करना ... अच्छा, वास्तव में एक अच्छा विचार नहीं है। मैंने संशोधित एक की कोशिश की, 7 तत्वों पर काट दिया और इसके लिए सम्मिलन प्रकार का उपयोग किया। फिर भी, भयानक प्रदर्शन। मैं सॉर्ट विलय करने के लिए स्विच किया। इसे क्रमबद्ध करने के लिए बहुत सारी मेमोरी की आवश्यकता हो सकती है (यह जगह नहीं है), लेकिन प्रदर्शन क्रमबद्ध सरणी पर लगभग बेहतर है और लगभग यादृच्छिक लोगों पर समान है (प्रारंभिक क्रम दोनों के लिए लगभग एक ही समय लेता है, क्विकॉर्ट केवल थोड़ा तेज़ था)।
यह पहले से ही एक चीज़ दिखाता है: आपके प्रश्नों का उत्तर आपके द्वारा उपयोग किए जाने वाले सॉर्टिंग एल्गोरिदम पर दृढ़ता से निर्भर करता है। यदि इसकी लगभग क्रमबद्ध सूचियों पर खराब प्रदर्शन होगा, तो सही स्थिति में डालने से अंत में जोड़ने से बहुत तेज होगा और फिर इसे फिर से क्रमबद्ध किया जाएगा; और विलय सॉर्ट आपके लिए कोई विकल्प नहीं हो सकता है, क्योंकि सूची विशाल होने पर इसे बहुत अधिक बाहरी मेमोरी की आवश्यकता हो सकती है। बीटीडब्ल्यू मैंने एक कस्टम मर्ज सॉर्ट कार्यान्वयन का उपयोग किया, जो निष्पक्ष कार्यान्वयन के लिए केवल 1/2 बाहरी भंडारण का उपयोग करता है (जिसे सरणी आकार के रूप में अधिक बाहरी भंडारण की आवश्यकता होती है)।
यदि मर्ज सॉर्ट कोई विकल्प नहीं है और Quicksort निश्चित रूप से कोई विकल्प नहीं है, तो सबसे अच्छा विकल्प शायद हीप प्रकार है।
मेरे परिणाम हैं: अंत में नए तत्वों को जोड़ना और फिर सरणी को फिर से क्रमबद्ध करना सही स्थिति में उन्हें सम्मिलित करने से कई आयाम तेज था। हालांकि, मेरे शुरुआती सरणी में 10 एमओओ तत्व थे (क्रमबद्ध) और मैं एक और एमओओ (अपरिवर्तित) जोड़ रहा था। तो यदि आप 10 तत्वों की सरणी में 10 तत्व जोड़ते हैं, तो उन्हें सही ढंग से डालने से सबकुछ फिर से क्रमबद्ध करने से बहुत तेज होता है। तो आपके प्रश्न का उत्तर यह भी निर्भर करता है कि प्रारंभिक (क्रमबद्ध) सरणी कितनी बड़ी है और आप इसमें कितने नए तत्व जोड़ना चाहते हैं।
एक उच्च स्तर पर, यह एक बहुत ही साधारण समस्या है, क्योंकि आप केवल पुनरावृत्त खोज के रूप में सॉर्ट करने के बारे में सोच सकते हैं। जब आप ऑर्डर किए गए सरणी, सूची या पेड़ में कोई तत्व डालना चाहते हैं, तो आपको उस बिंदु को खोजना होगा जिस पर इसे सम्मिलित करना है। फिर आप इसे कम लागत पर, अंदर डाल दिया। तो आप एक तरह के एल्गोरिदम के बारे में सोच सकते हैं जैसे चीजों का एक समूह लेना और एक-एक करके, उचित स्थिति की खोज करना और उन्हें डालना। इस प्रकार, एक सम्मिलन क्रम (ओ (एन * एन)) एक पुनरावृत्त रैखिक खोज (ओ (एन)) है। वृक्ष, ढेर, विलय, रेडिक्स, और त्वरित क्रम (ओ (एन * लॉग (एन))) पुनरावृत्त बाइनरी खोज (ओ (लॉग (एन)) के रूप में सोचा जा सकता है)। ओ (एन) सॉर्ट होना संभव है, अगर अंतर्निहित खोज ओ (1) है जो ऑर्डर तालिका में है। (इसका एक उदाहरण 52 कार्डों में उन्हें घुमाकर 52 कार्डों को सॉर्ट कर रहा है।)
तो आपके प्रश्न का उत्तर है, एक समय में चीजों को एक साथ डालने, बनाम उन्हें बचाने और फिर उन्हें सॉर्ट करने से बहुत अंतर नहीं होना चाहिए, एक बड़े ओ अर्थ में।आप निश्चित रूप से निपटने के लिए निरंतर कारक हो सकते हैं, और वे महत्वपूर्ण हो सकते हैं।
बेशक, यदि एन छोटा है, तो 10 की तरह, पूरी चर्चा मूर्खतापूर्ण है।
क्या यह एक सरणी है, या एक लिंक्ड-लिस्ट है? मुझे पता है कि आपने 'सूची' कहा है लेकिन आपने बाइनरी-काट करने का उल्लेख किया है, जो एक सरणी का तात्पर्य है। –
टैग "एल्गोरिदम" को "एल्गोरिदम" में बदल दिया – Eric