Finding if a string contains any string in a collection

I'm trying to improve the performance of a Java-function I have that is determining whether a given search string contains >0 of the strings in a collection. This could look like premature optimization but the function is called A LOT so any speed up would be very beneficial.

The code currently looks like this:

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;
}

The list typically has about 30 elements and the same collection is reused a lot between each call.

The code above is a pretty straightforward linear search. I don't think it can be significantly improved unless we change the data structure to make it better than O(n). Are there any data structures that would enable me to do that?

---

It is possible to speed it up significatly with Aho-Corasick algorithm.

You can build an Aho-Corasick automaton for a collection using O(total lenght of all strings in a collections) time and space. Then it will be possible to check if one of the strings in a collection is a substring of a given string S in O(S.lenght) time by traversing this automaton.

---

// 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 + ")");

This creates a pattern of alternatives like "(abc|def|ghi)" . You might consider a case-insensitive search.

And in the function containsAny :

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

Regex compilation is relatively smart. It would be comparable to using a search tree of your collection of sought words: "agent" and "agitator" to ("ag", ("ent", "itator"))

---

This is a CPU intensive operation and not long running or blocked on I/O. If you are using Java 8 you can use parallel streams to do processing in parallel as shown below. The method has been changed to use Collection instead of List to keep it more flexible.

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

Furthermore, instead of using List , a Set should be used as the underlying data structure so that duplicate entries, if any, will be eliminated.

链接地址: http://www.djcxy.com/p/39810.html

上一篇: firebase本地服务器>如何在文件更改时刷新浏览器

下一篇: 查找一个字符串是否包含集合中的任何字符串