2

我正在解决的问题是从另一个字符串替换所有字符串。

我通过使用 String.replaceAll 在codingbat.com 上相当容易地解决了这个问题，并一直这样做直到第一个字符串不再包含另一个字符串。

但是，我不喜欢这种方法，因为它非常慢。我曾尝试在此网站上搜索更有效的方法，但遇到了以下问题：

在 Java 中执行大量字符串替换的最快方法

String.replaceAll 比自己完成工作要慢得多

他们通过使用 StringUtils 和 Patterns 解决了这个问题。我还是觉得这些方法太慢了！

当我编写此类问题的代码时，我喜欢使用 Java 将我的运行时间控制在两秒内。我正在使用 1,000,000 个字符的字符串对此进行测试。String.replaceAll 在两秒内运行良好，其他两种方法也是如此。

有没有人有这个问题的快速解决方案？谢谢！

编辑：不幸的是，我收到的答案仍然运行得太慢。是的，我的意思是创建一个新字符串，而不是更改旧字符串，对那个错误感到抱歉。

我不确定它是如何工作的，但我认为循环遍历每个字符并检查可能会起作用。有算法的东西。

4

5 回答 5

1

问题是您的字符串非常庞大，您只想移动/复制一次，所有使用多次调用替换的解决方案最终仍会做大量不必要的工作。

您真正想要使用的是Apache StringUtils.replaceEachRepeatedly，因为该方法处理搜索多个字符串，同时只构建结果字符串一个。

于 2015-02-20T17:34:33.637 回答
1

字符串是不可变的，因此您无法从中删除内容。这意味着您需要创建一个不包含您想要删除的内容的新字符串。当您使用 String.replace 时，它​​几乎就是这样做的：它创建一个新字符串。

注意 String.replaceAll 因为它使用了一个正则表达式，每次调用它时都会编译（所以永远不要在长循环中使用它）。这很可能是你的问题。

如果您需要使用正则表达式，请使用 Pattern 类来编译您的正则表达式并重用该实例来为您处理的每个字符串创建一个新的匹配器。如果你不重用你的 Pattern 实例，它会很慢。

如果不需要正则表达式，StringUtils 有一个不依赖正则表达式的 replaceEach()。

如果您正在处理一个大字符串。您可能希望以流方式执行操作并循环字符并将字符复制到 StringBuilder。

或者，您可以使用正则表达式在字符串中搜索特定模式并循环它找到的匹配项，并为每个匹配项附加从前一个匹配项到当前匹配项的所有内容到 StringBuilder。

于 2015-02-20T16:40:43.267 回答
0

我前段时间遇到过同样的问题，来到这篇文章：使用 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://stackoverflow.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。

于 2015-02-20T16:30:03.197 回答
0

除了每个方法（替换、StringUtils 或 Patterns，...）之外，您只有一个线程工作。

如果您可以将该线程完成的工作分成两个或更多，例如每个线程在字符串中的特定位置运行到另一个，您将能够获得快速解决方案。

棘手的部分是划分工作，然后将其连接在一起。这将取决于您如何读取字符串，例如最后将其写入何处。

问候，

于 2015-02-20T16:18:24.550 回答
0

我刚试过这个，结果是：

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

我很想看看它在别人的机器上运行得有多快。因为我的老板认为我的机器足够快！:)

于 2015-02-20T17:16:17.557 回答