मैं एक बच्चे को उसके माता-पिता को सौंपकर और फिर उसे it.remove() के माध्यम से हटाकर कुशलतापूर्वक पेड़ बनाने की कोशिश कर रहा हूं:

for (OgOrganizationTreeDTO parent : parents) {
    setChildren(parent, organizationTree);
}

यहाँ setChildren फ़ंक्शन का कार्यान्वयन है

private void setChildren(OgOrganizationTreeDTO root, List<OgOrganizationTreeDTO> allOrganizations) {
    if (allOrganizations.isEmpty()) {
        return ;
    }
    Iterator<OgOrganizationTreeDTO> it = allOrganizations.iterator();
    while (it.hasNext()) {
        OgOrganizationTreeDTO potentialChild = it.next();
        if (potentialChild.getIdParentId() != null && potentialChild.getIdParentId().equals(root.getId())) {
            root.addChild(potentialChild);
            it.remove();
            setChildren(potentialChild, allOrganizations);
        }
    }
}

मैं एक लिंक्डलिस्ट का उपयोग कर रहा हूं और मुझे एक ConcurrentModificationException मिलता है। मैंने allOrganizations की प्रतिलिपि को पुनरावर्ती setChildren फ़ंक्शन जैसे new LinkedList<>(allOrganizations) में पास करके समस्या का समाधान किया है, लेकिन प्रतिलिपि भाग में O(n) समय लगता है और मैं नहीं चाहता वह।

मैंने LinkedBlockingQueue का उपयोग करने का भी प्रयास किया है, लेकिन मुझे पता चला है कि हटाने में O(n) समय लगता है।

मैं LinkedList O(1) हटाने का लाभ लेना चाहता हूं, इसलिए हर बार जब मैं एक बच्चा जोड़ता हूं, और उस पर फिर से लिखता हूं तो सूची छोटी हो जाती है।

मैंने अलग-अलग नोड्स को देखा के रूप में चिह्नित करके, और बेस केस को hashSet.size() == allOrganizations.size() पर सेट करके HashSet के साथ एक समाधान को सफलतापूर्वक कार्यान्वित किया है, लेकिन मैं अभी भी उसी आकार की सूची पर आवर्ती रहता हूं, इसलिए यह मदद नहीं करता है मैं अन्य।

क्या LinkedList O(1) निष्कासन का उपयोग करने के मेरे लक्ष्य को पूरा करने का कोई तरीका है, या इसके लिए और भी अधिक कुशल वैकल्पिक दृष्टिकोण है?

1
Gigaxel 14 फरवरी 2019, 13:32

1 उत्तर

सबसे बढ़िया उत्तर

खैर, मुझे नहीं पता कि इसे रिकर्सन के साथ कैसे करना है क्योंकि आप वास्तव में प्रत्येक रिकर्सिव कॉल में एक नया इटरेटर बनाते हैं (allOrganizations.iterator() - नया इटरेटर इंस्टेंस बनाता है)। तो जब आप कॉल डिलीट करते हैं तो आप अन्य इटरेटर्स के लिए संग्रह को संशोधित करते हैं और यही कारण है कि यह अपवाद फेंकता है।

  • एक समाधान कुछ CopyOnWriteList का उपयोग करना होगा जो समवर्ती संशोधन की अनुमति देता है लेकिन यह सिर्फ सूची की एक प्रति पास कर रहा है, उसी को संशोधित नहीं कर रहा है, इसलिए यह अतिरिक्त मेमोरी लेगा।

  • एक अन्य उपाय यह होगा कि कुछ संपत्ति को OgOrganizationTreeDTO वर्ग में जोड़ा जाए जो यह चिन्हित करता है कि क्या वह पंक्ति पहले ही संसाधित हो चुकी है। इस मामले में आइटम को सूची से हटाने के बजाय आप इसे संसाधित के रूप में चिह्नित करेंगे।

  • लेकिन वैसे भी जब से आप प्रदर्शन और बड़े ओ के बारे में पूछ रहे हैं तो मैं आपको एक और समाधान प्रदान कर सकता हूं जिसमें ओ (एन) जटिलता है। बेशक अधिक मेमोरी के साथ कुछ ट्रेडऑफ़ है लेकिन यह मानक मेमोरी बनाम जटिलता समस्या है ...

    private static void setChildrenMap(OgOrganizationTreeDTO root, 
         List<OgOrganizationTreeDTO> allOrganizations) {
    
      Map<Integer, OgOrganizationTreeDTO> organizationsMap = new HashMap<>();
      organizationsMap.put(root.getId(), root);
    
      for (OgOrganizationTreeDTO element : allOrganizations) {
        organizationsMap.put(element.getId(), element);
      }
    
      for (OgOrganizationTreeDTO element : allOrganizations) {
         organizationsMap.get(element.getParentId()).addChild(element);
      }
    
    }
    

मूल रूप से हैशपैप से एक तत्व लेना एक स्थिर समय है इसलिए हम इसका उपयोग आवश्यक माता-पिता को खोजने के लिए कर रहे हैं। यदि आप खराब डेटा वाले तत्वों की अपेक्षा करते हैं तो आपको कुछ चेक जोड़ने की आवश्यकता हो सकती है क्योंकि organizationsMap.get(element.getParentId()) शून्य वापस आ सकता है

1
Veselin Davidov 14 फरवरी 2019, 10:57