फास्ट सॉर्टिंग जहां ऑर्डर शायद ही कभी बदलता है

Question

मैं एक स्क्रॉलिंग व्यू (रेड अलर्ट या ज़ेल्डा सोचता हूं) के साथ 2 डी गेम पर काम कर रहा हूं लेकिन मैं ड्राइंग के साथ चिपक रहा हूं।

मूल रूप से मानचित्र पर दो प्रकार की वस्तुएं खींची जाती हैं। कुछ ने निश्चित पदों (पेड़ों और इमारतों की तरह) तय किए हैं और अन्य चारों ओर घूमते हैं (खिलाड़ी, दुश्मन, उड़ान तीर)।

चीजें एक सही तरीका है कि वे जरूरत में एक दूसरे के सामने प्रकट करने के लिए के लिए एक विशेष क्रम में तैयार करने के लिए किया जा (दूर की वस्तुओं को पहली और "कैमरा" की दिशा में काम)।

अभी मैं सभी वस्तुओं (दोनों प्रकार के) हर बार खेल अद्यतन प्रति सेकंड (100 बार) और यह CPU समय का एक बड़ा बेकार की तरह एक का मानना ​​है की सूची को क्रमबद्ध कर रहा हूँ। वस्तुओं का क्रम शायद ही कभी बदलता है, और जब वे करते हैं तो वे आमतौर पर सूची में केवल एक स्थिति को ऊपर या नीचे ले जाते हैं।

एक और मुद्दा यह है कि केवल स्क्रीन पर मौजूद वस्तुओं को ही माना जाना चाहिए। चूंकि नक्शे वस्तुओं के 1000s के साथ काफी बड़े हो सकते हैं, इसलिए मैं प्रति सेकंड 100 बार उन्हें सॉर्ट नहीं करना चाहता हूं।

आप कैसे सुझाव देंगे कि मैं इसे हल करूँ?

Answer 1

Bubble Sort का सबसे अच्छा मामला तब होता है जब तत्व पहले ही सॉर्ट किए जाते हैं। आपको उस मामले में ओ (एन) तुलना मिल जाएगी। विकिपीडिया के अनुसार:

कंप्यूटर ग्राफिक्स में यह अपनी क्षमता एक बहुत छोटा त्रुटि लगभग हल कर सरणियों में (सिर्फ दो तत्वों की अदला-बदली की तरह) का पता लगाने और सिर्फ रैखिक जटिलता (2n) के साथ इसे ठीक करने के लिए लोकप्रिय है।

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

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

Answer 2

ट्रैक रखें कि कौन सी ऑब्जेक्ट्स वेक्टर में स्क्रीन पर हैं और इसके अंत में नई दृश्यमान वस्तुएं जोड़ें। सॉर्टिंग के लिए बबल सॉर्ट या सम्मिलन सॉर्ट का उपयोग करें। यह यादृच्छिक डेटा के लिए लगातार अक्षम है, लेकिन लगभग क्रमबद्ध डेटा के लिए ~ ओ (एन)।

Answer 3

बबल और सम्मिलन प्रकार से सहमत हुए।

मैं प्रकार के बिना अन्य विचार है: अगर कभी-कभार ही आदेश को बदल, आप केवल परिवर्तन इतिहास पर नज़र रखने और जब प्रकार की जरूरत व्यवस्था बहाल कर सकता है। इसके अलावा, यदि तत्वों को जोड़ा या हटाया नहीं गया है, तो मूल आदेशित सूची के स्नैपशॉट को पुनर्स्थापित करें, यह बहुत आसान और तेज़ होगा। अगर मैं आपका प्रश्न स्पष्ट रूप से समझ गया।

Answer 4

प्राथमिकता क्यूई, या संभवतः एक दोगुनी-लिंक्ड सूची का उपयोग करने के बारे में सोचें ताकि आप जेड ऑर्डर के आधार पर ब्रूट-फोर्सिंग की बजाय आवश्यकता में सीधे आइटम को स्थानांतरित कर सकें। आपको क्लिप क्षेत्रों की पूरी तरह से जांच करनी चाहिए।

Answer 5

100 ऑब्जेक्ट्स को सॉर्ट करना बहुत लंबा नहीं लगेगा। लेकिन यदि प्रदर्शन वास्तव में मायने रखता है, और आप जानते हैं कि सूची लगभग क्रमबद्ध होने के समान है, ऑर्डर के बाहर कुछ आइटम के साथ, विलय सॉर्ट या टिम सॉर्ट एल्गोरिदम आपको अच्छे प्रदर्शन की संभावना है।इसमें एक सूची के लिए ओ (एन) प्रदर्शन है जो पहले ही सॉर्ट किया गया है, या जिसमें ऑर्डर के कुछ ही तत्व हैं।

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

वास्तव में, मानक जावा विधि का इस्तेमाल किया मर्ज तरह जावा 6 तक सॉर्टिंग, और जावा के साथ TimSort करने के लिए बदल 7.