प्रगति दिखाते समय एक बड़े संग्रह को क्रमबद्ध करें

Question

प्रगति पट्टी को अद्यतन करते समय संग्रह को सॉर्ट करने का सबसे अच्छा तरीका क्या है? वर्तमान में मैं इस तरह कोड है:

for (int i = 0; i < items.size(); i++) 
{ 
    progressBar.setValue(i); 

    // Uses Collections.binarySearch: 
    CollectionUtils.insertInOrder(sortedItems, item.get(i)); 
} 

इस प्रगति से पता चलता है, लेकिन प्रगति बार में sortedItems बड़ा बढ़ता है मदों की संख्या के रूप में धीमा। क्या किसी के पास बेहतर दृष्टिकोण है? आदर्श रूप में मैं Collections.sort() के समान इंटरफ़ेस का उपयोग करना चाहता हूं ताकि मैं अलग-अलग सॉर्टिंग एल्गोरिदम का प्रयास करूं।

कोई भी मदद महान होगी!

---

पृष्ठभूमि का एक सा है, यह कोड Lucene से दस्तावेजों (1-10 मिलियन) के बहुत सारे वापस खींच और उन पर एक कस्टम तुलनित्र चल रहा है। डेटा पर वापस डेटा लिखकर उन्हें सॉर्ट करना व्यावहारिक होने के लिए बहुत धीमा होगा। अधिकांश लागत डिस्क से आइटम को पढ़ रही है और फिर वस्तुओं पर तुलनित्र चल रही है। मेरे पीसी में मेमोरी का भार है इसलिए डिस्क पर स्वैपिंग से संबंधित कोई समस्या नहीं है।

अंत में मैं स्टीफन के समाधान के साथ गया क्योंकि यह बहुत साफ था और मुझे आसानी से एक बहु थ्रेडेड सॉर्टिंग एल्गोरिदम जोड़ने की अनुमति दी गई।

Answer 1

आप यहां सावधान रहना चाहते हैं। आपने एक एल्गोरिदम का उपयोग करना चुना है जो क्रमशः एक क्रमबद्ध डेटा संरचना बनाता है ताकि (मैं इसे ले जाऊं) आप एक प्रगति पट्टी प्रदर्शित कर सकते हैं। हालांकि, ऐसा करने में, आप ने एक सॉर्टिंग विधि चुना है जो इष्टतम प्रकार से काफी धीमी है। (दोनों प्रकार O(NlogN) हो जाएगा लेकिन वहाँ बड़े-ओ व्यवहार से प्रदर्शन करने के लिए और भी है ...)

आप चिंतित हैं, तो यह है कि यह कोई मुद्दा हो सकता है, TreeMap और Collections.sort का उपयोग कर एक विशिष्ट संग्रह सॉर्ट करने के लिए समय की तुलना करें। उत्तरार्द्ध इनपुट संग्रह को सरणी में कॉपी करके, सरणी को सॉर्ट करके और फिर इसे कॉपी करने के द्वारा काम करता है। (यह इनपुट काम करता है यदि इनपुट संग्रह एक ऐरेलिस्ट है। यदि आपको एक म्यूटेबल संग्रह के रूप में परिणाम की आवश्यकता नहीं है तो आप Collection.toArray, Arrays.sort और Arrays.asList का उपयोग कर अंतिम प्रतिलिपि से बच सकते हैं।)

एक वैकल्पिक विचार एक तुलनात्मक वस्तु का उपयोग करना होगा जो इसे कई बार ट्रैक किया गया है, और इसका उपयोग इस तरह की प्रगति को ट्रैक करने के लिए किया जाता है। आप इस तथ्य का उपयोग कर सकते हैं कि तुलनित्र को आमतौर पर लगभग N*log(N) बार कहा जा रहा है, हालांकि आपको उपयोग किए गए वास्तविक एल्गोरिदम के विरुद्ध इसे कैलिब्रेट करने की आवश्यकता हो सकती है।

संयोग से, तुलनित्र को कॉल की गिनती आपको प्रविष्टियों की गणना करके प्राप्त होने से प्रगति का एक बेहतर संकेत देगा। जब आप इस तरह को पूरा करने के करीब आते हैं तो आपको धीमी गति से दिखाई देने वाली प्रगति की दर नहीं मिलेगी।

(आप तो आप तुल्यकालन विचार करने की जरूरत पढ़ने और काउंटर लेखन अलग धागे होगा,। काउंटर volatile अतिरिक्त स्मृति यातायात की कीमत पर काम करेगा के रूप में, की घोषणा। आप, साथ ही इस मुद्दे पर ध्यान न दें सकता है अगर आप कर रहे हैं कभी कभी प्रगति बार के लिए खुश पुराने मान आदि दिखाने ... आपके प्लेटफ़ॉर्म पर निर्भर,)

---

^{1 - इस के साथ एक समस्या है। कुछ एल्गोरिदम हैं जहां सॉर्ट किए जा रहे डेटा के प्रारंभिक क्रम के आधार पर तुलना की संख्या काफी भिन्न हो सकती है। ऐसे एल्गोरिदम के लिए, काउंटर को कैलिब्रेट करने का कोई तरीका नहीं है जो "गैर-औसत" मामलों में काम करेगा।}

Answer 2

यदि आप बस क्रमबद्ध समय की तुलना कर रहे हैं, तो पहले और बाद में समय प्रिंट करें।

भविष्यवाणी करना कि जंगली में कितना समय लगेगा मुश्किल है। कुछ प्रकार के लिए यह इनपुट के आदेश पर निर्भर करता है। मैं काम के अनुपात को उत्पन्न करने के लिए i/(double) items.size() का उपयोग करता हूं और इसे एक अच्छा दिन कहता हूं। आप प्रत्येक items.size()/100 पुनरावृत्तियों को बार को अपडेट करना चुन सकते हैं। बेकार अपडेट के साथ खराब प्रगति पट्टी को स्लैम करने का कोई कारण नहीं है।

Answer 3

यहां मुद्दा छँटाई के भौतिक तंत्र है - के रूप में sortedItems बड़ा बढ़ता है, insertInOrder होगा, परिभाषा के द्वारा, अब, यह संभवत: O(n lg n) + O(n) आपरेशन (बाइनरी खोज का उपयोग कर अगले छोटी से छोटी वस्तु को खोजने के लिए है और फिर आइटम डालने के रूप में लेने)। यह अपरिहार्य है कि जैसे ही आपका संग्रह बड़ा हो जाता है, उचित स्थान पर अगला आइटम डालने में अधिक समय लगेगा।

एक प्रगति पट्टी का अनुमान लगाने का एकमात्र तरीका जिसका समय रैखिक रूप से बढ़ता है, lg फ़ंक्शन के विपरीत के समान कुछ अनुमान का उपयोग करना होगा, क्योंकि पहले 1000 आइटमों को सॉर्ट करने में पिछले 10 को सॉर्ट करने के समान समय लग सकता है (जो कि है बेशक एक सामान्यीकरण)।

Answer 4

क्या आप indeterminate प्रगति पट्टी का उपयोग करने में सक्षम हैं? यह अभी भी उपयोगकर्ता को कुछ प्रतिक्रिया प्रदान करता है कि कुछ हो रहा है। आपका कोड इस तरह दिखेगा:

progessbar.setIndeterminate(true); 
ArrayList sorted = new ArrayList(items); 
Colletions.sort(sorted); 

progessBar.setString("Hey you're done!"); 

मुझे लगता है कि यदि आप इसके बजाय द्विआधारी प्रविष्टि तरह आप कर रहे हैं की तुलना में तरह में बनाया का उपयोग कर, से बाहर बहुत बेहतर प्रदर्शन प्राप्त करने के लिए जा रहे हैं।

Answer 5

मैं कुछ खो चुके होंगे क्योंकि और कोई नहीं यह उल्लेख किया है, लेकिन यह अपने स्रोत List वस्तु के क्रम प्रकार की तरह लगता है हे (एन) समय में RandomAccess और इसलिए अपने Collections.binarySearch मंगलाचरण चल रहा है की एक implementor नहीं है। इससे चीजों को धीमा कर दिया जाएगा, बहुत ध्यान से, जब आप सॉर्ट करने के लिए वस्तुओं की संख्या को दोगुना करते हैं।

और इसके अलावा, यदि आप उदाहरण के लिए LinkedListsortedItems के लिए उपयोग कर रहे हैं तो सम्मिलन भी ओ (एन) है।

यदि ऐसा है, तो यह सही समझ में आता है कि जब आप 1 मिलियन से 2 मिलियन आइटम तक जाते हैं, तो आपका अनुमानित समय लगभग दोगुना हो जाएगा।

के निदान के लिए जो 2 List वस्तुओं की समस्या पैदा करने वाले

1. है प्रगति बार शुरू से ही धीमी है, यह items है; एक अलग कंटेनर का उपयोग करने का प्रयास करें, कुछ पेड़-आश या हैश-वाई
2. यदि प्रगति पट्टी धीमी और धीमी हो जाती है क्योंकि यह 100% के करीब हो जाती है, तो यह sortedItems है; उपरोक्त

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

Answer 6

क्यों अपने स्वयं के मर्ज सॉर्ट को लागू नहीं करते हैं (जो संग्रह .sort क्या कर रहा है) और एल्गोरिदम के मुख्य बिंदुओं पर प्रगति पट्टी को अपडेट करें (कहें, सरणी के 5% से अधिक के प्रत्येक विलय के बाद)?

Answer 7

प्रगति पट्टी पर एक सरल दृष्टिकोण यह है।

आप मॉड का उपयोग कर आइटम आकार के बावजूद प्रगति को अद्यतन करने के लिए कॉल की संख्या को ठीक कर सकते हैं। उदाहरण के लिए,

public void run(int total) { 
    int updateInterval = total/10; 
    System.out.println("interval = " + updateInterval); 
    for(int i = 0; i < total; i++) { 
     if(i % updateInterval == 0) { 
      printProgress((float)i/total * 100f); 
     } 
     // do task here 
    } 
} 

private void printProgress(float value) { 
    System.out.println(value + "%"); 
} 

यह प्रगति बार 10 बार अद्यतन (या 9? सीमा की स्थिति की जाँच करें) आकार 10 या 10 लाख है कि क्या होगा।

यह केवल एक उदाहरण है, तदनुसार मूल्यों को समायोजित करें।