जावा में .indexOf विधि के लिए एल्गोरिदम का विकल्प

Question

मैं सिर्फ जावा String वर्ग की .indexOf() विधि के कार्यान्वयन को देख रहा था और ऐसा लगता है कि कोड के लेखक किसी दिए गए स्ट्रिंग में सबस्ट्रिंग को खोजने के लिए ब्रूट फोर्स एल्गोरिदम का उपयोग करते हैं। यही है, दृष्टिकोण ओ (एमएन) में चलता है, जहां एम और एन क्रमशः स्रोत और लक्ष्य तारों की लंबाई हैं।

लेखक राबिन-कार्प जैसे अधिक कुशल एल्गोरिदम का उपयोग क्यों नहीं करते हैं, जिसमें एक अच्छा हैश फ़ंक्शन प्रदान किए जाने पर ओ (एम + एन) की रनटाइम जटिलता है?

मैं इस कार्यान्वयन के कारण के पीछे पूर्ण ज्ञान पर अनुपलब्ध हो सकता हूं और इसलिए समझना चाहता था।

Answer 1

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

यह कहा गया है कि जावा स्पेक में कहीं भी यह एल्गोरिदम का उपयोग अनिवार्य नहीं है। वे डिफ़ॉल्ट रूप से राबिन-कार्प को डिफ़ॉल्ट एल्गोरिदम के रूप में चुन सकते थे।

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

Answer 2

मुझे लगता है कि आप इंडेक्स का मतलब है या सबस्ट्रिंग के बजाय शामिल हैं। सबस्ट्रिंग ओ (1)

अक्सर सरल कोड तेज़ी से चलता है। कोड जो उदाहरण के लिए वस्तुओं को बनाता है अक्सर धीमा चलता है।

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

Answer 3

मुझे लगता है कि उन्होंने नहीं सोचा था कि लोग इसे बहुत बड़े तारों के लिए उपयोग करेंगे। 100 से कम स्ट्रिंग लंबाई के साथ यह बहुत अलग नहीं होगा।

Answer 4

बस एक अनुमान है, लेकिन याद रखें कि जावा स्ट्रिंग को i18n कारणों के लिए UTF-16 के रूप में संग्रहीत किया जाता है, सादा 8-बिट ASCII नहीं। यह हो सकता है कि यूटीएफ -16 (और अधिक कठिन यूटीएफ -8) पर कुछ algorthims का समर्थन समस्याग्रस्त हो सकता है। बस एक अनुमान है, यद्यपि।