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加速列表过滤

回答

相关问题