क्या तेज़ है: प्राथमिकता कतार में डालना, या पीछे से क्रमबद्ध करना?तेज़ क्या है: प्राथमिकता कतार में डालना, या पीछे से क्रमबद्ध करना?
मैं कुछ वस्तुओं को उत्पन्न कर रहा हूं जिन्हें मुझे अंत में क्रमबद्ध करने की आवश्यकता है। मैं सोच रहा था, जटिलता के मामले में तेज़ी से क्या है: उन्हें प्राथमिकता_क्यू या समान डेटा संरचना में सीधे डालना, या अंत में एक प्रकार एल्गोरिदम का उपयोग करना?
एक प्राथमिकता कतार में n आइटम सम्मिलित करना asymptotic जटिलता ओ (n लॉग n) जटिलता के मामले में ऐसा है, तो यह एक बार sort का उपयोग कर, अंत में तुलना में अधिक कुशल नहीं है होगा।
चाहे यह अभ्यास में अधिक कुशल है वास्तव में निर्भर करता है। आपको परीक्षण करने की ज़रूरत है। असल में, व्यावहारिक रूप से, प्रविष्टि एक रैखिक सरणी में (प्रविष्टि प्रकार के रूप में, एक ढेर के बिना) में भी सबसे कुशल हो सकता है, भले ही असम्बद्ध रूप से खराब रनटाइम हो।
मुझे लगता है कि सम्मिलन लगभग सभी मामलों में अधिक कुशल है जहां आप डेटा उत्पन्न कर रहे हैं (यानी यह पहले से ही सूची में नहीं है)।
एक प्राथमिकता कतार आपके जाने के लिए सम्मिलन का एकमात्र विकल्प नहीं है। जैसा कि अन्य उत्तरों में बताया गया है कि एक बाइनरी पेड़ (या संबंधित आरबी-पेड़) समान रूप से कुशल है।
मैं यह भी जांचूंगा कि प्राथमिकता कतार कैसे कार्यान्वित की जाती है - कई बी-पेड़ों पर पहले से ही आधारित हैं लेकिन कुछ कार्यान्वयन तत्वों को निकालने में बहुत अच्छे नहीं हैं (वे अनिवार्य रूप से पूरी कतार के माध्यम से जाते हैं और सर्वोच्च प्राथमिकता को देखते हैं) ।
प्राथमिकता कतार आमतौर पर एक ढेर के रूप में लागू किया जाता है। एक हीप का उपयोग करके सॉर्टिंग क्विकॉर्ट की तुलना में औसत धीमी गति से होती है, सिवाय इसके कि क्विकॉर्ट में खराब स्थिति का खराब प्रदर्शन होता है। इसके अलावा ढेर अपेक्षाकृत भारी डेटा संरचनाएं हैं, इसलिए अधिक ओवरहेड है।
मैं अंत में क्रमबद्ध करना चाहता हूं।
अपेक्षाकृत भारी? नहीं, यह एक साधारण सरणी है, और सिफ्ट-डाउन और बबल-अप ऑपरेशंस भी उतने ही सरल हैं। औसत पर क्विकॉर्ट औसत तेज क्यों है इस तथ्य से संबंधित है कि हेपसोर्ट को प्रत्येक तत्व को कम से कम दो बार स्थानांतरित करना होता है (यह दो पास में काम करता है)। हालांकि, यह वास्तव में यहां मामला नहीं है क्योंकि हम ऑनलाइन सॉर्टिंग करते हैं, इसलिए इस संदर्भ में हेपॉर्ट और क्विकॉर्ट के सापेक्ष रनटाइम को सावधानीपूर्वक पुन: मूल्यांकन किया जाना चाहिए। –
डेटा पर निर्भर करता है, लेकिन मुझे आमतौर पर InsertSort तेज़ी से लगता है।
मेरे पास एक संबंधित प्रश्न था, और मैंने अंत में पाया कि बाधा यह थी कि मैं एक डिफर्ड प्रकार कर रहा था (केवल जब मैं इसे समाप्त कर देता था) और बड़ी मात्रा में वस्तुओं पर, मुझे आमतौर पर सबसे खराब- केस-परिदृश्य मेरी quicksort (पहले से ही क्रम में) के लिए, तो मैं एक डालने के लिए इस्तेमाल किया प्रकार
Sorting 1000-2000 elements with many cache misses
तो अपने डेटा का विश्लेषण!
बाइनरी खोज पेड़ का उपयोग क्यों नहीं करें? फिर तत्वों को हर समय क्रमबद्ध किया जाता है और सम्मिलन लागत प्राथमिकता कतार के बराबर होती है। रेडब्लैक संतुलित पेड़ के बारे में पढ़ें here
मुझे लगता है कि प्राथमिकता कतार स्वयं-संतुलित बाइनरी कोशिशों की तुलना में अधिक कुशल होगी क्योंकि बाद में एक ही कैश-अनुकूल व्यवहार नहीं प्रदान करता है और ढेर स्मृति आवंटन पर भरोसा करता है। –
@ कोनराड: यह मेरे सरल परीक्षण का परिणाम प्रतीत होता है। मैं वास्तव में मल्टीसेट को भयानक होने की उम्मीद कर रहा था, ठीक उसी तरह स्मृति आवंटन के कारण, लेकिन यह * बुरा नहीं है, केवल 'std :: sort' से पांच गुना धीमा है। –
आपके पहले प्रश्न (जो तेज़ है) पर: यह निर्भर करता है। बस इसका परीक्षण करें। मान लें कि आप एक सदिश में अंतिम परिणाम चाहते हैं, विकल्प कुछ इस तरह दिख सकता है:
#include <iostream>
#include <vector>
#include <queue>
#include <cstdlib>
#include <functional>
#include <algorithm>
#include <iterator>
#ifndef NUM
#define NUM 10
#endif
int main() {
std::srand(1038749);
std::vector<int> res;
#ifdef USE_VECTOR
for (int i = 0; i < NUM; ++i) {
res.push_back(std::rand());
}
std::sort(res.begin(), res.end(), std::greater<int>());
#else
std::priority_queue<int> q;
for (int i = 0; i < NUM; ++i) {
q.push(std::rand());
}
res.resize(q.size());
for (int i = 0; i < NUM; ++i) {
res[i] = q.top();
q.pop();
}
#endif
#if NUM <= 10
std::copy(res.begin(), res.end(), std::ostream_iterator<int>(std::cout,"\n"));
#endif
}
$ g++ sortspeed.cpp -o sortspeed -DNUM=10000000 && time ./sortspeed
real 0m20.719s
user 0m20.561s
sys 0m0.077s
$ g++ sortspeed.cpp -o sortspeed -DUSE_VECTOR -DNUM=10000000 && time ./sortspeed
real 0m5.828s
user 0m5.733s
sys 0m0.108s
तो, std::sort धड़कता std::priority_queue, इस मामले में।लेकिन हो सकता है कि आपके पास std:sort बेहतर या खराब हो, और हो सकता है कि आपके पास ढेर का बेहतर या खराब कार्यान्वयन हो। या यदि बेहतर या बुरा नहीं है, तो आपके सटीक उपयोग के लिए केवल उतना ही कम उपयुक्त है, जो मेरे आविष्कारित उपयोग से अलग है: "मान वाले सॉर्ट किए गए वेक्टर बनाएं"।
मैं बहुत से विश्वास के साथ कह सकता हूं कि यादृच्छिक डेटा std::sort का सबसे खराब मामला नहीं मारा जाएगा, इसलिए एक अर्थ में यह परीक्षण इसे चापलूसी कर सकता है। लेकिन std::sort के अच्छे कार्यान्वयन के लिए, इसका सबसे खराब मामला निर्माण करना बहुत कठिन होगा, और वास्तव में वैसे भी वह सब बुरा नहीं हो सकता है।
संपादित करें:
#elif defined(USE_SET)
std::multiset<int,std::greater<int> > s;
for (int i = 0; i < NUM; ++i) {
s.insert(std::rand());
}
res.resize(s.size());
int j = 0;
for (std::multiset<int>::iterator i = s.begin(); i != s.end(); ++i, ++j) {
res[j] = *i;
}
#else
$ g++ sortspeed.cpp -o sortspeed -DUSE_SET -DNUM=10000000 && time ./sortspeed
real 0m26.656s
user 0m26.530s
sys 0m0.062s
अपने दूसरे प्रश्न (जटिलता) करने के लिए:: मैं एक मल्टीसेट का उपयोग करते हैं, के बाद से कुछ लोगों को एक पेड़ का सुझाव दिया है जोड़ा वे सब हे रहे हैं (एन एन लॉग इन करें), बारीकियों कार्यान्वयन अनदेखी विवरण जैसे स्मृति आवंटन ओ (1) है या नहीं (vector::push_back और अंत में डालने के अन्य रूपों को एम (1) को अमूर्त किया गया है) और यह मानते हुए कि "सॉर्ट" से आप तुलनात्मक प्रकार का मतलब रखते हैं। अन्य प्रकार के प्रकार में कम जटिलता हो सकती है।
क्यों वेक्टर में कतार के तत्व डालते हैं? –
@static_rtti: सिर्फ इसलिए कि मुझे नहीं पता कि आप उनके साथ क्या करना चाहते हैं, इसलिए मैं कुछ कर रहा हूं। प्राथमिकता कतार की गति का मूल्यांकन करने के लिए सभी पॉपों को करना आवश्यक है, लेकिन मुझे लगता है कि मुझे मूल्यों का उपयोग करने की आवश्यकता नहीं थी। मुझे संदेह है कि उन्हें वेक्टर में जोड़ने से 'पॉप' की तुलना में बहुत अधिक समय लगता है, लेकिन आपको अपना खुद का परीक्षण चलाने चाहिए जो आपके वास्तविक उद्देश्य के लिए जितना संभव हो सके। –
परीक्षण के लिए धन्यवाद! –
जहां तक मैं समझता हूं, आपकी समस्या को प्राथमिकता कतार की आवश्यकता नहीं है, क्योंकि आपके कार्य "सब कुछ के बाद, कई प्रविष्टियां करें" जैसे लगता है। यह एक लेजर से शूटिंग पक्षियों की तरह है, एक उचित उपकरण नहीं है। इसके लिए मानक सॉर्टिंग तकनीक का प्रयोग करें।
आपको प्राथमिकता कतार की आवश्यकता होगी, यदि आपका कार्य संचालन के अनुक्रम का अनुकरण करना था, जहां प्रत्येक ऑपरेशन या तो "सेट में एक तत्व जोड़ें" या "सेट से सबसे छोटा/सबसे बड़ा तत्व निकालें" हो सकता है। उदाहरण के लिए, ग्राफ पर सबसे छोटा रास्ता खोजने की समस्या में इसका उपयोग किया जा सकता है। यहां आप मानक सॉर्टिंग तकनीकों का उपयोग नहीं कर सकते हैं।
एक अधिकतम-डालने प्राथमिकता कतार संचालन पर ओ (एलजी एन)
स्टैक ओवरफ़्लो में आपका स्वागत है। आपका उत्तर सटीक है, जहां तक यह जाता है, लेकिन यह सवाल की पूछताछ की दो तकनीकों की तुलना नहीं करता है। उदाहरण के लिए, यदि आप प्राथमिकता कतार में एन सम्मिलित संचालन करते हैं, तो आपके पास ओ (एन एलजी एन) संचालन है; यदि आप डेटा को पीछे से क्रमबद्ध करते हैं, तो आपके पास आमतौर पर ओ (एन एलजी एन) संचालन भी होते हैं। तो, तुलना में स्थिरांक का विश्लेषण शामिल होगा - जो मुश्किल हो जाता है। –
यह शायद आप के लिए एक छोटे से खेल में देर से जहाँ तक आपके प्रश्न का संबंध है आता है, लेकिन के पूरा हो जाने।
परीक्षण आपके विशिष्ट कंप्यूटर आर्किटेक्चर, कंपाइलर और कार्यान्वयन के लिए इस प्रश्न का उत्तर देने का सबसे अच्छा तरीका है। इसके अलावा, सामान्यीकरण हैं।
सबसे पहले, प्राथमिकता कतार जरूरी नहीं है ओ (एन लॉग एन)।
यदि आपके पास पूर्णांक डेटा है, तो प्राथमिकता पंक्तियां हैं जो ओ (1) समय में काम करती हैं। बीचर एंड मेयर का 1 99 2 का प्रकाशन "विभाजन के लिए मोर्फोलॉजिकल दृष्टिकोण: वाटरशेड ट्रांसफॉर्मेशन" पदानुक्रमित कतारों का वर्णन करता है, जो सीमित सीमा के साथ पूर्णांक मानों के लिए बहुत तेज़ी से काम करता है। ब्राउन के 1 9 88 के प्रकाशन "कैलेंडर कतार: सिमुलेशन इवेंट सेट समस्या के लिए एक तेज़ 0 (1) प्राथमिकता कतार कार्यान्वयन" एक और समाधान प्रदान करता है जो पूर्णांक की बड़ी श्रृंखला के साथ अच्छी तरह से काम करता है - दो दशक के काम के बाद ब्राउन के प्रकाशन ने पूर्णांक करने के लिए कुछ अच्छे परिणाम दिए हैं प्राथमिकता कतार तेज़। लेकिन इन कतारों की मशीनरी जटिल हो सकती है: बाल्टी प्रकार और रेडिक्स प्रकार अभी भी ओ (1) ऑपरेशन प्रदान कर सकते हैं। कुछ मामलों में, आप ओ (1) प्राथमिकता कतार का लाभ उठाने के लिए फ़्लोटिंग-पॉइंट डेटा को भी मापने में सक्षम हो सकते हैं।
यहां तक कि फ़्लोटिंग-पॉइंट डेटा के सामान्य मामले में, ओ (एन लॉग एन) थोड़ा भ्रामक है।Edelkamp की किताब
आप कर सकते हैं के रूप में: "अनुमानी खोजें: सिद्धांत और अनुप्रयोग" विभिन्न प्राथमिकता कतार एल्गोरिदम (याद है, प्राथमिकता कतारों छंटाई और ढेर प्रबंधन के बराबर हैं) के लिए समय जटिलता दिखा नीचे दिए सुविधाजनक टेबल है देखें, कई प्राथमिकता कतारों में ओ (लॉग एन) लागत केवल प्रविष्टि के लिए नहीं है, बल्कि निष्कर्षण के लिए भी, और यहां तक कि कतार प्रबंधन भी है! जबकि गुणांक को आमतौर पर एल्गोरिदम की समय जटिलता को मापने के लिए गिरा दिया जाता है, लेकिन इन लागतों को अभी भी जानने के लायक हैं।
लेकिन इन सभी कतारों में अभी भी समय जटिलताएं हैं जो तुलनीय हैं। कौन सा सबसे अच्छा है? क्रिस एल लुएन्गो हैंड्रिक्स द्वारा एक 2010 का पेपर "छवि विश्लेषण के लिए प्राथमिकता पंक्तियों की समीक्षा" इस सवाल को संबोधित करता है।
हेंड्रिक्स 'पकड़ परीक्षण में, एक प्राथमिकता कतार रेंज [0,50] में एन यादृच्छिक संख्या के साथ वरीयता प्राप्त किया गया था। कतार के शीर्ष-तत्व को तब हटा दिया गया था, [0,2] श्रेणी में यादृच्छिक मूल्य से वृद्धि हुई, और फिर कतारबद्ध की गई। इस ऑपरेशन को 10^7 बार दोहराया गया था। यादृच्छिक संख्याओं को उत्पन्न करने के ऊपरी हिस्से को मापा समय से घटाया गया था। सीढ़ी कतार और पदानुक्रमिक ढेर ने इस परीक्षण से काफी अच्छा प्रदर्शन किया।
कतारों को प्रारंभ करने और खाली करने के लिए प्रति तत्व समय भी मापा गया था - ये परीक्षण आपके प्रश्न के लिए बहुत प्रासंगिक हैं।
आप देख सकते हैं, अलग कतारों अक्सर enqueueing और dequeueing करने के लिए बहुत अलग अलग प्रतिक्रियाएं था। इन आंकड़ों का अर्थ यह है कि प्राथमिकता कतार एल्गोरिदम हो सकते हैं जो निरंतर संचालन के लिए श्रेष्ठ हैं, केवल भरने के लिए एल्गोरिदम का कोई सर्वश्रेष्ठ विकल्प नहीं है और फिर प्राथमिकता कतार (ऑपरेशन जो आप कर रहे हैं) खाली कर रहे हैं।
के अपने प्रश्नों पर वापस देखें:
क्या तेज है: एक प्राथमिकता कतार में डालने, या पूर्वव्यापी छँटाई?
ऊपर दिखाए गए अनुसार, प्राथमिकता कतारों को कुशल बनाया जा सकता है, लेकिन अभी भी सम्मिलन, निष्कासन और प्रबंधन के लिए लागतें हैं। एक वेक्टर में सम्मिलन तेजी से है। यह ओ (1) अमूर्त समय में है, और कोई प्रबंधन लागत नहीं है, साथ ही वेक्टर ओ (एन) पढ़ने के लिए है।
वेक्टर को सॉर्ट करने से आपको ओ (एन लॉग एन) लगता है कि आपके पास फ्लोटिंग-पॉइंट डेटा है, लेकिन इस बार जटिलता प्राथमिकता कतारों जैसी चीजों को छुपा नहीं रही है। (हालांकि, आपको कुछ सावधान रहना होगा, हालांकि, क्विक्सॉर्ट कुछ डेटा पर बहुत अच्छी तरह से चलता है, लेकिन इसमें ओ (एन^2) की सबसे बुरी स्थिति की जटिलता है। कुछ कार्यान्वयन के लिए, यह एक गंभीर सुरक्षा जोखिम है।)
मुझे डर है कि मेरे पास सॉर्टिंग की लागत के लिए डेटा नहीं है, लेकिन मैं कहूंगा कि रेट्रोएक्टिव सॉर्टिंग आप जो बेहतर करने की कोशिश कर रहे हैं उसके सार को कैप्चर करती है और इसलिए बेहतर विकल्प है। पोस्ट-सॉर्टिंग बनाम प्राथमिकता कतार प्रबंधन की सापेक्ष जटिलता के आधार पर, मैं कहूंगा कि पोस्ट-सॉर्टिंग तेज होना चाहिए। लेकिन फिर, आपको इसका परीक्षण करना चाहिए।
मैं कुछ वस्तुओं को उत्पन्न कर रहा हूं जिन्हें मुझे अंत में क्रमबद्ध करने की आवश्यकता है। मैं सोच रहा था, जटिलता के मामले में तेज़ी से क्या है: उन्हें प्राथमिकता-कतार या समान डेटा संरचना में सीधे डालना, या अंत में एक प्रकार एल्गोरिदम का उपयोग करना?
हम शायद इसे ऊपर से ढंक चुके हैं।
एक और सवाल है जिसे आपने नहीं पूछा था, हालांकि। और शायद आप पहले से ही जवाब जानते हैं। यह स्थिरता का सवाल है। सी ++ एसटीएल का कहना है कि प्राथमिकता कतार को "सख्त कमजोर" आदेश बनाए रखना चाहिए। इसका मतलब है कि समान प्राथमिकता के तत्व अतुलनीय हैं और किसी भी क्रम में रखा जा सकता है, क्योंकि "कुल आदेश" के विपरीत जहां प्रत्येक तत्व तुलनीय है। (here ऑर्डर करने का एक अच्छा विवरण है।) सॉर्टिंग में, "सख्त कमजोर" एक अस्थिर प्रकार के समान होता है और "कुल क्रम" स्थिर प्रकार के समान होता है।
उपरोक्त यह है कि यदि समान प्राथमिकता के तत्व उसी क्रम में रहना चाहिए तो आपने उन्हें अपनी डेटा संरचना में धक्का दिया है, तो आपको एक स्थिर प्रकार या कुल क्रम की आवश्यकता है। यदि आप सी ++ एसटीएल का उपयोग करने की योजना बना रहे हैं, तो आपके पास केवल एक विकल्प है। प्राथमिकता कतार एक सख्त कमजोर आदेश का उपयोग करती है, इसलिए वे यहां बेकार हैं, लेकिन एसटीएल एल्गोरिदम पुस्तकालय में "स्थिर_आर्ट" एल्गोरिदम काम पूरा कर लेगा।
मुझे आशा है कि इस मदद करता है। मुझे बताएं कि क्या आप किसी भी कागजात का एक प्रतिलिपि चाहते हैं या स्पष्टीकरण चाहते हैं। :-)
इस महान जवाब के लिए धन्यवाद! –
मुझे 2007 से "एक उच्च प्रदर्शन प्राथमिकता पंक्तियों का प्रायोगिक अध्ययन" से एक और दिलचस्प लेकिन पुराना पेपर मिला। यह पीटर सैंडर्स से कम से कम एक उच्च प्रदर्शन डेटा संरचनाओं का संदर्भ देता है जिसे अनुक्रम ढेर कहा जाता है http://algo2.iti.kit.edu/sanders/papers/falenex.ps.gz http://www.mpi-inf.mpg.de/ ~ सैंडर्स/प्रोग्राम/spq/ – Karussell
वाह। मुझे SO प्यार है क्योंकि आपके जैसे लोग हैं –
डेटा की मात्रा के बारे में कोई विवरण? क्या आपको एक पूर्ण प्रकार/स्थिर सॉर्ट या आंशिक सॉर्ट/nth_element की आवश्यकता होगी? – MadH
मुझे एक पूर्ण प्रकार की आवश्यकता है, लेकिन इसे स्थिर नहीं होना चाहिए। मैं विशिष्ट समस्या आकार के प्रदर्शन की तुलना में जटिलता में अधिक रूचि रखता हूं, इसलिए मैंने किसी को निर्दिष्ट नहीं किया है। –
लगभग एक डुप्लिकेट (लेकिन जावा के लिए, इसलिए मैंने बंद करने के लिए वोट नहीं दिया): http://stackoverflow.com/questions/3607593/is-it-faster-to-add-to-a-collection-then-sort- यह-या-ऐड-टू-ए-सॉर्ट-संग्रह – Thilo