क्या मैं एक सूची बना सकता हूं, और इसे एक ही समय में सॉर्ट कर सकता हूं?

Question

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

तो, इस समय मैं मूल रूप से इस मिल गया है:

my_list = [] 

for item in "query for stuff": 
    my_list.append("query for %s data" % item) 

my_list.sort() 

do_stuff(my_list) 

"सामान के लिए क्वेरी" बिट सॉफ्टवेयर, जो मुझे एक iterable दे देंगे साथ क्वेरी इंटरफेस है। my_list को पुनरावर्तनीय सामग्री की सामग्री से डेटा की एक सूची रखने की आवश्यकता है। ऐसा करने से, मैं पहली सूची के लिए पूछताछ कर रहा हूं, फिर डेटा निकालने और इसे my_list में डालने के लिए इसे लूप कर रहा हूं। तो मैं इसे सॉर्ट कर रहा हूँ। आखिरकार, मैं do_stuff() विधि के साथ सामान कर रहा हूं, जो उस पर लूप करेगा और प्रत्येक आइटम को सामान देगा।

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

for item in "query for stuff": 
    my_list.append_sorted(item) 

इसे इस तरह यह करने के लिए कोशिश कर परेशान कर रहा लायक है, या मैं बस सूची निर्माण, और फिर इसे छँटाई करने के लिए छड़ी चाहिए?

धन्यवाद!

Answer 1

संक्षिप्त उत्तर यह है: यह इसके लायक नहीं है।

insertion sort पर एक नज़र डालें। सबसे बुरी स्थिति चलने का समय O(n^2) है (औसत मामला भी वर्गबद्ध है)। दूसरी ओर, Python's sort (जिसे Timsort भी कहा जाता है) सबसे खराब मामले में O(n log n) ले जाएगा।

हां, जैसा कि आप डालने के रूप में सूचीबद्ध क्रमबद्ध रखने के लिए यह "प्रतीत होता है" क्लीनर करता है, लेकिन यह एक झूठ है। इसका कोई वास्तविक लाभ नहीं है। सम्मिलन प्रकार का उपयोग करने पर विचार करने का एकमात्र समय तब होता है जब आपको प्रत्येक सम्मिलन के बाद क्रमबद्ध सूची दिखाने की आवश्यकता होती है।

Answer 2

दो दृष्टिकोण आकस्मिक रूप से समकक्ष हैं।

सॉर्टिंग ओ (एन एलजी एन) है (पाइथन डिफ़ॉल्ट रूप से टिमसॉर्ट का उपयोग करता है, बहुत छोटे सरणी को छोड़कर), और क्रमबद्ध सूची में डालने से ओ (एलजी एन) (बाइनरी सर्च का उपयोग करके) होता है, जिसे आपको करना होगा एन बार

प्रैक्टिस में, एक विधि या दूसरा थोड़ा तेज़ हो सकता है, इस पर निर्भर करता है कि आपका डेटा कितना पहले से सॉर्ट किया गया है।

संपादित करें: मैं ग्रहण करने के बाद आप मिल गया है एक क्रमबद्ध सूची के बीच में डालने सम्मिलन बिंदु निरंतर समय हो सकता है कि (यानी सूची एक लिंक्ड सूची है, जो डेटा संरचना क्या तुम करोगी है की तरह व्यवहार ऐसे एल्गोरिदम के लिए उपयोग करें)। यह शायद पाइथन सूचियों के मामले में नहीं है, जैसा कि स्वेन द्वारा इंगित किया गया है। यह "सूची क्रमबद्ध रखें" दृष्टिकोण ओ (एन^2), यानी सम्मिलन प्रकार बना देगा।

मैं "शायद" कहता हूं क्योंकि कुछ सूची कार्यान्वयन सूची बढ़ने के साथ सरणी से लिंक की गई सूची में स्विच करते हैं, सबसे उल्लेखनीय उदाहरण CoreFoundation/Cocoa में CFArray/NSArray है। यह पायथन के साथ मामला हो सकता है या नहीं भी हो सकता है।

Answer 3

bisect मॉड्यूल पर एक नज़र डालें। यह आपको सूची आदेश बनाए रखने के लिए विभिन्न टूल देता है। आपके मामले में, आप शायद bisect.insort का उपयोग करना चाहते हैं।

for item in query_for_stuff(): 
    bisect.insort(my_list, "query for %s data" % item)