मैं इन सूचियों को तेज़ी से कैसे घटा सकता हूं?

Question

मैं दो ऐरेलिस्टों को घटा देना चाहता हूं, इसलिए मेरे पास वह बच्चा हो सकता है जो अन्य सूची में नहीं है।

मैं इसे इस तरह से कार्य करें:

removeIDs=(ArrayList<Integer>) storedIDs.clone(); 
removeIDs.removeAll(downloadedIDs); 

downloadIDs=(ArrayList<Integer>) downloadedIDs.clone(); 
downloadIDs.removeAll(storedIDs); 

समस्या है कि दोनों सूचियों 5000childs होते हैं और यह मेरे androidphone पर लगभग 4 सेकंड लगते हैं।

क्या ऐसा करने का कोई तेज़ तरीका है? तेजी से सेट का उपयोग कर रहा है? (मुझे नहीं सूचियों में डुप्लिकेट मानों है)

मैं जब तक आप आदेश रखने की जरूरत के बजाय एक Android एप्लिकेशन

Answer 1

उपयोग HashSet ArrayList का विकास।

किसी तत्व को हटाने के लिए सूची कार्यान्वयन के लिए पूर्ण सूची का स्कैन की आवश्यकता होती है, तुलना करके हैशसेट केवल हैश कोड की गणना है और फिर लक्ष्य बाल्टी की पहचान है।

Answer 2

सेट्स को तेज़ी से होना चाहिए। अभी, यह मूल रूप से एक^^ लूप कर रहा है। यह removeIDs में प्रत्येक तत्व पर loops और यह देखने के लिए जांचता है कि वह आईडी डाउनलोड आईडी में है, जिसके लिए पूरी सूची खोजना आवश्यक है। यदि डाउनलोड आईडी को खोज के लिए तेज़ी से कुछ संग्रहीत किया गया था, जैसे हैशसेट, यह बहुत तेज़ होगा और ओ (एन^2) के बजाय ओ (एन) बन जाएगा। कलेक्शन एपीआई में कुछ तेज भी हो सकता है, लेकिन मुझे यह नहीं पता।

यदि आपको ऑर्डर करने की आवश्यकता है, तो आप सामान्य हैशसेट के बजाय एक लिंक्ड हैशसेट का उपयोग कर सकते हैं, लेकिन इसमें कुछ मेमोरी ओवरहेर्ड और तत्वों को डालने/हटाने के लिए कुछ प्रदर्शन हिट होगा।

Answer 3

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

Answer 4

यदि कोई सूची आवश्यक है, तो आप LinkedList चुन सकते हैं। आपके मामले में, @Chris के रूप में, ArrayList कार्यान्वयन प्रत्येक हटाने में सभी तत्वों को स्थानांतरित करेगा।

लिंक्डलिस्ट के साथ आपको यादृच्छिक जोड़ने/निकालने के लिए एक बेहतर प्रदर्शन मिलेगा। यह post देखें।

Answer 5

सबसे पहले मैं लंबे उत्तर के लिए माफ़ी दे रहा हूं। यदि मैं किसी भी समय गलत हूं तो आपको हमेशा सही करने के लिए आपका स्वागत है। यहाँ मैं समाधान के हल के लिए कुछ विकल्प की तुलना कर रहा हूँ

विकल्प 1 < ArrayList>:

अपने कोड आप इस्तेमाल में ArrayList.removeAll विधि removeAll

के स्रोत कोड के कोड के लिए देख सकते हैं removeAll

public boolean removeAll(Collection<?> c) { 
     return batchRemove(c, false); 
    } 

इतना पता है कि batchRemove विधि में है की जरूरत है। यहां यह link है। यहां महत्वपूर्ण हिस्सा आप

for (; r < size; r++) 
     if (c.contains(elementData[r]) == complement) 
       elementData[w++] = elementData[r]; 

देख सकते हैं अब contains विधि है जो सिर्फ indexOf विधि का एक आवरण है इस पर गौर कर सकते हैं। link। इंडेक्सऑफ विधि में ओ (एन) ऑपरेशन होता है।(ध्यान देने योग्य बात सिर्फ एक हिस्सा यहाँ)

for (int i = 0; i < size; i++) 
      if (elementData[i]==null) 
        return i; 

सब कुछ खत्म हो

तो यह एक

O (n^2)

removeAll

विकल्प में परिचालन है 2 < हैशसेट>: पहले मैंने यहां कुछ लिखा था लेकिन ऐसा लगता है कि मैं कुछ पॉइंट में गलत था टी इसे हटाने के लिए। हैशसेट के बारे में विशेषज्ञ से बेहतर सुझाव लें। मुझे आपके मामले में यकीन नहीं है कि हैशप एक बेहतर समाधान होगा या नहीं। तो मैं एक और समाधान का प्रस्ताव कर रहा हूँ

विकल्प 3 < मेरे सुझाव आप कोशिश कर सकते हैं>:

चरण 1: यदि आपका डेटा तो और ने इस कदम की कोई जरूरत नहीं सूची है जो आप घटा देंगे सॉर्ट क्रमबद्ध हो जाता है (दूसरी सूची)

चरण 2: अवर्गीकृत सूची के प्रत्येक तत्व के लिए दूसरी सूची

चरण 3 में एक द्विआधारी खोज चलाने : अगर कोई मुकाबला नहीं फिर एक और परिणाम सूची में स्टोर कर पाया लेकिन अगर मैच पाया तो न जोड़ने

चरण 4: परिणाम सूची अपने अंतिम जवाब है

विकल्प 3 की लागत:

चरण 1: अगर हल नहीं O(nlogn) समय

चरण 2:O(nlogn) समय

चरण 3:O(n) अंतरिक्ष

**

इसलिए समग्र ओ (nlogn) समय और हे (एन) अंतरिक्ष

**