इंडेक्स

Question

द्वारा ओ (1) यादृच्छिक अभिगम के साथ क्रमबद्ध सेट कैसे बनाएं, तारों के संग्रह की आवश्यकता है जहां सॉर्ट किए जाने वाले तत्वों को सॉर्ट करने के लिए आवश्यक है और गैर-डुप्लिकेट भी इंडेक्स के माध्यम से पुनर्प्राप्त किया जा सकता है।

• मैं TreeSet जो डुप्लिकेट दूर करता है और आदेश में सब कुछ सॉर्ट करता लेकिन सूचकांक के माध्यम से प्राप्त नहीं कर सकता का उपयोग कर सकते हैं। इंडेक्स के माध्यम से पुनर्प्राप्त करने के लिए, मैं ArrayList और addAll तत्व बना सकता हूं, लेकिन यह addAll बहुत समय लगता है।

या

• मैं एक ArrayList, आवश्यक डालने का उपयोग कर सकते हैं और फिर, किसी अन्य विधि द्वारा डुप्लिकेट निकालने तो Collections.sort पद्धति का उपयोग करके तत्वों सॉर्ट करने के लिए।

लेकिन यह बात ये है कि इन सभी समय लेने के लिए, यह संग्रह प्राप्त करने के लिए कोई सीधा तरीका है, संग्रहित, गैर-डुप्लिकेट, ओ (1) इंडेक्स द्वारा यादृच्छिक पहुंच के साथ।

Answer 1

SetUniqueList नामक कॉमन्स संग्रह में डेटा प्रकार है जो मुझे विश्वास है कि आपकी पूरी ज़रूरतें पूरी होती हैं। इसे देखें:

https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/list/SetUniqueList.html

Answer 2

मुझे यकीन नहीं है, क्या आप मानचित्र का परीक्षण करते हैं? मेरा मतलब है कि आपकी स्ट्रिंग को ट्रीमैप में कुंजी के रूप में उपयोग करें।

मानचित्र में, यह अपनी स्थिति (एक हैश मान) खोजने के लिए एक कुंजी के लिए ओ (1) है। और TreeMap की keySet TreeMap में चाबियों का एक क्रमबद्ध सेट वापस कर देगा।

क्या यह आपकी आवश्यकता के अनुरूप है?

Answer 3

आप दूसरे विचार का उपयोग कर सकते हैं:

मैं ArrayList, आवश्यक डालने का उपयोग कर सकते हैं और फिर, कुछ अन्य विधि द्वारा डुप्लिकेट निकालने तो Collections.sort पद्धति का उपयोग करके तत्वों सॉर्ट करने के लिए।

लेकिन तरह से पहले डुप्लिकेट हटाने के बजाय, आप सॉर्ट सकता ArrayList पहले, तो उन सभी डुप्लीकेट लगातार पदों पर हैं और बाद में एक भी पास में हटाया जा सकता है।

इस बिंदु पर, आपके दोनों तरीकों में एक ही समग्र जटिलता है: ओ (एन * लॉगएन) और यह ध्यान देने योग्य है कि आप किसी भी तरह से क्रमबद्ध अनुक्रम प्राप्त नहीं कर सकते हैं (मूल्यों के बारे में कुछ ज्ञान के अतिरिक्त शोषण के बिना)।

Answer 4

आप List शुरुआत में और आपरेशन के अंत करने के लिए बाध्य कर रहे हैं, यह एक Set में तब्दील "कॉपी" निर्माता (या addAll) के बाद तत्वों भर जाती है, इस डुप्लिकेट को हटा के साथ। यदि आप इसे उचित Comparator के साथ TreeSet में परिवर्तित करते हैं तो यह इसे भी सॉर्ट करेगा। इससे भी, आप इसे वापस List में परिवर्तित कर सकते हैं।

Answer 5

प्रदर्शन इस बात पर निर्भर करता है कि तत्व कितनी बार जोड़े जाते हैं और उन्हें कितनी बार इंडेक्स द्वारा एक्सेस किया जाएगा।

मैं ट्रीसेट का उपयोग कर सकता हूं जो डुप्लिकेट को हटा देता है और क्रम में सबकुछ टाइप करता है लेकिन इंडेक्स के माध्यम से पुनर्प्राप्त नहीं कर सकता है। इंडेक्स के माध्यम से पुनर्प्राप्त करने के लिए, मैं सरणी सूची बना सकता हूं और इसमें तत्व जोड़ सकता हूं, लेकिन यह addAll बहुत समय लगता है।

List.addAll (yourSortedSet) कम से कम हे (एन) समय और स्थान हर बार जब आप (तत्व के सूचकांक से अर्थात्) सूची के रूप में SortedSet उपयोग करना चाहते का समय लगेगा।

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

सॉर्टिंग निश्चित रूप से आपकी सूची के क्रमबद्ध दृश्य को हर बार ओ (एन) से अधिक ले जाएगा।

एक और समाधान

आप सूचकांक द्वारा फ़ेच नहीं कर रहे हैं बहुत बार तो यह यह करने के लिए इस प्रकार और अधिक कुशल है:

बस एक SortedSet में String रों की दुकान का विस्तार TreeSet हो सकता है और अपनी खुद की get(int i) विधि प्रदान/कार्यान्वित करें जहां आप ith तत्व तक पुन: सक्रिय करते हैं और उस तत्व को वापस करते हैं। सबसे बुरे मामले में, यह ओ (एन) अन्यथा बहुत कम होगा। इस तरह आप कोई तुलना या रूपांतरण या स्ट्रिंग की प्रतिलिपि कर रहे हैं। कोई अतिरिक्त जगह की आवश्यकता नहीं है।

Answer 6

एक हैशमैप का उपयोग करें, आपको अद्वितीय मूल्यों के साथ समस्या हल हो जाएगी और इसे सॉर्टिंग विधियों द्वारा क्रमबद्ध किया जाएगा। यदि यह संभव है Quicksort का उपयोग करें।

Answer 7

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

Answer 8

यहाँ वास्तविक समस्या है कि ओपी हमें वास्तविक समस्या नहीं बताया गया है। तो बहुत से लोग डेटा संरचनाओं पर अनुमान लगाते हैं और वास्तव में सोचने के बिना उत्तर पोस्ट करते हैं।

असली लक्षण, ओपी एक टिप्पणी में कहा गया है, कि यह प्रतिलिपि करने के लिए है कि TreeSet एक ArrayList में 700 मि.से लेता है एक TreeSet में तार डाल करने के लिए, और एक और 700 एमएस है। जाहिर है, कार्यक्रम ऐसा नहीं कर रहा है जो ओपी सोचता है, क्योंकि कॉपी को कुछ माइक्रोसेकंडों पर लेना चाहिए। असल में, मेरे प्राचीन थिंकपैड पर चल रहे कार्यक्रम में, केवल 360 मिमी 100,000 यादृच्छिक तार बनाने के लिए लेते हैं, उन्हें ट्रीसेट में डालते हैं, और उस ट्रीसेट को एक ऐरेलिस्ट में कॉपी करते हैं।

उस ने कहा, ओपी ने एक उत्तर (दो बार) चुना है। शायद अगर/ओपी असली समस्या के बारे में सोचने का फैसला करता है, तो SSCCE का यह उदाहरण उपयोगी होगा। यह सीडब्ल्यू है, इसलिए इसे संपादित करने में संकोच न करें।

---

import java.lang.management.ManagementFactory; 
import java.lang.management.ThreadMXBean; 
import java.util.ArrayList; 
import java.util.List; 
import java.util.Random; 
import java.util.TreeSet; 


public class Microbench 
{ 
    public static void main(String[] argv) 
    throws Exception 
    {   
     ThreadMXBean threadBean = ManagementFactory.getThreadMXBean(); 
     long start = threadBean.getCurrentThreadCpuTime(); 
     executeTest(); 
     long finish = threadBean.getCurrentThreadCpuTime(); 
     double elapsed = (finish - start)/1000000.0; 
     System.out.println(String.format("elapsed time = %7.3f ms", elapsed)); 
    } 


    private static List<String> executeTest() 
    { 
     String[] data = generateRandomStrings(100000); 

     TreeSet<String> set = new TreeSet<String>(); 
     for (String s : data) 
      set.add(s); 

     return new ArrayList<String>(set); 
    } 


    private static String[] generateRandomStrings(int size) 
    { 
     Random rnd = new Random(); 
     String[] result = new String[size]; 
     for (int ii = 0 ; ii < size ; ii++) 
      result[ii] = String.valueOf(rnd.nextLong()); 
     return result; 
    } 
} 

Answer 9

वहाँ कि उपयोग LinkedMap जहां नक्शे में प्रत्येक तत्व अद्वितीय है या सूची और ओवरराइड विधि का अपना स्वयं का विस्तार कर जोड़ने

import java.util.ArrayList; 

public class MyList<V> extends ArrayList<V>{ 

    private static final long serialVersionUID = 5847609794342633994L; 

    public boolean add(V object) { 
     //make each object unique 
     if(contains(object)){ 
      return false; 
     } 

     //you can make here ordering and after save it at position 

     //your ordering here 

     //using extended method add 
     super.add(yourposition,object); 
    } 
} 

Answer 10

मैं भी की समस्या का सामना करना पड़ा करने के दो तरीके है एक TreeMap में एक निश्चित स्थिति पर तत्व खोजना। मैंने पेड़ को वजन के साथ बढ़ाया जो इंडेक्स द्वारा तत्वों तक पहुंचने और इंडेक्स पर तत्व ढूंढने की अनुमति देता है। परियोजना को अनुक्रमित-पेड़-मानचित्र http://code.google.com/p/indexed-tree-map/ कहा जाता है। सॉर्ट किए गए मानचित्र में किसी इंडेक्स पर किसी तत्व या तत्व की अनुक्रमणिका ढूंढने के लिए कार्यान्वयन रैखिक पुनरावृत्ति पर आधारित नहीं है बल्कि पेड़ बाइनरी खोज पर आधारित है। पेड़ के वजन को अद्यतन करना ऊर्ध्वाधर पेड़ चढ़ाई पर भी आधारित है। तो कोई रैखिक पुनरावृत्तियों।