替代连续字符串.replace

string replace java

2022-09-01 12:34:03

我想替换字符串输入中的一些字符串：

string=string.replace("<h1>","<big><big><big><b>");
string=string.replace("</h1>","</b></big></big></big>");
string=string.replace("<h2>","<big><big>");
string=string.replace("</h2>","</big></big>");
string=string.replace("<h3>","<big>");
string=string.replace("</h3>","</big>");
string=string.replace("<h4>","<b>");
string=string.replace("</h4>","</b>");
string=string.replace("<h5>","<small><b>");
string=string.replace("</h5>","</b><small>");
string=string.replace("<h6>","<small>");
string=string.replace("</h6>","</small>");

如您所见，这种方法不是最好的，因为每次我都必须搜索要替换的部分等，并且字符串是不可变的......此外，输入很大，这意味着需要考虑一些性能问题。

有没有更好的方法来降低此代码的复杂性？

答案 1

尽管与String.replace（）相比，StringBuilder.replace（）是一个巨大的改进，但它仍然远远没有达到最佳状态。

问题在于，如果替换部件的长度与可替换部件的长度不同（适用于我们的情况），则可能必须分配更大的内部阵列，并且必须复制内容，然后将进行替换（这也涉及复制）。StringBuilder.replace()char

想象一下：您有一个包含 10.000 个字符的文本。如果要将位置（第 2 个字符）处的子字符串替换为，则实现必须重新分配至少大于 1 的缓冲区，必须将旧内容复制到新数组，并且必须将 9.997 个字符（从位置开始）复制到右侧 1 以适合，最后将的字符复制到起始位置。每次更换都必须这样做！这很慢。"XY"1"ABC"char3"ABC""XY""ABC"1

更快的解决方案：动态构建输出

我们可以动态构建输出：不包含可替换文本的部分可以简单地附加到输出中，如果我们找到可替换的片段，我们会附加替换而不是它。从理论上讲，只需循环输入一次即可生成输出。听起来很简单，实现它并不难。

实现：

我们将使用预加载的可替换替换字符串的映射：Map

Map<String, String> map = new HashMap<>();
map.put("<h1>", "<big><big><big><b>");
map.put("</h1>", "</b></big></big></big>");
map.put("<h2>", "<big><big>");
map.put("</h2>", "</big></big>");
map.put("<h3>", "<big>");
map.put("</h3>", "</big>");
map.put("<h4>", "<b>");
map.put("</h4>", "</b>");
map.put("<h5>", "<small><b>");
map.put("</h5>", "</b></small>");
map.put("<h6>", "<small>");
map.put("</h6>", "</small>");

使用这个，这里是替换器代码：（代码后面的更多解释）

public static String replaceTags(String src, Map<String, String> map) {
    StringBuilder sb = new StringBuilder(src.length() + src.length() / 2);

    for (int pos = 0;;) {
        int ltIdx = src.indexOf('<', pos);
        if (ltIdx < 0) {
            // No more '<', we're done:
            sb.append(src, pos, src.length());
            return sb.toString();
        }

        sb.append(src, pos, ltIdx); // Copy chars before '<'
        // Check if our hit is replaceable:
        boolean mismatch = true;
        for (Entry<String, String> e : map.entrySet()) {
            String key = e.getKey();
            if (src.regionMatches(ltIdx, key, 0, key.length())) {
                // Match, append the replacement:
                sb.append(e.getValue());
                pos = ltIdx + key.length();
                mismatch = false;
                break;
            }
        }
        if (mismatch) {
            sb.append('<');
            pos = ltIdx + 1;
        }
    }
}

测试它：

String in = "Yo<h1>TITLE</h1><h3>Hi!</h3>Nice day.<h6>Hi back!</h6>End";
System.out.println(in);
System.out.println(replaceTags(in, map));

输出：（换行以避免滚动条）

Yo<h1>TITLE</h1><h3>Hi!</h3>Nice day.<h6>Hi back!</h6>End

Yo<big><big><big><b>TITLE</b></big></big></big><big>Hi!</big>Nice day.
<small>Hi back!</small>End

这个解决方案比使用正则表达式更快，因为这涉及很多开销，比如编译 a ，创建一个等，正则表达式也更通用。它还会在引擎盖下创建许多临时对象，这些对象在更换后被丢弃。在这里，我只使用一个（在其引擎盖下加上数组），代码只迭代输入一次。此外，此解决方案比使用此答案顶部详述的要快得多。PatternMatcherStringBuildercharStringStringBuilder.replace()

注释和说明

我初始化了 in 方法，如下所示：StringBuilderreplaceTags()

StringBuilder sb = new StringBuilder(src.length() + src.length() / 2);

因此，基本上我以原始长度的150%的初始容量创建了它。这是因为我们的替换比可替换文本长，因此如果发生替换，输出显然会比输入长。提供更大的初始容量将导致根本不会重新分配内部（当然，所需的初始容量取决于可替换替换对及其在输入中的频率/发生频率，但这个+50%是一个很好的上限估计）。StringStringBuilderchar[]

我还利用了所有可替换字符串都以字符开头的事实，因此找到下一个潜在的可替换位置变得极快：'<'

int ltIdx = src.indexOf('<', pos);

它只是一个简单的循环和内部比较，并且由于它总是从开始搜索（而不是从输入开始），因此总的来说，代码只迭代输入一次。charStringposString

最后，为了判断可替换对象是否确实出现在潜在位置，我们使用 String.regionMatches（） 方法来检查可替换的 stings，这也是非常快的，因为它所做的只是比较循环中的值，并在第一个不匹配字符处返回。Stringchar

还有一个加号：

这个问题没有提到它，但是我们的输入是一个HTML文档。HTML 标记不区分大小写，这意味着输入可能包含而不是。
对于此算法，这不是问题。in 中有一个重载，它支持不区分大小写的比较：<H1><h1>regionMatches()String

boolean regionMatches(boolean ignoreCase, int toffset, String other,
                          int ooffset, int len);

因此，如果我们想修改我们的算法，以查找和替换相同但使用不同字母大小写的输入标签，我们只需要修改这一行：

if (src.regionMatches(true, ltIdx, key, 0, key.length())) {

使用此修改后的代码，可替换标记变得不区分大小写：

Yo<H1>TITLE</H1><h3>Hi!</h3>Nice day.<H6>Hi back!</H6>End
Yo<big><big><big><b>TITLE</b></big></big></big><big>Hi!</big>Nice day.
<small>Hi back!</small>End

答案 2

为了提高性能 - 使用。为方便起见，您可以使用它来存储值和替换。StringBuilderMap

Map<String, String> map = new HashMap<>();
map.put("<h1>","<big><big><big><b>");
map.put("</h1>","</b></big></big></big>");
map.put("<h2>","<big><big>");
...
StringBuilder builder = new StringBuilder(yourString);
for (String key : map.keySet()) {
    replaceAll(builder, key, map.get(key));
}

...要替换StringBuilder中的所有出现，您可以在此处检查：使用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);
    }
}