Я пытаюсь улучшить производительность Java-функции, которая у меня есть, которая определяет, содержит ли данная строка поискa > 0 строк в коллекции. Это может показаться преждевременной оптимизацией, но функция называется 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). Существуют ли какие-либо структуры данных, которые позволили бы мне это сделать?
Можно значительно ускорить его с помощью алгоритма Ахо-Корасика.
Вы можете построить автомат Aho-Corasick для коллекции, используя O (общая длина всех строк в коллекциях) время и пространство. Тогда можно будет проверить, является ли одна из строк в коллекции подстрокой заданной строки S в O (S.lenght), пройдя этот автомат.
// 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"))
Это интенсивная работа с ЦП и не долгая работа или блокировка ввода-вывода. Если вы используете 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);
}
Кроме того, вместо List, a Set следует использовать в качестве базовой структуры данных, чтобы дублировать записи, если они есть, будут устранены.
Вы можете завершить поиск примерно через 2/3 времени, используя алгоритм Aho Corasick.
Принятый ответ от @user2040251 среди других (включая меня) предложил алгоритм Ахо Корасика.
Из ваших комментариев я вижу, что вы не ищете общее решение, а решение, которое хорошо работает в конкретном случае использования.
@Vlad создал возможный набор тестов для оценки некоторых предлагаемых решений.
Тесты, выполненные @Marco13 в реализации Java в http://ahocorasick.org/, показывают, что ваша первоначальная реализация была быстрее.
Ваши комментарии предоставили существенные дополнительные сведения о проблеме, которую вы пытаетесь решить:
Ранее я прокомментировал, что другие протестированные Ахо-Корасиком испытания находили все возможные матчи. Метод, который возвращался после первого совпадения, был намного быстрее. Чтобы узнать, была ли моя интуиция правильной, я создал ветку Robert Bor java Aho -Corasick. Эта ветвь теперь слита в Ахо-Корасик!
Я также реализовал метод, который выполнял каждый поиск в своем потоке. Эта реализация была ужасной и выполнялась примерно в 10 раз медленнее.
Обновление: С момента моего первоначального тестирования я столкнулся с Еще быстрее Aho-Corasick реализация.
Я включил контрольный пример реализации параллельного потока Java 8, предложенный @GladwinB, а также две com.eaio.stringsearch.
По-прежнему можно получить прибыль. В этой статье, например, описывается набор вариантов соответствия Aho-Corasick, который кажется подходящим для вашей проблемы. К более быстрому соответствию строк для обнаружения вторжений
Можете ли вы попробовать с этим решением:
final String[] searchList = searchCollection.toArray(new String[0]);
Arrays.sort(searchList, new Comparator<String>() {
@Override
public int compare(final String o1, final String o2) {
if (o1 == null && o2 == null) {
return 0;
}
if (o1 == null || o1.isEmpty()) {
return 1;
}
if (o2 == null || o2.isEmpty()) {
return -1;
}
return o1.compareTo(o2);
}
});
final int result = Arrays.binarySearch(searchList, searchString);
return result >= 0 ? true : false;
Сравните с этим своего рода инвертированную и оптимизированную версию:
public static boolean containsAny(String searchString, List<String> searchCollection) {
for (int offset = 0; offset < searchString.length(); offset++) {
for (String sought: searchCollection) {
int remainder = searchString.length() - offset;
if (remainder >= sought.length && searchString.startsWith(sought, offset)) {
return true;
}
}
}
return false;
}
Обратите внимание на использование startWith со смещением.
Я считаю, что наиболее подходящая структура данных для этого - это Дерево суффикса. Для строки размера n, построение дерева принимает Theta(n) и ищет в нем подстроку длиной m, принимает O(m).
Это одна из тех структур данных, которые очень хорошо подходят (и предназначены) для поиска строк. Это очень распространенная структура данных со многими реализациями в Интернете.
Как и многие другие люди, в целом для хранения и поиска строк существуют лучшие структуры данных. Проблема в вашем случае состоит в том, что ваш список содержит только 30 записей. Накладные расходы, добавленные с помощью более сложной структуры данных и алгоритма, могут легко перевесить выигрыш, который вы получите от него.
Не поймите меня неправильно, ваше узкое место - это строка indexOf. Похоже, что на нее приходится 95% обработки. Но если другие структуры данных не помогают (я попробовал готовый Aho-Corasick Trie, и это было в два раза медленнее), вот что проверить...
Комментарий об использовании indexOf, а не содержит сомнительный. В моих тестах. Я видел около 1,5 млн поисков в секунду с "содержит" и только около 700 тыс. С помощью indexOf. Если у вас есть те же результаты, это удвоит скорость прямо там.
Изменить
// This is a performance optimization of contains.
if (searchString.indexOf(stringInCollection, 0) > -1) {
[назад] на
if (searchString.contains(stringInCollection)) {
Если вам интересно, трю, с которым я тестировал, здесь: http://ahocorasick.org/, и код довольно прост. Проблема, которую я видел, это то, что у нее нет функции для раннего выхода после первого совпадения. Он анализирует всю строку и находит все совпадения. Это было быстрее, чем indexOf() для случаев, когда совпадений не было (830K/sec), но все еще медленнее, чем contains().
@Yrlec из вашего комментария, что searchCollection можно считать постоянным с небольшим количеством изменений, вы можете сортировать его и кэшировать, или вы можете реализовать собственный класс List, который хранит ссылку на отсортированные элементы, которые добавляются в он.
Причиной этого является то, что у вас есть сортировка searchCollection, тогда вы можете использовать метод compareTo для String и уменьшить количество итераций, тем самым увеличивая производительность вашего метода.
public static boolean containsAny(String searchString, List<String> searchCollectionSorted) {
int size = searchCollectionSorted.size();
for (int i = 0; i < size; i++) {
String stringInCollection = searchCollectionSorted.get(i);
if (!Util.isNullOrEmpty(stringInCollection)) {
if(stringInCollection.compareToIgnoreCase(searchString) > 0) {
if (searchString.startsWith(stringInCollection) {
return true;
} else {
// No point of iterating if we reach here as the searchstring is greater and hence iterations are saved improving performance
break;
}
}
}
} return false;
}
Вы можете использовать структуру данных HashSet. Но хэш-набор не позволит дублировать. Например, вы не можете иметь строку "foo" дважды в HashSet.
С положительной стороны сложность должна быть O (1).
http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html
TreeSet, HashSet или PrefixTree - неплохие решения. Вы должны предпочесть PrefixTree, если вам нужно будет найти, существует ли данный префикс в коллекции (сложность O (длина (S)), в противном случае используйте HashSet. http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html