तुलनात्मक बनाम ट्रीसेट के साथ सूची

Question

विकल्प 1: एक सूची बनाएं जो तुलनात्मक लागू करती है और जब भी आप कोई मूल्य जोड़ते हैं तो संग्रह .sort (सूची l) का उपयोग करके इसे सॉर्ट करें। विकल्प 2: एक ट्रीसेट बनाएं (जो स्वयं को हर समय क्रमबद्ध रखता है)।

कौन सा तेजी से होगा? मैं यह पूछ रहा हूं क्योंकि सूची मुझे ListIterator का विकल्प देती है जो मुझे अपने मामले में चाहिए, क्योंकि यह मुझे पुनरावृत्ति के दौरान एक तत्व जोड़ने देता है।

Answer 1

सबसे महत्वपूर्ण मतभेद:

Criterion  | List with Collections.sort | TreeSet 
----------------+----------------------------+--------- 
cost of adding | O(n log n)     | O(log n) 
equal sort keys | permitted     | eliminated as duplicates 
iteration  | bidirectional, can insert | unidirectional, can not insert 

जब एक ConcurrentModificationException प्राप्त किए बिना पुनरावृत्ति एक तत्व सम्मिलित करने के लिए, आप कर सकते हैं:

for (E e : new ArrayList<E>(collection)) { 
    // some other code 

    collection.add(anotherE); 
} 

Answer 2

यहां ट्रीसेट का उपयोग करें।

ट्रीसेट में जोड़ना log(n) ऑपरेशन है। सूची में जोड़ना समय है, लेकिन इसे क्रमबद्ध करना n log(n) है।

Answer 3

Collections.sort nlog के साथ एक संशोधित मर्ज-तरह का उपयोग करता है (एन) सॉर्ट टाइम। यदि आप प्रत्येक अतिरिक्त पर विधि को कॉल करते हैं तो आप n^2log (n) समय के साथ समाप्त हो सकते हैं। जबकि ट्रीसेट में सम्मिलन गारंटीकृत लॉग (एन) है। तो यदि आप इसे हर अतिरिक्त पर कॉल करते हैं तो यह n.log (n) बन जाता है। तो मैं इसके बजाए ट्रीसेट का उपयोग करने का सुझाव दूंगा। लेकिन ट्रीसेट डुप्लिकेट की अनुमति नहीं देता है, जिससे आपके निर्णय को प्रभावित हो सकता है।

यदि आप सूची का उपयोग कर रहे हैं, तो Collections.sort का उपयोग करने के बजाय, एक चीज है जिसे आप अनुकूलित करने के लिए कर सकते हैं; जैसा कि आप जानते हैं कि प्रत्येक बार जब आप सूची में तत्व डालते हैं, तो सूची पहले ही सॉर्ट की जाती है, इसलिए यहां सम्मिलन प्रकार का उपयोग करके आपको बेहतर प्रदर्शन मिलेगा, क्योंकि इस तरह के मामलों में सम्मिलन क्रम बेहतर प्रदर्शन करता है।