जावा

Question

में सबसे तेज़ सबस्ट्रिंग खोज विधि क्या है I जावा का उपयोग कर स्ट्रिंग (हैस्टैक) की सूची में सबस्ट्रिंग (सुइयों) को खोजने के लिए एक तरीका लागू करने की आवश्यकता है।

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

जावा में, जैसा कि मुझे पता है, स्ट्रिंग में खोज सबस्ट्रिंग देखने के लिए 3 बिल्ड-इन विधि हैं।

1. string.contains()

2. string.indexOf()

3. नियमित अभिव्यक्ति। क्या ऊपर प्रत्येक विधि के runtimes हैं: यह string.matches की तरह कुछ ("जा"))

मेरा प्रश्न है? यह जांचने के लिए सबसे तेज़ या सबसे कुशल या सबसे लोकप्रिय तरीका है कि स्ट्रिंग की सूची में एक दिया गया सबस्ट्रिंग है या नहीं।

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

Answer 1

String[] names = new String[]{"jack", "jackson", "jason", "dijafu"}; 
    long start = 0; 
    long stop = 0; 

    //Contains 
    start = System.nanoTime(); 
    for (int i = 0; i < names.length; i++){ 
     names[i].contains("ja"); 
    } 
    stop = System.nanoTime(); 
    System.out.println("Contains: " + (stop-start)); 

    //IndexOf 
    start = System.nanoTime(); 
    for (int i = 0; i < names.length; i++){ 
     names[i].indexOf("ja"); 
    } 
    stop = System.nanoTime(); 
    System.out.println("IndexOf: " + (stop-start)); 

    //Matches 
    start = System.nanoTime(); 
    for (int i = 0; i < names.length; i++){ 
     names[i].matches("ja"); 
    } 
    stop = System.nanoTime(); 
    System.out.println("Matches: " + (stop-start)); 

आउटपुट:

Contains: 16677 
IndexOf: 4491 
Matches: 864018 

Answer 2

जहां तक ​​आपने तीनों के बारे में पूछा था, एक नियमित अभिव्यक्ति बहुत धीमी हो जाएगी क्योंकि जब आपके पास बहुत आसान लक्ष्य होता है तो उसे एक पूर्ण राज्य मशीन को एक साथ रखने की आवश्यकता होती है। contains बनाम indexOf ... के लिए

2114 public boolean contains(CharSequence s) { 
2115  return indexOf(s.toString()) > -1; 
2116 } 

(यानी, contains सिर्फ indexOf कहता है, लेकिन आप प्रत्येक मंगलाचरण पर एक अतिरिक्त String निर्माण लग सकते हैं। यह contains का सिर्फ एक कार्यान्वयन है, लेकिन जब से contains का अनुबंध एक है indexOf का सरलीकरण, शायद यह है कि प्रत्येक कार्यान्वयन कैसे काम करेगा।)

Answer 3

यह विशिष्ट जेआरई (और यहां तक ​​कि जेडीके) बनाने/संस्करण पर निर्भर है। यह भी निर्भर करता है/कारकों पर निर्भर करता है जैसे स्ट्रिंग लम्बाई, निहित होने की संभावना, किस स्थिति में इत्यादि। सटीक प्रदर्शन डेटा प्राप्त करने का एकमात्र तरीका आपके सटीक संदर्भ को स्थापित करने की आवश्यकता है।

हालांकि, सामान्य रूप से aString.contains() और aString.indexOf() बिल्कुल वही होना चाहिए। और यहां तक ​​कि यदि एक नियमित अभिव्यक्ति को शानदार रूप से अनुकूलित किया गया था, तो यह पहले दो के प्रदर्शन से अधिक नहीं होगा।

नहीं, जावा अत्यधिक विशिष्ट एल्गोरिदम का उपयोग नहीं करता है।

Answer 4

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

Answer 5

आप स्ट्रिंग्स की एक बड़ी राशि खोज रहे हैं अगर मैं पढ़ा है Aho-Corasick एल्गोरिथ्म बहुत तेजी से है, लेकिन यह एक देशी रूप जावा में लागू है। यह यूनिक्स-आधारित सिस्टम में जीआरईपी द्वारा उपयोग किया जाने वाला वही एल्गोरिदम है जो मदद करता है और यह बहुत ही कुशल है। Here बर्कले का एक जावा कार्यान्वयन सौजन्य है।

यह भी देखें: https://stackoverflow.com/a/1765616/59087

Answer 6

स्वीकार किए जाते हैं जवाब सही और पूरा नहीं हुआ नहीं है।

• indexOf() विसंगतियों पर बैकट्रैकिंग का उपयोग करके एक बेवकूफ स्ट्रिंग खोज करता है। यह छोटे पैटर्न/ग्रंथों पर काफी तेज है लेकिन बड़े ग्रंथों पर बहुत खराब प्रदर्शन से पता चलता
• contains("ja") indexOf के बराबर होना चाहिए (क्योंकि यह यह करने के लिए प्रतिनिधियों)
• matches("ja") सही परिणाम देने नहीं होगा, क्योंकि यह की खोज करता है एक सटीक मिलान (केवल स्ट्रिंग "ja" ठीक प्रकार से दिखाई देगा)
• Pattern p = Pattern.compile("ja"); Matcher m = p.matcher("jack"); m.find(); नियमित अभिव्यक्ति के साथ ग्रंथों को खोजने के लिए सही तरीका होगा। अभ्यास (बड़े ग्रंथों का उपयोग) में यह सबसे कारगर केवल जावा एपीआई का उपयोग कर तरीका होगा। इसका कारण यह है एक निरंतर पैटर्न ("ja" की तरह) regex इंजन (जो धीमी है) द्वारा संसाधित नहीं किया जाएगा लेकिन द्वारा एक बोयर-मूर-एल्गोरिथ्म (जो तेज है)