तारों की पहले से क्रमबद्ध सरणी सूची में स्ट्रिंग डालने का सबसे प्रभावी तरीका क्या है?

Question

मेरे पास एक ऐरेलिस्ट है जिसमें इसमें 17,000 शब्द हैं। मुझे केवल सूची में एक शब्द जोड़ना होगा यदि यह पहले से नहीं है और मुझे सूची के क्रम क्रम को संरक्षित करने की आवश्यकता है। यानी, मुझे इसे अपने वर्णानुक्रमिक सही स्थान में रखना होगा।

मुझे नहीं पता कि इसे सम्मिलित करने के लिए सही जगह कैसे खोजें। मैं यह पता लगाने के लिए एक बाइनरी खोज का उपयोग कर रहा हूं कि शब्द पहले से ही सूची में है या नहीं और अगर यह वहां है या यदि यह नहीं है तो सूचकांक लौटाता है। मैं ArrayList.add (पूर्णांक सूचकांक, ई तत्व) में यह डाल करने के लिए प्रयोग पर योजना बना रहा था।

Answer 1

binary search मन में आता है, सूची API हालांकि बेहतर

शामिल हो सकता है एक द्विआधारी खोज आप एक के लिए प्राप्त होगा बिंदु जहां आपके पास 2 आइटम शेष हैं, एक ऊपर और एक नीचे, उनमें से एक संभवतः == आपके आइटम पर है। आपके मामले में आपके पास == केस नहीं होगा, इसलिए उच्चतम की अनुक्रमणिका वापस करें और इसकी स्थिति में डालें। मुझे नहीं पता कि जावा में एक ट्यूपल क्लास है या आप कंटेनर बना सकते हैं। किसी भी तरह से, वापसी की तरह कुछ:

(bool, int) binSearch(IList list) 
    returns true, -1 if found 
    returns false, higher of 2 bounds otherwise 

स्पष्ट रूप से इस जावा नहीं है बल्कि यह एक खंड आप द्विआधारी खोज आप अंतिम मान खोजा वापस जाने के लिए इसे संशोधित कर सकता है लिखा था तो

Answer 2

कन्वर्ट करने के लिए नहीं है। यह मान या तो मिलान करने वाली स्ट्रिंग या उस स्थान का स्थान हो सकता है जहां इसे डाला जाना चाहिए।

यह एक द्विआधारी खोज में है, आप तब तक सूची को उप-विभाजित करते हैं जब तक आपको स्ट्रिंग नहीं मिलती या फिर इसे उप-विभाजित नहीं कर सकता। वह स्थिति जहां आप सूची को उप-विभाजित नहीं कर सकते हैं वह स्थिति है जहां आपकी स्ट्रिंग डाली जानी चाहिए।

Answer 3

एक प्रक्रिया को तेज करने के लिए, सामान्य विचार यह है कि अधिक स्मृति का उपयोग करना है, जैसा कि हम सभी जानते हैं। यहां, यह प्रत्येक पत्र के लिए पहले तारों की अनुक्रमणिका हो सकती है। उदाहरण के लिए एक अतिरिक्त ArrayList, छद्म में लिखा:

ArrayList indexes; 
indexes[0] = {"a", 0}; 
indexes[1] = {"b", 123}; 
... 

एक स्ट्रिंग "एक" के साथ शुरू के लिए, आप अनुक्रमित 0-123 के बीच एक द्विआधारी खोज कर सकते हैं।

Answer 4

अंतर्निहित binarySearch विधि का उपयोग करें। यदि कुंजी नहीं मिला है, संख्या दी
-(insertionIndex) - 1

Answer 5

है अगर वहाँ दोहराया शब्द नहीं हैं, जैसा कि आप कहते हैं, आप एक trie लागू करने पर विचार कर सकता है। एक ट्राई पर ऑपरेशन डालें, हैश टेबल की तुलना में कुछ तेज है, क्योंकि कोई टकराव नहीं है। खोज के लिए भी यही सच है।

इसके अलावा, सूची के मध्य में एक तत्व डालने के लिए ArrayList में, इसका मतलब तत्वों का आधा हिस्सा या सरणी आकार में वृद्धि करना है, जो कुछ महंगा हो सकता है।

आप उत्सुक हैं, तो आप निम्नलिखित पृष्ठ में एक कार्यान्वयन देख सकते हैं: https://forums.oracle.com/forums/thread.jspa?messageID=8787521

Answer 6

में कन्वर्ट ArrayList एक TreeSethttp://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html

TreeSet आप के लिए डुप्लिकेट का ख्याल रखना होगा, और शब्द रख वर्णमाला क्रम में।

उदाहरण: (WordList शब्दों का ArrayList है)

TreeSet<String> WordSet = new TreeSet<String>(WordList);