JAVA加速列表過濾

我有一個初始列表與每個主題的主題和短語。JAVA加速列表過濾

public class Subject { 
    private String subject_name; 
    private List<Phrase> phrases; 
} 

public class Phrase { 
    private String phrase_name; 
}

我需要過濾初始科目列表（應該得到另一個列表），條件是短語名稱應符合在輸入文本的話。所以，如果我有作爲輸入列表：

subjects : 
[ 
    { 
     subject_name : "black", 
     phrases : 
     [ 
      phrase_name : "one", 
      phrase_name : "two", 
      phrase_name : "three"  
     ] 
    }, 
    { 
     subject_name : "white", 
     phrases : 
     [ 
      phrase_name : "qw", 
      phrase_name : "as", 
      phrase_name : "do", 
      phrase_name : "oopopop" 
     ] 
    }, 
    { 
     subject_name : "green", 
     phrases : 
     [ 
      phrase_name : "rrr", 
      phrase_name : "ppo" 
     ] 
    } 
]

，我必須爲輸入文本= "one year today some rrr"，最後我需要得到下面的列表

subjects : 
[ 
    { 
     subject_name : "black", 
     phrases : 
     [ 
      phrase_name : "one" 
     ] 
    }, 
    { 
     subject_name : "green", 
     phrases : 
     [ 
      phrase_name : "rrr" 
     ] 
    } 
]

下面做工精細的代碼，我得到想要的結果，但是當我需要根據文本大小過濾例如20000「文本」時，會花費我一些時間〜5分鐘的主題，所以速度很慢。

private List<Subject> filterSubjects(List<Subject> subjects, String text) { 
    List<Subject> result = new ArrayList<Subject>(); 

    for (Subject subject : subjects) { 

     List<Phrase> p = new ArrayList<Phrase>(); 
     for (Phrase phrase : subject.getPhrases()) { 
      String regex = "\\b(" + replaceSpecialChars(phrase.getName()).toLowerCase() + ")\\b"; 
      Pattern pattern = Pattern.compile(regex); 
      Matcher matcher = pattern.matcher(text); 

      if (matcher.find()) { 
       p.add(phrase); 
      } 
     } 

     if (!p.isEmpty()) { 
      result.add(new Subject.SubjectBuilder(subject.getSubjectId(), subject.getName()) 
        .setWeight(subject.getWeight()).setColor(subject.getColor()) 
        .setOntologyId(subject.getOntologyId()).setCreatedBy(subject.getCreatedBy()) 
        .setUpdatedBy(subject.getUpdatedBy()).setPhrases(p).build()); 

     } 
    } 

    return result; 
}

我也試圖與流，但因爲我不希望過濾初始主題列表中，但需要得到一個新的，不爲我工作：

subjects = subjects.stream() 
     .filter(s -> s.getPhrases().parallelStream() 
       .anyMatch(p -> text.matches(".*\\b" + replaceSpecialChars(p.getName().toLowerCase()) + "\\b.*"))) 
     .collect(Collectors.toList()); 

subjects.parallelStream() 
     .forEach(s -> s.getPhrases().removeIf(p -> !text.matches(".*\\b" 
       + replaceSpecialChars(p.getName().toLowerCase()) 
       + "\\b.*")));

編輯

這裏是分析的結果

來源

2017-09-08 Dumitru Gutu

您是否分析了它以查看最大的熱點？ – Kayaman

我剛剛做了，整個時間都被這種方法消耗掉了。第二名是replaceSpecialChars。 –

正則表達式可能不是這裏最好的選擇。 [使用JSON解析器]（https://stackoverflow.com/questions/2591098/how-to-parse-json-in-java）。 – Michael

在我看來，你不能擺脫for循環（這是代碼複雜度的絕對殺手），因爲你需要檢查每個主題（即使你在過濾之前對主題進行了排序）。所以，我認爲唯一可能的加速可以通過多線程完成（如果您不關心輸出列表中的順序）。爲此，您可以使用java的內置ExecutorService。它會產生指定數量的線程，您提交所有的過濾任務，並且ExecutorService會自動在這些線程間調度它們。

編輯：您可能還需要確保你的SubjectBuilder不創建的p副本，因爲這可能需要時間的巨大量了。

來源

2017-09-08 08:38:03 vatbub

我會嘗試擺脫正則表達式，因爲你正在爲每個主題中的每個短語編譯這些。我不知道這將是更有效，或者達到完全相同的結果，因爲我不能運行鍼對您的數據集，但你可以嘗試這樣的變化：

 List<Phrase> p = new ArrayList<Phrase>(); 
     for (Phrase phrase : subject.getPhrases()) { 
      //String regex = "\\b(" + phrase.getName().toLowerCase() + ")\\b"; 
      //Pattern pattern = Pattern.compile(regex); 
      //Matcher matcher = pattern.matcher(text); 
      // 
      //if (matcher.find()) { 
      // p.add(phrase); 
      //} 
      if (text.contains(phrase.getName().toLowerCase())) { 
       p.add(phrase); 
      } 
     }

我做了一個基本的測試我認爲它應該以類似的方式匹配

來源

2017-09-08 09:02:07 robjwilkins

包含不起作用，因爲我需要檢查我的整個單詞，而不是那個字符串是另一個字符串的一部分。所以規則是短語中的單詞是文本的一部分 –

@DumitruGutu對不起，你能提供一個例子嗎？謝謝 – robjwilkins

至於你提到你嘗試過流，沒有運氣，這是我嘗試你的函數轉換成流（警告：未經測試！）：

subjects.parallelStream() 
      .map(subject -> { 
       List<Phrase> filteredPhrases = subject.getPhrases().parallelStream() 
         .filter(p -> text.matches(".*\\b" + replaceSpecialChars(p.getName().toLowerCase()) + "\\b.*")) 
         .collect(Collectors.toList()); 
       return new AbstractMap.SimpleEntry<>(subject, filteredPhrases); 
      }) 
      .filter(entry -> !entry.getValue().isEmpty()) 
      .map(entry -> { 
       Subject subj = entry.getKey(); 
       List<Phrase> filteredPhrases = entry.getValue(); 
       return new Subject.SubjectBuilder(subj.getId(), subj.getName()).setWeight(subj.getWeight()).setPhrases(filteredPhrases); 
      }) 
      .map(Subject.SubjectBuilder::build) 
      .collect(Collectors.toList());

基本上，第一張地圖是要創建一對原始主題和過濾後的短語，在第二個映射中，這些對映射到一個實例，並初始化所有參數（還要注意，不是原始短語，而是過濾後的參數），第三個然後僅僅映射新主題的構建。我不確定這段代碼是否會比你的代碼更快（我也沒有測試它，所以沒有任何保證！），它只是一個想法，你如何用流解決你的任務。

來源

2017-09-08 09:59:45 hoefling

正如評論中所建議的那樣，您應該進行配置。恰當地使用，一個分析器應該給你比「整個時間在這個方法中消耗」更多的細節。您應該能夠看到在Pattern.compile()，Matcher.find()，ArrayList.add()以及所有其他方法（無論它們是您的還是JDK方法）中花費了多少時間。

你這樣做絕對至關重要，否則你就是在盲目工作中浪費精力。例如，也許ArrayList.add()正在花時間。你可以用各種方式解決它。但是，除非你有確鑿證據表明問題出在哪裏，否則爲什麼花時間呢？

您也可以應用提取方法重構，以便您有更多自己的方法供分析器報告。這樣做的好處是編譯器和運行時在優化小方法方面非常出色。

當你發現那裏的時間被消耗，你需要在兩種方法：

使該方法更有效
找到一個方法來調用該方法的次數更少

如果它在replaceSpecialChars()上花費了很多時間，那麼你應該看看它，並改善它的性能。

根據它們的複雜性，編譯正則表達式可能需要時間。如果replaceSpecialChars()中有一個Pattern.compile()，將它移動到某個地方只會調用一次（靜態初始化程序，構造函數等）。如果它使用正則表達式並且沒有Pattern.compile()，請考慮引入一個。

您的編輯顯示大部分時間都用於您向我們顯示的代碼調用的Pattern.compile()。

因爲您向我們顯示的代碼中的regex是使用數據中的字符串構建的，所以您不能只調用Pattern.compile()一次。但是，您可能會從記憶重複的短語中受益 - 這取決於數據中有多少重複。

Map<String, Pattern> patterns = new HashMap<>(); 

Pattern pattern(String s) { 
    Pattern pattern = patterns.get(s); 
    if(pattern == null) { 
     pattern = Pattern.compile("\\b" + s + "\\b"); 
     patterns.put(s,pattern); 
    } 
    return pattern; 
}

（請注意，這是不是線程安全的 - 有更好的緩存類，例如番石榴）

你可以做的查找，內文更容易，通過準備它（每輸入一次）：

轉換所有的邊界字符空格
一dd正面和背面的空間

現在你只需要preparedText.contains(" " + phrase.getName() + " ")。這避免了編譯一個正則表達式。您可以使用正則表達式來準備文本，但這隻需要進行一次（如果您有多個文本，則可以重新使用編譯的Pattern。

但是，如果你這樣做，你可能也會再次，根據不同的 - 這也可能

Set<String> wordSet = new HashSet<>(Arrays.asList(preparedText.split(" ")));

wordSet.contains(phrase.getName())應該比preparedText.contains(phrase.getName())快，足夠大的文本

：處理文本爲Set這是快於要搜索的字符串。 DAT a - 更快地遍歷text中的令牌，在一組中查找單詞，而不是遍歷單詞。這可能會以不同的順序返回物品 - 這是否重要取決於您的要求。

Set<String> lookingFor = collectWordsToFind(subject); 
StringTokenizer tokens = new StringTokenizer(text); 
for(String token : tokens) { 
    if(lookingFor.contains(token)) { // or if(lookingFor.remove(token)) 
      outputlist.add(token); 
    } 
}

這可以避免多次掃描每個text。

最後，踩着右後衛，我會考慮先預處理Subject數據，使得地圖phrase_name到Subject。也許你已經從外部源讀取數據 - 如果是這樣，通過各種手段，當你閱讀（也許不是你列出目前有）建立這個地圖：

Map<String,Set<Subject>> map = new HashMap<>(); 
for(Subject subject : subjects) { 
    for(String phrase : subject.phrases()) { 
     String name = phrase.name(); 
     Set<Subject> subjectsForName = map.get(name); 
     if(subjectsForName == null) { 
      subjectsForName = new HashSet<>(); 
      map.put(name, subjectsForName); 
     } 
     subjectsForName.add(subject); 
    } 
}

現在在每個單詞你輸入text，您可以快速獲得一組包含該詞組名稱的主題，Set<Subjects> subjectsForThisWord = map.get(word)。

Map<T,Collection<U>>是一種相當常見的模式，但像Guava和Apache Commons這樣的第三方集合庫提供了MultiMap，它們使用更簡潔的API來做同樣的事情。

來源

2017-09-08 10:57:54 slim

似乎Pattern.compile獲得方法的最多時間 –

使用Set爲文本不適用於我，因爲「短語」名稱可以是單詞（一個，兩個，三個單詞等）的組合。似乎text.contains在這裏是正確的解決方案 –

您必須找到的詞越多，執行不同的正則表達式匹配的成本越低。除了每個不同的正則表達式的準備成本之外，您還要爲每個單詞執行新的線性搜索操作。相反，讓引擎只匹配整個單詞，並對單詞執行快速地圖查找。

首先，準備一個查找圖

Map<String,Map.Entry<Phrase,Subject>> lookup = subject.stream() 
    .flatMap(s->s.getPhrases().stream().map(p->new AbstractMap.SimpleImmutableEntry<>(p,s))) 
    .collect(Collectors.toMap(e -> e.getKey().getName(), Function.identity()));

然後，使用正則表達式引擎以流在整個字和由Subject小號查找他們的相關聯的Subject/Phrase組合，組，並轉換所得到的基團與新Subject小號算賬：

List<Subject> result = 
    Pattern.compile("\\W+").splitAsStream(text) 
      .map(lookup::get) 
      .filter(Objects::nonNull) 
      .collect(Collectors.groupingBy(Map.Entry::getValue, 
         Collectors.mapping(Map.Entry::getKey, Collectors.toList()))) 
      .entrySet().stream() 
      .map(e -> { 
      Subject subject=e.getKey(); 
      return new Subject.SubjectBuilder(subject.getSubjectId(), subject.getName()) 
       .setWeight(subject.getWeight()).setColor(subject.getColor()) 
       .setOntologyId(subject.getOntologyId()).setCreatedBy(subject.getCreatedBy()) 
       .setUpdatedBy(subject.getUpdatedBy()).setPhrases(e.getValue()).build(); 
      }) 
      .collect(Collectors.toList());

它就會簡單得多，如果Subject.SubjectBuilder支持指定現有Subject作爲模板，而不必手動每個屬性複製......

來源

2017-09-08 14:13:34 Holger

看看它，你可能想'Pattern.compile（「\\ W +」）。splitAsStream（text）.distinct（）...'... – Holger

的解決方案似乎是使用非常簡單「包含」而不是使用模式消耗最多的處理時間：

private List<Subject> filterSubjects(List<Subject> subjects, String text) { 

    String SPACE_PATTERN = " "; 
    List<Subject> result = new ArrayList<Subject>(); 

    for (Subject subject : subjects) { 

     List<Phrase> p = new ArrayList<Phrase>(); 
     for (Phrase phrase : subject.getPhrases()) {   
      if (text.contains(SPACE_PATTERN + replaceSpecialChars(phrase.getName()).toLowerCase() + SPACE_PATTERN)) { 
       p.add(phrase); 
      } 
     } 

     if (!p.isEmpty()) { 
      result.add(new Subject.SubjectBuilder(subject.getSubjectId(), subject.getName()) 
        .setWeight(subject.getWeight()).setColor(subject.getColor()) 
        .setOntologyId(subject.getOntologyId()).setCreatedBy(subject.getCreatedBy()) 
        .setUpdatedBy(subject.getUpdatedBy()).setPhrases(p).build()); 

     } 
    } 

    return result; 
}

，讓我從性能〜5分鐘之前，現在〜20秒20K文本處理。我將優化的另一個步驟是從循環中取出replaceSpecialChars以獲得短語名稱

來源

2017-09-08 15:08:07

幹得好！我認爲應該通過@slim提供的建議。使用集合： 'Set set = new HashSet <>（Arrays.asList（text.split（「」）））; if（set.contains（phrase.getName（））|| set.contains（replaceSpecialChars（phrase.getName（））。toLowerCase（）））{...} –

JAVA加速列表過濾

回答

相關問題