如何优化替换字符串中的大量条目?

Question

我正在寻找一种用大量条目替换字符串的方法。

条目的大小为500~5000，大多数条目的字符长度不同。条目中没有正则表达式。不会被改变。
字符串的长度可以是10~250。包含unicode，每个都不同。
这个方法每秒将被调用大约100次。每个都是异步的。
必须按顺序更换，并以上次更换为准。

所以，我尝试过的方法是

public String method(String text) {
String result = text; // "This is a text. aabbuisaufdsafdsaa."
HashMap<String, String> map = getMap();
for (Map.Entry<String, String> entry : map.entrySet())
result = result.replace(entry.getKey(), entry.getValue());
return result;
}

非常缓慢。平均31000 ns, 1000个大小条目。

我目前使用的方法是StringUtils (commons-lang3 version 3.12.0):

private String[] searchList = null;
private String[] replacementList = null;
public String method(String text) {
String result = text; // "This is a text. aabbuisaufdsafdsaa."
result = StringUtils.replaceEachRepeatedly(result, getSearchList(), getReplacementList());
return result;
}
// Same with #getReplacementList.
private String[] getSearchList() {
// This will be init when this class loaded. I just paste it here.
if (this.searchList == null) {
HashMap<String, String> map = getMap();
this.searchList = new String[map.size()];
int index = 0;
for (Map.Entry<String, String> entry : map.entrySet()) {
this.searchList[index] = entry.getKey();
index++;
}
}
return this.searchList;
}

比上一级快50%~70%。平均11000 ns, 1000个大小条目。

所以我在寻找一个更好的方法，它可以更复杂。我唯一需要的就是快点。
如果有什么建议，我将不胜感激!

Answer 1

假设getMap()不变，每秒替换>1300次的完整实现(在我的机器上使用随机实例):

public static void main(String... args) {
// 10k keys to search in
final Map<String, String> map = IntStream
.range(0, 10_000)
.mapToObj(x -> randomWord())
.distinct()
.collect(toMap(x -> x, x -> randomWord()));
final StringSearcher<String> s = StringSearcher
.builder()
.ignoreOverlaps()
.addSearchStrings(map.keySet())
.build();
// bench 1000 times
final int TIMES = 1000;
long total_time = 0L;
for(int j = 0; j < TIMES; j++) {
// random big string 7k chars
final String big = IntStream
.range(0, 1_000)
.mapToObj(x -> randomWord())
.collect(joining());
final long startTime = System.currentTimeMillis();
// current index on the input string
int i = 0;
// output buffer, we will append text chunks
StringBuilder output = new StringBuilder();
// for every key in the input string...
for (Emit e : s.parseText(big)) {
// if there are text between previous key and current
if (e.getStart() > i)
// copy to buffer
output.append(big.subSequence(i, e.getStart() - 1));
// instead copy the key we copy the value (replace)
output.append(map.get(e.getSearchString()));
// the new pending position is at the end of the key
i = e.getEnd() + 1;
}
// if no more keys found may be text to copy to buffer
if (i < big.length())
output.append(big.subSequence(i, big.length() - 1));
// here output contains the replaced string.
total_time += System.currentTimeMillis() - startTime;
}
System.out.printf("Avg time: %f secs%n", total_time / (1000.0 * TIMES));
}
private static String randomWord() {
return Integer.toString(ThreadLocalRandom.current().nextInt(1_000_000, 10_000_000));
}

与输出

Avg time: 0,000768 secs

使用的Aho-Corasick-fast实现是neo-search:

<dependency>
<groupId>org.neosearch.stringsearcher</groupId>
<artifactId>multiple-string-searcher</artifactId>
<version>0.1.1</version>
</dependency>

键长度为6/7个字符，映射包含10k个要搜索的键，用于搜索和替换的长度文本为~7k。

使用您的参数(map中5k个键和250字节长度):

Avg time: 0,000052 secs

即>每秒19k个替换.