Как эффективно удалить все экземпляры строки из другой строки?
Проблема, которую я решаю, это замена всех строк из другой строки.
Я довольно легко решил эту проблему на codingbat.com, используя String.replaceAll, и делал это до тех пор, пока первая строка больше не будет содержать другую строку.
Однако мне не нравится этот метод, так как он очень медленный. Я попытался найти этот сайт для более эффективных методов, и наткнулся на эти вопросы:
Самый быстрый способ выполнить много замен строк в Java
String.replaceAll значительно медленнее, чем делать работу самостоятельно
Они решили проблему с помощью StringUtils и Patterns. Я все еще думаю, что эти методы слишком медленные!
Когда я кодирую подобные проблемы, я предпочитаю сократить время выполнения Java на две секунды. Я проверяю это с помощью строки из 1000000 символов. String.replaceAll прошло хорошо за две секунды, как и два других метода.
У кого-нибудь есть быстрое решение этой проблемы? Спасибо!
РЕДАКТИРОВАТЬ: К сожалению, ответы, которые я получил, все еще работают слишком медленно. И да, я имел в виду сделать новую строку, а не менять старую, извините за эту ошибку.
Я не уверен, как это будет работать, но я думаю, что цикл по каждому символу и проверка могут работать. Что-то с алгоритмами.
5 ответов
Проблема в том, что ваша строка огромна, вы хотите переместить / скопировать ее только один раз, и все решения, использующие несколько вызовов для замены, все равно будут выполнять огромное количество ненужной работы.
Что вы действительно хотите использовать, так это Apache StringUtils.replaceEachRepeated, так как этот метод обрабатывает поиск нескольких строк, в то время как строит только одну строку результата.
Строки являются неизменными, поэтому вы не можете удалить из них вещи. Это означает, что вам нужно создать новую строку без того материала, который вы хотите удалить. Когда вы используете String.replace, это в значительной степени то, что он делает: он создает новую строку.
Остерегайтесь String.replaceAll, так как он использует регулярное выражение, которое компилируется при каждом его вызове (поэтому никогда не используйте его в длинном цикле). Это, вероятно, ваша проблема.
Если вам нужно использовать регулярные выражения, используйте класс Pattern для компиляции вашего регулярного выражения и повторно используйте экземпляр для создания нового Matcher для каждой строки, которую вы обрабатываете. Если вы не используете свой экземпляр Pattern, он будет медленным.
Если вам не нужно регулярное выражение, StringUtils имеет replaceEach(), который не использует регулярные выражения.
Если вы обрабатываете большую строку. Возможно, вы захотите сделать что-то в потоковом режиме, циклически перебирать символы и копировать символы в StringBuilder.
В качестве альтернативы, вы можете использовать регулярное выражение для поиска определенного шаблона в строке и зацикливать найденные совпадения и для каждого совпадения добавлять все, начиная от предыдущего совпадения до текущего совпадения, в StringBuilder.
Помимо времени, которое занимает каждый метод (replace, StringUtils или Patterns, ...), у вас работает только один поток.
Если вы можете разделить работу, выполняемую этим потоком, на два или более, например, каждый поток выполняется для определенной позиции в строке для другого, вы сможете получить быстрое решение.
Самое сложное - это разделить работу, а затем объединить ее. Это будет зависеть от того, как вы читаете строку, например, куда вы ее пишете.
С Уважением,
Я столкнулся с той же проблемой некоторое время назад и пришел к этому посту: Заменить все вхождения строки с помощью StringBuilder?
Используя реализацию, приведенную в посте:
public static void main(String[] args) {
String from = "A really long string full of ands and ors";
String replaceFrom = "and";
String replaceTo = "or";
long initTime = System.nanoTime();
String result1 = from.replace(replaceFrom, replaceTo);
System.out.println("Time1: " + (System.nanoTime() - initTime));
System.out.println(result1);
StringBuilder sb1 = new StringBuilder(from);
initTime = System.nanoTime();
replaceAll(sb1, replaceFrom, replaceTo);
System.out.println("Time1: " + (System.nanoTime() - initTime));
System.out.println(sb1.toString());
}
// From https://stackru.com/questions/3472663/replace-all-occurences-of-a-string-using-stringbuilder
public static void replaceAll(StringBuilder builder, String from, String to) {
int index = builder.indexOf(from);
while (index != -1) {
builder.replace(index, index + from.length(), to);
index += to.length(); // Move to the end of the replacement
index = builder.indexOf(from, index);
}
}
Объяснение лучшей производительности второго решения состоит в том, что оно опирается на StringBuilder, изменяемый объект, а не на неизменяемый String. Посмотрите Неизменность Строк в Java для лучшего объяснения.
Это решение будет работать как с использованием StringBuffer, так и StringBuilder, но, как объясняется в разделе Разница между StringBuilder и StringBuffer, StringBuffer синхронизируется, а StringBuilder - нет, поэтому, если вам не нужна синхронизация, лучше использовать StringBuilder.
Я только что попробовал это, что привело к:
100960923
197642683484
import java.util.Stack;
public class Test {
public static String removeAll(final String stringToModify, final String stringToFindAndRemove) {
if (stringToModify==null||stringToModify.length()==0) return new String(stringToModify);
if (stringToFindAndRemove==null||stringToFindAndRemove.length()==0) return new String(stringToModify);
if (stringToModify.length()<stringToFindAndRemove.length()) return new String(stringToModify);
int lastChar = 0;
int buffPos=0;
Stack<Integer>stack = new Stack<Integer>();
char[] chars = stringToModify.toCharArray();
char[] ref = stringToFindAndRemove.toCharArray();
char[] ret = new char[chars.length];
for (int a=0;a<chars.length;a++) {
if (chars[a]==ref[buffPos]) {
if (buffPos==ref.length-1) {
buffPos=0;
stack.pop();
} else {
if (buffPos==0) stack.push(lastChar);
buffPos++;
}
} else {
if (buffPos!=0) {
for (int b=0;b<buffPos;b++) {
ret[lastChar]=ref[b];
lastChar++;
}
a--;
buffPos = 0;
} else {
ret[lastChar]=chars[a];
lastChar++;
}
}
if (stack.size()>0&&(lastChar-stack.peek()>=ref.length)) {
while(stack.size()>0 && (lastChar-stack.peek()>=ref.length)) {
int top = stack.pop();
boolean f = true;
for (int foo=0;foo<ref.length;foo++) {
if (ret[top+foo]!=ref[foo]) {
f=false;
break;
}
}
if (f) lastChar=top;
}
}
}
if (buffPos!=0) {
for (int b=0;b<buffPos;b++) {
ret[lastChar]=ref[b];
lastChar++;
}
}
char[] out = new char[lastChar];
System.arraycopy(ret,0,out,0,lastChar);
return new String(out);
}
public static void main(final String[] args) {
StringBuffer s = new StringBuffer();
StringBuffer un = new StringBuffer();
for (int a=0;a<100000;a++) {
s.append("s");
un.append("un");
}
StringBuffer h = new StringBuffer(s);
h.append(un);
h.append("m");
String huge = h.toString();
String t = "sun";
long startTime = System.nanoTime();
String rep = removeAll(huge,t);
long endTime = System.nanoTime();
long duration = (endTime - startTime);
//System.out.println(rep);
System.out.println(duration);
startTime = System.nanoTime();
rep = new String(huge);
int pos = rep.indexOf(t);
while (pos!=-1) {
rep = rep.replaceAll(t,"");
pos = rep.indexOf(t);
}
endTime = System.nanoTime();
duration = (endTime - startTime);
//System.out.println(rep);
System.out.println(duration);
}
}
Мне было бы интересно посмотреть, как быстро это работает на чужой машине. Потому что мой босс считает, что моя машина достаточно быстрая!:)