Проверьте файл plist вашего проекта. Это похоже на проблему с безопасностью транспорта приложений https://stackoverflow.com/a/30732693/6517981
Если вам нужна постоянная подстрока, а не регулярное выражение, я бы порекомендовал Boyer-Moore. В Интернете много исходного кода.
Кроме того, используйте кольцевой буфер, чтобы не думать слишком сильно о границах буфера.
Майк.
Вы можете увеличить скорость поиска очень больших строк, используя некоторый алгоритм поиска строк
Я бы сказал, переключитесь на символьное решение, и в этом случае вы должны сканировать первый символ в вашем целевом тексте, а затем, когда вы найдете этот символ увеличивает счетчик и ищет следующий символ. Каждый раз, когда вы не найдете следующего подряд символа, перезапускайте счетчик. Это будет работать следующим образом:
public boolean streamContainsString(Reader reader, String searchString) throws IOException {
char[] buffer = new char[1024];
int numCharsRead;
int count = 0;
while((numCharsRead = reader.read(buffer)) > 0) {
if (buffer[numCharsRead -1] == searchString.charAt(count))
count++;
else
count = 0;
if (count == searchString.size())
return true;
}
return false;
}
Единственная проблема - когда вы просматриваете символы ... и в этом случае должен быть способ запомнить вашу переменную count. Я не вижу простого способа сделать это, кроме как частной переменной для всего класса. В этом случае вы не должны создавать экземпляры count внутри этого метода.
Реализовать скользящее окно. Создайте свой буфер, переместите все элементы в буфере на один вперед и введите один новый символ в буфер в конце. Если буфер равен вашему искомому слову, он содержится.
Конечно, если вы хотите сделать это более эффективным, вы можете найти способ предотвратить перемещение всех элементов в буфере, например, используя циклический буфер и представление строк, которые «циклически» так, как это делает буфер, поэтому вам нужно только проверить равенство содержимого. Это сохраняет перемещение всех элементов в буфере.
Если вы не привязаны к использованию Reader, вы можете использовать API Java NIO для эффективной загрузки файла. Например (непроверено, но должно быть близко к рабочему):
public boolean streamContainsString(File input, String searchString) throws IOException {
Pattern pattern = Pattern.compile(Pattern.quote(searchString));
FileInputStream fis = new FileInputStream(input);
FileChannel fc = fis.getChannel();
int sz = (int) fc.size();
MappedByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, sz);
CharsetDecoder decoder = Charset.forName("UTF-8").newDecoder();
CharBuffer cb = decoder.decode(bb);
Matcher matcher = pattern.matcher(cb);
return matcher.matches();
}
По сути, это mmap () - файл для поиска, который зависит от операционной системы, чтобы сделать правильные вещи в отношении использования кеша и памяти. Однако обратите внимание, что map () дороже простого чтения файла в большой буфер для файлов размером менее 10 КБ.
Я считаю, что лучшим решением этой проблемы является простота. Помните, поскольку я читаю из потока, я хочу, чтобы количество операций чтения из потока было минимальным (поскольку задержка сети или диска может быть проблемой), сохраняя при этом объем используемой памяти постоянным (поскольку поток может быть очень большой по размеру). Фактическая эффективность сопоставления строк не является целью номер один (поскольку она уже изучена до смерти ).
Основываясь на предложении AlbertoPL, вот простое решение, которое сравнивает буфер с символом строки поиска по характеру. Ключевым моментом является то, что, поскольку поиск выполняется только по одному символу за раз, обратное отслеживание не требуется и, следовательно, не требуется никаких циклических буферов или буферов определенного размера.
Теперь, если кто-то сможет предложить аналогичную реализацию, основанную на алгоритме поиска Кнута-Морриса-Пратта , то у нас будет хорошее эффективное решение;)
public boolean streamContainsString(Reader reader, String searchString) throws IOException {
char[] buffer = new char[1024];
int numCharsRead;
int count = 0;
while((numCharsRead = reader.read(buffer)) > 0) {
for (int c = 0; c < numCharsRead; c++) {
if (buffer[c] == searchString.charAt(count))
count++;
else
count = 0;
if (count == searchString.length()) return true;
}
}
return false;
}
Вместо того, чтобы иметь буфер в виде массива, используйте абстракцию, реализующую кольцевой буфер . Расчет вашего индекса будет buf [(next + i)% sizeof (buf)]
, и вам нужно будет внимательно заполнять буфер наполовину за раз. Но пока строка поиска умещается в половине буфера, вы ее найдете.
Я думаю, вам нужно буферизовать небольшой объем на границе между буферами.
Например, если размер вашего буфера равен 1024, а длина SearchString равна 10, то, помимо поиска в каждом 1024-байтовом буфере, вам также необходимо искать каждый 18-байтовый переход между двумя буферами (9 байтов от конца предыдущий буфер объединен с 9 байтами от начала следующего буфера).
Этот ответ относился к первоначальной версии вопроса, где ключ должен был читать поток только настолько, насколько это необходимо для сопоставления со строкой, если эта строка присутствует. Это решение не отвечает требованию гарантировать фиксированное использование памяти, но, возможно, стоит подумать, если вы нашли этот вопрос и не связаны этим ограничением.
Если вы связаны ограничением использования постоянной памяти, Java хранит массивы любой тип в куче, поэтому обнуление ссылки никоим образом не освобождает память; Я думаю, что любое решение, включающее массивы в цикле, потребляет память в куче и требует GC.
Для простой реализации, возможно, Java 5 Scanner , который может принимать InputStream и использовать java.util.regex.
Здесь есть три хороших решения:
Если вы хотите что-то простое и достаточно быстрое, откажитесь от буфера и вместо этого реализуйте простой недетерминированный конечный автомат. Ваше состояние будет списком индексов в строке, которую вы ищете, и ваша логика будет выглядеть примерно так (псевдокод):
String Needle;
n = длина иглы ();
для каждого входного символа c сделать
добавить индекс 0 в список
для каждого индекса i в списке выполните
если c == игла [i], то
если i + 1 == n, то
вернуть истину
еще
замените i в списке на i + 1
конец
еще
удалить я из списка
конец
конец
конец
Это найдет строку, если она существует, и вам никогда не понадобится buffer.
Немного больше работы, но также быстрее: выполните преобразование NFA в DFA, которое заранее выясняет, какие списки индексов возможны, и присваивает каждому из них небольшое целое число. (Если вы читали о поиске строк в Википедии, это называется конструкцией powerset .) Тогда у вас есть одно состояние, и вы выполняете переход из одного состояния в другое для каждого входящего символа. Требуемый NFA - это просто DFA для строки, которой предшествует состояние, которое недетерминированно либо отбрасывает символ, либо пытается использовать текущий символ. Вам также понадобится явное состояние ошибки.
Если вы хотите что-то быстрее, создайте буфер, размер которого как минимум вдвое n
, и пользователя Boyer-Moore скомпилируют конечный автомат из ] игла
. Вы' У меня будет много дополнительных хлопот, потому что Бойера-Мура нетривиально реализовать (хотя вы найдете код в Интернете) и потому что вам нужно будет организовать перемещение строки через буфер. Вам нужно будет построить или найти кольцевой буфер, который может «скользить» без копирования; в противном случае вы, вероятно, вернете любой выигрыш в производительности, который мог бы получить от Boyer-Moore.
Алгоритм поиска Кнута-Морриса-Пратта никогда не выполняет резервное копирование; это как раз то свойство, которое вам нужно для поиска в потоке. Я использовал его раньше для решения этой проблемы, хотя могут быть более простые способы использования доступных библиотек Java. (Когда это до меня дошло, я работал над C в 90-х.)
KMP, по сути, является быстрым способом создания DFA с сопоставлением строк, как в предложении № 2 Нормана Рэмси.