तेज स्ट्रिंग मिलान/इटरेशन विधि?

Question

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

String[] targetWords; // contains "inventory", "finished", and "goods" 
ArrayList<String> extractedStrings = new ArrayList<String>(); 

for (int i = 0; i < listOfWords.size(); i++) { 
    String[] words = listOfWords.get(i).split(" "); 
    outerloop: 
    for (int j = 0; j < words.length; j++) { 
     for (int k = 0; k < targetWords.length; k++) { 
      if (words[j].equalsIgnoreCase(targetWords[k])) { 
       extractedStrings.add(listOfWords.get(i)); 
       break outerloop; 
      } 
     } 
    } 
} 

सूची 100k से अधिक शब्द हैं, और इस के साथ प्रत्येक लक्ष्य वाक्यांश के लिए कार्य को पूरा करने rounghly .4 .8 के लिए सेकंड लेता है: अभी, मैं विचार इस प्रकार से लागू किया। चीजें हैं, मेरे पास प्रक्रिया के लिए इनमें से बहुत से लक्ष्य वाक्यांश हैं, और सेकंड वास्तव में जोड़ते हैं। इस प्रकार, मैं सोच रहा था कि क्या कोई इस कार्य को पूरा करने के लिए एक अधिक कुशल तरीका के बारे में जानता था? अग्रिम में मदद के लिए धन्यवाद!

Answer 1

आप गर्त targetWords से तत्वों में से प्रत्येक से गुजर रहे हैं, बजाय एक साथ targetWords से सभी शब्दों के लिए जाँच की। इसके अलावा, आप प्रत्येक पुनरावृत्ति में शब्दों की अपनी सूची को बिना किसी आवश्यकता के विभाजित कर रहे हैं, ओवरहेड बना रहे हैं।

मैं सुझाव है कि आप गठबंधन अपने targetWords में एक (संकलित) regular expression:

(?xi) # turn on comments, use case insensitive matching 
\b  # word boundary, i.e. start/end of string, whitespace 
(  # begin of group containing 'inventory' or 'finished' or 'goods' 
inventory|finished|goods # bar separates alternatives 
)  # end of group 
\b  # word boundary 

मत भूलना दोहरे-उद्धरण के लिए अपने नियमित अभिव्यक्ति स्ट्रिंग में backspaces।

import java.util.regex.*; 
... 
Pattern targetPattern = Pattern.compile("(?xi)\\b(inventory|finished|goods)\\b"); 
for (String singleString : listOfWords) { 
    if (targetPattern.matcher(singleString).find()) { 
    extractedStrings.add(singleString); 
    } 
} 

आप नियमित अभिव्यक्ति की गति के साथ संतुष्ट नहीं हैं - हालांकि नियमित अभिव्यक्ति इंजन आमतौर पर प्रदर्शन के लिए अनुकूलित कर रहे हैं - आप अपने खुद के उच्च गति बहु स्ट्रिंग खोज रोल करने की जरूरत है। Aho–Corasick string matching algorithm को पाठ में कई निश्चित तारों को खोजने के लिए अनुकूलित किया गया है, लेकिन निश्चित रूप से इस एल्गोरिदम को कार्यान्वित करना केवल पैटर्न बनाने की तुलना में काफी प्रयास है।

Answer 2

मैं प्रत्येक शब्द के लिए समानांतरता के लिए इसे ExecutorService के साथ कार्यान्वित करने का प्रयास करूंगा। http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ExecutorService.html

निश्चित थ्रेड पूल के आकार के साथ उदाहरण के लिए:

Executors.newFixedThreadPool(20); 

Answer 3

100k शब्द की आपकी सूची (एक बार) एक HashSet के लिए जोड़ा जा सकता है। अपनी सूची के माध्यम से पुनरावृत्ति करने के बजाय, wordSet.contains() का उपयोग करें - एक हैशसेट इसके लिए निरंतर समय का प्रदर्शन देता है, इसलिए सूची के आकार से प्रभावित नहीं होता है।

Answer 4

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

कुंजी लुकअप को कम कर रही है। इस तकनीक का उपयोग करके आप तेजी से लुकअप के लिए शब्दों की अपनी विशाल सूची को प्रभावी ढंग से अनुक्रमणित करेंगे।

Answer 5

यदि आप संपूर्ण वाक्यांश या सूची से केवल एक शब्द चाहते हैं तो मैं थोड़ा उलझन में हूं। यदि आप सूची से स्ट्रिंग प्राप्त करने का प्रयास कर रहे हैं तो अगर आपके लक्षित शब्दों में से एक स्ट्रिंग में है तो यह आपके लिए काम करना चाहिए।

String[] targetWords= new String[]{"inventory", "finished", "goods"}; 
    List<String> listOfWords = new ArrayList<String>(); 

    // build lookup map 
    Map<String, ArrayList<String>> lookupMap = new HashMap<String, ArrayList<String>>(); 
    for(String words : listOfWords) { 
     for(String word : words.split(" ")) { 
      if(lookupMap.get(word) == null) lookupMap.put(word, new ArrayList<String>()); 
      lookupMap.get(word).add(words); 
     } 
    } 

    // find phrases 
    Set<String> extractedStrings = new HashSet<String>(); 
    for(String target : targetWords) { 
     if(lookupMap.containsKey(target)) extractedStrings.addAll(lookupMap.get(target)); 
    }