ऑब्जेक्ट्स की अक्सर पूछे जाने वाली सूची के लिए सर्वश्रेष्ठ डेटास्ट्रक्चर

Question

मेरे पास ऑब्जेक्ट्स की एक सूची है, सूची। एंटीटी क्लास में एक इकाई ऑब्जेक्ट को दूसरे से अलग करने के लिए कुछ विशेषताओं (व्यवसाय नियम) पर एक समान विधि है।

List<Entity> noDuplicates = new ArrayList<Entity>(); 
for(Entity entity: lstEntities) 
{ 
    int indexOf = noDuplicates.indexOf(entity); 
    if(indexOf >= 0) 
    { 
      noDuplicates.get(indexOf).merge(entity); 
    } 
    else 
    { 
      noDuplicates.add(entity); 
    } 
} 

अब, समस्या यह है कि मैं देख रहा किया गया है कि कोड के इस हिस्से, धीमी हो रही है है:

काम है कि हम आम तौर पर इस सूची में बाहर ले जाने के इस तरह सभी डुप्लिकेट कुछ निकालना है जैसे ही सूची में 10000 से अधिक वस्तुएं हैं, उतनी ही कम है। मुझे लगता है कि सरणीसूची एओ (एन) खोज कर रही है।

क्या कोई तेज़ विकल्प है, हैश मैप का उपयोग करना एक विकल्प नहीं है, क्योंकि इकाई की विशिष्टता अपने 4 गुणों पर एक साथ बनाई गई है, यह कुंजी को स्वयं मानचित्र में डालने के लिए कठिन होगा? तेजी से पूछताछ में सेट मदद सॉर्ट करेगा?

धन्यवाद

Answer 1

अब, जो समस्या मैं देख रहा हूं वह यह है कि कोड का यह हिस्सा 10000 से अधिक वस्तुओं के साथ ही धीमा हो रहा है। मुझे लगता है कि सरणीसूची ओ (एन) खोज कर रही है।

एल्गोरिथ्म आप पोस्ट वास्तव में हे से भी बदतर है (एन) के माध्यम से

• पुनरावृत्ति इनपुट सूची lstEntities - हे (एन)
• इस लूप के भीतर, आप ArrayList.indexOf(T) है जो बुला रहे हैं स्कैन करने के लिए सूची - हे (एन) फिर

आप एल्गोरिथ्म वास्तव में हे (एन^2) के बाद से आप संभवतः एक पाश के भीतर दो बार सूची स्कैनिंग कर रहे हैं।

यह आप की तरह लगता है कि आप क्या करना चाहते हैं वास्तव में दो आपरेशन है:

1. इनपुट List से, जब आप डुप्लीकेट ढूंढना डुप्लीकेट
2. निकालने के लिए, "मर्ज" संस्थाओं।

आप नेस्टेड लूप की बजाय सूची को स्कैन करके ऐसा कर सकते हैं। मैं उन क्षेत्रों को स्थानांतरित करने के लिए अपने Entity को तोड़ने की अनुशंसा करता हूं जो ID जैसे किसी अन्य प्रकार में एक इकाई को पहचानते हैं, या कम से कम getID() विधि जोड़ें जो इन फ़ील्ड को एक ही प्रकार में समूहित कर सकता है। इस तरह आप इकाइयों को "डुप्लिकेट" पहचान के साथ मर्ज करने में सक्षम होने के लिए आसानी से दो प्रकार के बीच एक नक्शा बना सकते हैं। यह कुछ इस तरह दिख सकता है:

Map<ID, Entity> map = new HashMap<ID, Entity>(inputList.size()); 
for (Entity e : inputList) { 
    Entity existing = map.get(e.getID()); 
    if (existing == null) { 
     //not in map, add it 
     map.put(e.getID(), e); 
    } 
    else { 
     existing.merge(e); 
    } 
} 

सूची के माध्यम से बार-बार दोहराना हे (एन) है, जबकि HashMap.get(K) एक निरंतर समय ऑपरेशन है।

Answer 2

एक विचार एक List के बजाय एक Set उपयोग करने के लिए है, वहाँ एक Set में कोई डुप्लिकेट हैं। एक सूची से डुप्लीकेट निकालने के लिए, तो आप सिर्फ एक नया Set

List<Entity> list = //your list. 
Set<Entity> set = new HashSet<Entitiy>(); 
set.addAll(list); 

को List जोड़ सकता है लेकिन तब फिर से, शायद वहाँ पहली जगह में एक List को उपयोग करने के कारण क्या है? यदि नहीं, तो आप इसके बजाय Set का उपयोग कर सकते हैं, और किसी भी डुप्लीकेट के बारे में चिंता करने की आवश्यकता नहीं है।

संपादित

एक Set में तत्वों का कोई सूचकांक संदर्भ नहीं है (एक List है, जहां आप get(int index) कर सकते हैं की तुलना में)। Set में तत्व संदर्भ के विशिष्ट बिंदु के बिना चारों ओर तैर रहे हैं।

यदि आपको एक विशिष्ट खोजना है, तो आपको उन सभी के माध्यम से फिर से प्रयास करने की आवश्यकता है। यदि यह ठीक नहीं है और/या आप अनुक्रमित संदर्भ के बिना नहीं हो सकते हैं - जो get(int index) और remove(int index) के लिए अनुमति देता है - मुझे लगता है कि Set आपके लिए कोई विकल्प नहीं है।

Answer 3

सूची संरचना के बजाय, आप एक सेट का उपयोग कर सकते हैं (अगर आप इकाई विशिष्टता के बारे में चिंतित हैं तो अधिक उपयुक्त), जैसा कि लार्स ने सुझाव दिया है। इसके अतिरिक्त, यदि प्रदर्शन एक समस्या है, तो मैं TreeSet का उपयोग करने और Comparator को उनके गुणों के आधार पर इकाई उदाहरणों की तुलना करने के लिए लागू करना चाहता हूं। वृक्ष संरचना तेजी से (लॉगरिदमिक जटिलता) डालने, हटाने और पुनर्प्राप्ति संचालन की अनुमति देगी।

Answer 4

यह सब इस बात पर निर्भर करता है कि merge ऑपरेशन क्या कर रहा है। mergeequals करते समय तुलना की गई किसी भी विशेषता को बदलता है? यदि नहीं, तो आप यदि आप ऐसा करते हैं कि कितना यह तेजी से हो जाएगा देखकर हैरान रह जाएंगे:

पहले, अपने Entity वर्ग कि equals की अपनी परिभाषा के साथ संगत है के लिए एक hashCode परिभाषित करते हैं।एक आम तरीका यह है है:

public int hashCode() { 
    // assuming the four attributes that determine equality are called 
    // attrFoo, attrBar, attrBaz, and attrQux 
    int hash = 1; 
    hash += attrFoo == null ? 0 : attrFoo.hashCode(); 
    hash *= 37; 
    hash += attrBar == null ? 0 : attrBar.hashCode(); 
    hash *= 37; 
    hash += attrBaz == null ? 0 : attrBaz.hashCode(); 
    hash *= 37; 
    hash += attrQux == null ? 0 : attrQux.hashCode(); 

    return hash; 
} 

फिर, एक HashMap उपयोग करती हैं इसलिए आप इन बातों को पा सकते हैं कि:

Map<Entity, Entity> map = new HashMap<Entity, Entity>(); 
for(Entity entity: lstEntities) { 
    if (map.containsKey(entity)) { 
    map.get(entity).merge(entity); 
    } else { 
    map.put(entity, entity); 
    } 
} 
return map.values(); // or keys(). Whichever. 

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

Answer 5

जब तक आपके पास किसी सूची के क्रम की आवश्यकता के लिए कोई कारण न हो, तो संभवतः आप एक सेट - विशेष रूप से, हैशसेट के साथ सबसे अच्छा हो।

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

Answer 6

दो सरल कदम (N * लॉग (एन)) कलन विधि:

1. क्रमबद्ध
2. पुनरावृत्ति करने के लिए प्रत्येक आइटम की तुलना सूची में चार महत्वपूर्ण क्षेत्रों के आधार पर एक तुलनित्र का उपयोग कर सूची सूची में अगला, यदि वे बराबर हैं, तो उन्हें मर्ज करें और एक को हटा दें।