जावा डेटा संरचना जिसमें कुशल जोड़, हटाएं और यादृच्छिक

Question

मुझे जावा डेटा संरचना की आवश्यकता है जिसे मैं कुशलता से जोड़, हटा और एक्सेस कर सकता हूं।

यह काम नहीं करता क्या है:

ArrayList कुशल ऐड (निरंतर समय), और रैंडम एक्सेस (बस एक यादृच्छिक पूर्णांक के साथ "प्राप्त") है, लेकिन क्योंकि यह संभावित रूप से करने के लिए किया हटाए गए रैखिक समय लग सकता है इसके लिए पूरी सूची खोजें।

ट्रीसेट या हैशसेट में कुशल जोड़ना और हटाना है, लेकिन मैं यह नहीं समझ सकता कि यादृच्छिक वस्तु कैसे प्राप्त करें।

कोई विचार?

सिद्धांत रूप में, एक बी ट्री काम करेगा, अगर मैं खुद को यादृच्छिक लेफ्ट्स या अधिकारों के साथ पेड़ को पार कर सकता हूं, लेकिन मुझे नहीं लगता कि मानक जावा क्लास मुझे यह क्षमता देता है।

यदि मैं मानक जावा कक्षाओं में कुछ भी काम नहीं करता हूं तो मैं किसी तृतीय पक्ष लाइब्रेरी का उपयोग करने के लिए तैयार हूं।

मुझे डुप्लीकेट या नल का समर्थन करने की आवश्यकता नहीं है, न ही इसे थ्रेड सुरक्षित होने की आवश्यकता है।

धन्यवाद।

Answer 1

यदि आप सूची हटाने अनॉर्डर्ड सूची हटाते हैं तो आप इसे एक ऐरेलिस्ट/हैश मैप जोड़ी (जहां नक्शा सूची में वस्तुओं की अनुक्रमणिका संग्रहीत करेगा) के साथ प्राप्त कर सकते हैं। हटाने पर, सूची में सभी बाद के तत्वों को एक स्थिति में स्थानांतरित करने के बजाय, आप हटाए गए आइटम की जगह भरने के लिए अंतिम तत्व को ले जाएं। फिर हटाने के दौरान छूने की आवश्यकता वाले दो अलग-अलग तत्व हैं। एक त्वरित उदाहरण (जो मैं परीक्षण नहीं किया है और मैं घपला नहीं किया उम्मीद):

class SpecialSet<E> extends AbstractSet<E> implements Set<E> { 
    private final List<E> list = new ArrayList<>(); 
    private final Map<E,Integer> indexMap = new HashMap<>(); 

    @Override 
    public boolean add(E e) { 
     if (contains(e)) return false; 
     indexMap.put(e, list.size()); 
     list.add(e); 
     return true; 
    } 

    @Override 
    public boolean remove(Object o) { 
     Integer indexBoxed = indexMap.remove(o); 
     if (indexBoxed == null) return false; 
     int index = indexBoxed; 
     int last = list.size() - 1; 
     E element = list.remove(last); 
     if (index != last) { 
      indexMap.put(element, index); 
      list.set(index, element); 
     } 
     return true; 
    } 

    public E removeRandom() { 
     E element = list.get((int)(Math.random() * size())); 
     remove(element); 
     return element; 
    } 

    @Override 
    public boolean contains(Object o) { 
     return indexMap.containsKey(o); 
    } 

    @Override 
    public Iterator<E> iterator() { 
     return list.iterator(); 
    } 

    @Override 
    public int size() { 
     return list.size(); 
    } 
} 

क्या वस्तु समानता परीक्षण व्यवहार आप चाहते हैं पर निर्भर करता है, तो आप शायद बाहर HashMap एक IdentityHashMap के लिए एक छोटे से बेहतर करने के लिए स्वैप कर सकता है गति।

Answer 2

मैं प्रस्ताव करता हूं कि आप एक इंटेजर कुंजी के साथ एक मानचित्र का उपयोग करें। इस तरह आप निकालने के लिए एक यादृच्छिक संख्या उत्पन्न कर सकते हैं।

पाठक के लिए समस्या शेष: बाद में हटाए जाने (या किसी भी ऑपरेशन) पर अंतराल होंगे।

Answer 3

ध्यान दें कि यदि आप आवश्यक अधिकतम आकार को पूर्व-आवंटित करते हैं तो एक साधारण सरणी नौकरी करेगी। "शीर्ष" सूचकांक मान रखें और "शीर्ष" को बढ़ाकर और उस सरणी तत्व में संग्रहीत करके डालें। जब आप हटाते हैं, हटाए गए तत्व में "शीर्ष" मान को नीचे कॉपी करें और "शीर्ष" घटाएं।

यदि आप अपने अधिकतम आकार को नहीं जानते हैं तो भी आप सरणी की सरणी आवंटित कर सकते हैं और उसी मूल एल्गोरिदम का उपयोग कर सकते हैं, केवल तत्व को एक्सेस करने से पहले आपको पहले प्रमुख और मामूली सरणी अनुक्रमणिका मानों की गणना करने की आवश्यकता है।