Muszę zamienić wiele różnych podciągów w ciągu w najbardziej efektywny sposób. czy jest inny sposób niż brutalna siła zastępowania każdego pola za pomocą string.replace?
Odpowiedzi:
Jeśli ciąg, na którym operujesz, jest bardzo długi lub operujesz na wielu ciągach, warto użyć java.util.regex.Matcher (kompilacja wymaga czasu z góry, więc nie będzie wydajna jeśli dane wejściowe są bardzo małe lub wzorzec wyszukiwania często się zmienia).
Poniżej znajduje się pełny przykład oparty na liście tokenów pobranych z mapy. (Używa StringUtils z Apache Commons Lang).
Map<String,String> tokens = new HashMap<String,String>();
tokens.put("cat", "Garfield");
tokens.put("beverage", "coffee");
String template = "%cat% really needs some %beverage%.";
// Create pattern of the format "%(cat|beverage)%"
String patternString = "%(" + StringUtils.join(tokens.keySet(), "|") + ")%";
Pattern pattern = Pattern.compile(patternString);
Matcher matcher = pattern.matcher(template);
StringBuffer sb = new StringBuffer();
while(matcher.find()) {
matcher.appendReplacement(sb, tokens.get(matcher.group(1)));
}
matcher.appendTail(sb);
System.out.println(sb.toString());
Po skompilowaniu wyrażenia regularnego skanowanie ciągu wejściowego jest zwykle bardzo szybkie (chociaż jeśli twoje wyrażenie regularne jest złożone lub obejmuje cofanie, nadal będziesz musiał wykonać test porównawczy, aby to potwierdzić!)
"%(" + StringUtils.join(tokens.keySet(), "|") + ")%";
Jednym z najbardziej wydajnych sposobów zastąpienia pasujących ciągów (bez wyrażeń regularnych) jest użycie algorytmu Aho-Corasick z wydajnym Trie (wymawiane „try”), szybkim algorytmem haszowania i wydajną implementacją kolekcji .
Proste rozwiązanie wykorzystuje Apache w StringUtils.replaceEachnastępujący sposób:
private String testStringUtils(
final String text, final Map<String, String> definitions ) {
final String[] keys = keys( definitions );
final String[] values = values( definitions );
return StringUtils.replaceEach( text, keys, values );
}
To spowalnia w przypadku dużych tekstów.
Implementacja Bora algorytmu Aho-Corasick wprowadza nieco większą złożoność, która staje się szczegółem implementacji dzięki zastosowaniu fasady z tą samą sygnaturą metody:
private String testBorAhoCorasick(
final String text, final Map<String, String> definitions ) {
// Create a buffer sufficiently large that re-allocations are minimized.
final StringBuilder sb = new StringBuilder( text.length() << 1 );
final TrieBuilder builder = Trie.builder();
builder.onlyWholeWords();
builder.removeOverlaps();
final String[] keys = keys( definitions );
for( final String key : keys ) {
builder.addKeyword( key );
}
final Trie trie = builder.build();
final Collection<Emit> emits = trie.parseText( text );
int prevIndex = 0;
for( final Emit emit : emits ) {
final int matchIndex = emit.getStart();
sb.append( text.substring( prevIndex, matchIndex ) );
sb.append( definitions.get( emit.getKeyword() ) );
prevIndex = emit.getEnd() + 1;
}
// Add the remainder of the string (contains no more matches).
sb.append( text.substring( prevIndex ) );
return sb.toString();
}
Dla testów porównawczych bufor został utworzony przy użyciu randomNumeric w następujący sposób:
private final static int TEXT_SIZE = 1000;
private final static int MATCHES_DIVISOR = 10;
private final static StringBuilder SOURCE
= new StringBuilder( randomNumeric( TEXT_SIZE ) );
Gdzie MATCHES_DIVISORdyktuje liczbę zmiennych do wstrzyknięcia:
private void injectVariables( final Map<String, String> definitions ) {
for( int i = (SOURCE.length() / MATCHES_DIVISOR) + 1; i > 0; i-- ) {
final int r = current().nextInt( 1, SOURCE.length() );
SOURCE.insert( r, randomKey( definitions ) );
}
}
Sam kod porównawczy ( JMH wydawał się przesadą ):
long duration = System.nanoTime();
final String result = testBorAhoCorasick( text, definitions );
duration = System.nanoTime() - duration;
System.out.println( elapsed( duration ) );
Prosty mikro-test z 1 000 000 znaków i 1000 losowo umieszczonych ciągów do zastąpienia.
Bez konkursu.
Używając 10000 znaków i 1000 pasujących ciągów do zamiany:
Podział się zamyka.
Używając 1000 znaków i 10 pasujących ciągów do zamiany:
W przypadku krótkich strun, koszt przygotowania Aho-Corasicka przyćmiewa podejście brutalnej siły o StringUtils.replaceEach.
Możliwe jest podejście hybrydowe oparte na długości tekstu, aby uzyskać to, co najlepsze z obu implementacji.
Rozważ porównanie innych implementacji dla tekstu dłuższego niż 1 MB, w tym:
Artykuły i informacje dotyczące algorytmu:
To zadziałało dla mnie:
String result = input.replaceAll("string1|string2|string3","replacementString");
Przykład:
String input = "applemangobananaarefruits";
String result = input.replaceAll("mango|are|ts","-");
System.out.println(result);
Wyjście: jabłkowo-bananowo-owocowe
Jeśli zamierzasz zmieniać String wiele razy, zwykle bardziej efektywne jest użycie StringBuilder (ale zmierz swoją wydajność, aby się dowiedzieć) :
String str = "The rain in Spain falls mainly on the plain";
StringBuilder sb = new StringBuilder(str);
// do your replacing in sb - although you'll find this trickier than simply using String
String newStr = sb.toString();
Za każdym razem, gdy wykonujesz zamianę na String, tworzony jest nowy obiekt String, ponieważ Ciągi są niezmienne. StringBuilder jest zmienny, to znaczy można go zmieniać tak bardzo, jak chcesz.
StringBuilderwykona zamianę bardziej efektywnie, ponieważ jego bufor tablicy znaków można określić na wymaganą długość. StringBuilderjest przeznaczony nie tylko do dołączania!
Oczywiście prawdziwe pytanie brzmi, czy to optymalizacja za daleko? JVM bardzo dobrze radzi sobie z tworzeniem wielu obiektów i późniejszym wyrzucaniem elementów bezużytecznych i podobnie jak w przypadku wszystkich pytań dotyczących optymalizacji, moje pierwsze pytanie dotyczy tego, czy zmierzyliście to i stwierdziliście, że jest to problem.
A co powiesz na użycie metody replaceAll () ?
str.replaceAll(search1, replace1).replaceAll(search2, replace2).replaceAll(search3, replace3).replaceAll(search4, replace4)
Rythm, silnik szablonów java, teraz wydany z nową funkcją zwaną trybem interpolacji ciągów, która umożliwia wykonanie czegoś takiego:
String result = Rythm.render("@name is inviting you", "Diana");
Powyższy przypadek pokazuje, że możesz przekazać argument do szablonu według pozycji. Rythm pozwala również na przekazywanie argumentów według nazwy:
Map<String, Object> args = new HashMap<String, Object>();
args.put("title", "Mr.");
args.put("name", "John");
String result = Rythm.render("Hello @title @name", args);
Uwaga Rythm jest BARDZO SZYBKI, około 2 do 3 razy szybszy niż String.format i prędkość, ponieważ kompiluje szablon do kodu bajtowego java, wydajność środowiska wykonawczego jest bardzo zbliżona do konkatentacji z StringBuilder.
Spinki do mankietów:
"%cat% really needs some %beverage%."; czy ten %oddzielny token nie jest predefiniowanym formatem? Twoja pierwsza uwaga jest jeszcze bardziej zabawna, JDK zapewnia wiele „starych możliwości”, niektóre z nich zaczynają się w latach 90-tych, dlaczego ludzie zawracają sobie głowę ich używaniem? Twoje komentarze i głosy w dół nie mają żadnego sensu
Poniższe jest oparte na odpowiedzi Todda Owena . To rozwiązanie powoduje, że jeśli zamienniki zawierają znaki o specjalnym znaczeniu w wyrażeniach regularnych, można uzyskać nieoczekiwane rezultaty. Chciałem również mieć możliwość opcjonalnego wyszukiwania bez uwzględniania wielkości liter. Oto co wymyśliłem:
/**
* Performs simultaneous search/replace of multiple strings. Case Sensitive!
*/
public String replaceMultiple(String target, Map<String, String> replacements) {
return replaceMultiple(target, replacements, true);
}
/**
* Performs simultaneous search/replace of multiple strings.
*
* @param target string to perform replacements on.
* @param replacements map where key represents value to search for, and value represents replacem
* @param caseSensitive whether or not the search is case-sensitive.
* @return replaced string
*/
public String replaceMultiple(String target, Map<String, String> replacements, boolean caseSensitive) {
if(target == null || "".equals(target) || replacements == null || replacements.size() == 0)
return target;
//if we are doing case-insensitive replacements, we need to make the map case-insensitive--make a new map with all-lower-case keys
if(!caseSensitive) {
Map<String, String> altReplacements = new HashMap<String, String>(replacements.size());
for(String key : replacements.keySet())
altReplacements.put(key.toLowerCase(), replacements.get(key));
replacements = altReplacements;
}
StringBuilder patternString = new StringBuilder();
if(!caseSensitive)
patternString.append("(?i)");
patternString.append('(');
boolean first = true;
for(String key : replacements.keySet()) {
if(first)
first = false;
else
patternString.append('|');
patternString.append(Pattern.quote(key));
}
patternString.append(')');
Pattern pattern = Pattern.compile(patternString.toString());
Matcher matcher = pattern.matcher(target);
StringBuffer res = new StringBuffer();
while(matcher.find()) {
String match = matcher.group(1);
if(!caseSensitive)
match = match.toLowerCase();
matcher.appendReplacement(res, replacements.get(match));
}
matcher.appendTail(res);
return res.toString();
}
Oto moje przypadki testów jednostkowych:
@Test
public void replaceMultipleTest() {
assertNull(ExtStringUtils.replaceMultiple(null, null));
assertNull(ExtStringUtils.replaceMultiple(null, Collections.<String, String>emptyMap()));
assertEquals("", ExtStringUtils.replaceMultiple("", null));
assertEquals("", ExtStringUtils.replaceMultiple("", Collections.<String, String>emptyMap()));
assertEquals("folks, we are not sane anymore. with me, i promise you, we will burn in flames", ExtStringUtils.replaceMultiple("folks, we are not winning anymore. with me, i promise you, we will win big league", makeMap("win big league", "burn in flames", "winning", "sane")));
assertEquals("bcaacbbcaacb", ExtStringUtils.replaceMultiple("abccbaabccba", makeMap("a", "b", "b", "c", "c", "a")));
assertEquals("bcaCBAbcCCBb", ExtStringUtils.replaceMultiple("abcCBAabCCBa", makeMap("a", "b", "b", "c", "c", "a")));
assertEquals("bcaacbbcaacb", ExtStringUtils.replaceMultiple("abcCBAabCCBa", makeMap("a", "b", "b", "c", "c", "a"), false));
assertEquals("c colon backslash temp backslash star dot star ", ExtStringUtils.replaceMultiple("c:\\temp\\*.*", makeMap(".", " dot ", ":", " colon ", "\\", " backslash ", "*", " star "), false));
}
private Map<String, String> makeMap(String ... vals) {
Map<String, String> map = new HashMap<String, String>(vals.length / 2);
for(int i = 1; i < vals.length; i+= 2)
map.put(vals[i-1], vals[i]);
return map;
}
public String replace(String input, Map<String, String> pairs) {
// Reverse lexic-order of keys is good enough for most cases,
// as it puts longer words before their prefixes ("tool" before "too").
// However, there are corner cases, which this algorithm doesn't handle
// no matter what order of keys you choose, eg. it fails to match "edit"
// before "bed" in "..bedit.." because "bed" appears first in the input,
// but "edit" may be the desired longer match. Depends which you prefer.
final Map<String, String> sorted =
new TreeMap<String, String>(Collections.reverseOrder());
sorted.putAll(pairs);
final String[] keys = sorted.keySet().toArray(new String[sorted.size()]);
final String[] vals = sorted.values().toArray(new String[sorted.size()]);
final int lo = 0, hi = input.length();
final StringBuilder result = new StringBuilder();
int s = lo;
for (int i = s; i < hi; i++) {
for (int p = 0; p < keys.length; p++) {
if (input.regionMatches(i, keys[p], 0, keys[p].length())) {
/* TODO: check for "edit", if this is "bed" in "..bedit.." case,
* i.e. look ahead for all prioritized/longer keys starting within
* the current match region; iff found, then ignore match ("bed")
* and continue search (find "edit" later), else handle match. */
// if (better-match-overlaps-right-ahead)
// continue;
result.append(input, s, i).append(vals[p]);
i += keys[p].length();
s = i--;
}
}
}
if (s == lo) // no matches? no changes!
return input;
return result.append(input, s, hi).toString();
}
Jest to pełna, jednoklasowa implementacja oparta na powyższej doskonałej odpowiedzi Dave'a Jarvisa . Klasa automatycznie wybiera jeden z dwóch różnych dostarczonych algorytmów w celu uzyskania maksymalnej wydajności. (Ta odpowiedź jest dla osób, które chciałyby po prostu szybko skopiować i wkleić).
package somepackage
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import org.ahocorasick.trie.Emit;
import org.ahocorasick.trie.Trie;
import org.ahocorasick.trie.Trie.TrieBuilder;
import org.apache.commons.lang3.StringUtils;
/**
* ReplaceStrings, This class is used to replace multiple strings in a section of text, with high
* time efficiency. The chosen algorithms were adapted from: https://stackoverflow.com/a/40836618
*/
public final class ReplaceStrings {
/**
* replace, This replaces multiple strings in a section of text, according to the supplied
* search and replace definitions. For maximum efficiency, this will automatically choose
* between two possible replacement algorithms.
*
* Performance note: If it is known in advance that the source text is long, then this method
* signature has a very small additional performance advantage over the other method signature.
* (Although either method signature will still choose the best algorithm.)
*/
public static String replace(
final String sourceText, final Map<String, String> searchReplaceDefinitions) {
final boolean useLongAlgorithm
= (sourceText.length() > 1000 || searchReplaceDefinitions.size() > 25);
if (useLongAlgorithm) {
// No parameter adaptations are needed for the long algorithm.
return replaceUsing_AhoCorasickAlgorithm(sourceText, searchReplaceDefinitions);
} else {
// Create search and replace arrays, which are needed by the short algorithm.
final ArrayList<String> searchList = new ArrayList<>();
final ArrayList<String> replaceList = new ArrayList<>();
final Set<Map.Entry<String, String>> allEntries = searchReplaceDefinitions.entrySet();
for (Map.Entry<String, String> entry : allEntries) {
searchList.add(entry.getKey());
replaceList.add(entry.getValue());
}
return replaceUsing_StringUtilsAlgorithm(sourceText, searchList, replaceList);
}
}
/**
* replace, This replaces multiple strings in a section of text, according to the supplied
* search strings and replacement strings. For maximum efficiency, this will automatically
* choose between two possible replacement algorithms.
*
* Performance note: If it is known in advance that the source text is short, then this method
* signature has a very small additional performance advantage over the other method signature.
* (Although either method signature will still choose the best algorithm.)
*/
public static String replace(final String sourceText,
final ArrayList<String> searchList, final ArrayList<String> replacementList) {
if (searchList.size() != replacementList.size()) {
throw new RuntimeException("ReplaceStrings.replace(), "
+ "The search list and the replacement list must be the same size.");
}
final boolean useLongAlgorithm = (sourceText.length() > 1000 || searchList.size() > 25);
if (useLongAlgorithm) {
// Create a definitions map, which is needed by the long algorithm.
HashMap<String, String> definitions = new HashMap<>();
final int searchListLength = searchList.size();
for (int index = 0; index < searchListLength; ++index) {
definitions.put(searchList.get(index), replacementList.get(index));
}
return replaceUsing_AhoCorasickAlgorithm(sourceText, definitions);
} else {
// No parameter adaptations are needed for the short algorithm.
return replaceUsing_StringUtilsAlgorithm(sourceText, searchList, replacementList);
}
}
/**
* replaceUsing_StringUtilsAlgorithm, This is a string replacement algorithm that is most
* efficient for sourceText under 1000 characters, and less than 25 search strings.
*/
private static String replaceUsing_StringUtilsAlgorithm(final String sourceText,
final ArrayList<String> searchList, final ArrayList<String> replacementList) {
final String[] searchArray = searchList.toArray(new String[]{});
final String[] replacementArray = replacementList.toArray(new String[]{});
return StringUtils.replaceEach(sourceText, searchArray, replacementArray);
}
/**
* replaceUsing_AhoCorasickAlgorithm, This is a string replacement algorithm that is most
* efficient for sourceText over 1000 characters, or large lists of search strings.
*/
private static String replaceUsing_AhoCorasickAlgorithm(final String sourceText,
final Map<String, String> searchReplaceDefinitions) {
// Create a buffer sufficiently large that re-allocations are minimized.
final StringBuilder sb = new StringBuilder(sourceText.length() << 1);
final TrieBuilder builder = Trie.builder();
builder.onlyWholeWords();
builder.ignoreOverlaps();
for (final String key : searchReplaceDefinitions.keySet()) {
builder.addKeyword(key);
}
final Trie trie = builder.build();
final Collection<Emit> emits = trie.parseText(sourceText);
int prevIndex = 0;
for (final Emit emit : emits) {
final int matchIndex = emit.getStart();
sb.append(sourceText.substring(prevIndex, matchIndex));
sb.append(searchReplaceDefinitions.get(emit.getKeyword()));
prevIndex = emit.getEnd() + 1;
}
// Add the remainder of the string (contains no more matches).
sb.append(sourceText.substring(prevIndex));
return sb.toString();
}
/**
* main, This contains some test and example code.
*/
public static void main(String[] args) {
String shortSource = "The quick brown fox jumped over something. ";
StringBuilder longSourceBuilder = new StringBuilder();
for (int i = 0; i < 50; ++i) {
longSourceBuilder.append(shortSource);
}
String longSource = longSourceBuilder.toString();
HashMap<String, String> searchReplaceMap = new HashMap<>();
ArrayList<String> searchList = new ArrayList<>();
ArrayList<String> replaceList = new ArrayList<>();
searchReplaceMap.put("fox", "grasshopper");
searchReplaceMap.put("something", "the mountain");
searchList.add("fox");
replaceList.add("grasshopper");
searchList.add("something");
replaceList.add("the mountain");
String shortResultUsingArrays = replace(shortSource, searchList, replaceList);
String shortResultUsingMap = replace(shortSource, searchReplaceMap);
String longResultUsingArrays = replace(longSource, searchList, replaceList);
String longResultUsingMap = replace(longSource, searchReplaceMap);
System.out.println(shortResultUsingArrays);
System.out.println("----------------------------------------------");
System.out.println(shortResultUsingMap);
System.out.println("----------------------------------------------");
System.out.println(longResultUsingArrays);
System.out.println("----------------------------------------------");
System.out.println(longResultUsingMap);
System.out.println("----------------------------------------------");
}
}
(W razie potrzeby dodaj je do pliku pom).
<!-- Apache Commons utilities. Super commonly used utilities.
https://mvnrepository.com/artifact/org.apache.commons/commons-lang3 -->
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-lang3</artifactId>
<version>3.10</version>
</dependency>
<!-- ahocorasick, An algorithm used for efficient searching and
replacing of multiple strings.
https://mvnrepository.com/artifact/org.ahocorasick/ahocorasick -->
<dependency>
<groupId>org.ahocorasick</groupId>
<artifactId>ahocorasick</artifactId>
<version>0.4.0</version>
</dependency>