查找字符串是否包含集合中的任何字符串

Question

我正在尝试提高我所拥有的Java函数的性能,该函数确定给定的搜索字符串是否包含集合中> 0的字符串.这可能看起来像是过早优化但功能被称为A LOT,因此任何加速都会非常有益.

代码目前看起来像这样:

public static boolean containsAny(String searchString, List<String> searchCollection) {
    int size = searchCollection.size();
    for (int i = 0; i < size; i++) {
        String stringInCollection = searchCollection.get(i);
        if (!Util.isNullOrEmpty(stringInCollection)) {
            // This is a performance optimization of contains.
            if (searchString.indexOf(stringInCollection, 0) > -1) {
                return true;
            }
        }
    }
    return false;
}

该列表通常具有大约30个元素,并且在每次调用之间重复使用相同的集合.

上面的代码是一个非常简单的线性搜索.除非我们改变数据结构以使其优于O(n),否则我认为它不会得到显着改善.是否有任何数据结构可以让我这样做？

Answer 1

使用Aho-Corasick算法可以显着加快速度.

您可以使用O(集合中所有字符串的总长度)时间和空间为集合构建Aho-Corasick自动机.然后,通过遍历该自动机,可以检查集合中的一个字符串是否是O(S.lenght)时间内给定字符串S的子字符串.

Answer 2

// Make a regex pattern (once only):
StringBuilder pattern = new StringBuilder();
for (String sought : searchCollection) {
    if (!Util.isNullOrEmpty(sought)) {
        if (pattern.length() != 0) {
            pattern.append('|');
        }
        pattern.append(Pattern.quote(sought));
    }
}
final Pattern PATTERN = Pattern.compile("(" + pattern + ")");

这创造了一种替代品的模式"(abc|def|ghi)".您可以考虑使用不区分大小写的搜索.

并在功能containsAny:

Matcher m = PATTERN.matcher(searchString);
return m.find();

正则表达式编译相对聪明.它与使用您搜索的单词集合的搜索树相当:"agent" and "agitator" to ("ag", ("ent", "itator"))

Answer 3

这是一项CPU密集型操作,不会在I/O上长时间运行或阻塞.如果您使用的是Java 8,则可以使用并行流并行处理,如下所示.该方法已更改为使用Collection而不是List使其更灵活.

public static boolean containsAny(final String searchString,
        final Collection<String> searchCollection) {
    return searchCollection.stream().parallel()
            .anyMatch(x -> searchString.indexOf(x) > -1);
}

此外,应该使用Lista Set作为底层数据结构,而不是使用,以便消除重复的条目(如果有的话).