[java] Java 한 번에 (또는 가장 효율적인 방법으로) 문자열의 여러 다른 하위 문자열 바꾸기

Question 1

가장 효율적인 방법으로 문자열의 여러 하위 문자열을 교체해야합니다. string.replace를 사용하여 각 필드를 대체하는 다른 방법이 있습니까?

Question 2

작업중인 문자열이 매우 길거나 많은 문자열에서 작업하는 경우 java.util.regex.Matcher를 사용하는 것이 좋습니다 (이렇게하려면 컴파일하는 데 시간이 오래 걸리므로 효율적이지 않습니다. 입력이 매우 적거나 검색 패턴이 자주 변경되는 경우).

아래는지도에서 가져온 토큰 목록을 기반으로 한 전체 예입니다. (Apache Commons Lang의 StringUtils 사용).

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

정규식이 컴파일되면 일반적으로 입력 문자열 스캔이 매우 빠릅니다 (정규식이 복잡하거나 역 추적을 포함하는 경우에도이를 확인하기 위해 벤치마킹해야합니다!).

Question 3

연산

정규식없이 일치하는 문자열을 대체하는 가장 효율적인 방법 중 하나는 Aho-Corasick 알고리즘 을 고성능 Trie ( “try”로 발음), 빠른 해싱 알고리즘 및 효율적인 컬렉션 구현 과 함께 사용 하는 것입니다.

간단한 코드

간단한 솔루션은 StringUtils.replaceEach다음과 같이 Apache를 활용 합니다.

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

이것은 큰 텍스트에서 느려집니다.

빠른 코드

Bor의 Aho-Corasick 알고리즘 구현은 동일한 메서드 시그니처가있는 파사드를 사용하여 구현 세부 사항이되는 약간 더 복잡합니다.

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

벤치 마크

벤치 마크의 경우 다음과 같이 randomNumeric 을 사용하여 버퍼를 생성했습니다 .

  private final static int TEXT_SIZE = 1000;
  private final static int MATCHES_DIVISOR = 10;

  private final static StringBuilder SOURCE
    = new StringBuilder( randomNumeric( TEXT_SIZE ) );

어디 MATCHES_DIVISOR지시 주입하는 변수의 수를 :

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

벤치 마크 코드 자체 ( JMH 가 과도하게 보임 ) :

long duration = System.nanoTime();
final String result = testBorAhoCorasick( text, definitions );
duration = System.nanoTime() - duration;
System.out.println( elapsed( duration ) );

1,000,000 : 1,000

1,000,000 개의 문자와 1,000 개의 무작위로 배치 된 문자열이있는 간단한 마이크로 벤치 마크입니다.

testStringUtils : 25 초, 25533 밀리
testBorAhoCorasick : 0 초, 68 밀리

경쟁없이.

10,000 : 1,000

10,000 자 및 1,000 개의 일치하는 문자열을 사용하여 대체 :

testStringUtils : 1 초, 1402 밀리
testBorAhoCorasick : 0 초, 37 밀리

분할이 종료됩니다.

1,000 : 10

1,000 자 및 10 개의 일치하는 문자열을 사용하여 대체 :

testStringUtils : 0 초, 7 밀리
testBorAhoCorasick : 0 초, 19 밀리

짧은 문자열의 경우 Aho-Corasick을 설정하는 오버 헤드는 다음과 같은 무차별 대입 접근 방식을가립니다. StringUtils.replaceEach .

두 구현 모두를 최대한 활용하기 위해 텍스트 길이를 기반으로 한 하이브리드 접근 방식이 가능합니다.

구현

다음을 포함하여 1MB보다 긴 텍스트에 대한 다른 구현을 비교해보십시오.

서류

알고리즘과 관련된 문서 및 정보 :

Question 4

이것은 나를 위해 일했습니다.

String result = input.replaceAll("string1|string2|string3","replacementString");

예:

String input = "applemangobananaarefruits";
String result = input.replaceAll("mango|are|ts","-");
System.out.println(result);

출력 : apple-banana-frui-

Question 5

문자열을 여러 번 변경하려는 경우 일반적으로 StringBuilder를 사용하는 것이 더 효율적입니다 (하지만 성능을 측정하여 알아 내십시오) .

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

String은 변경할 수 없기 때문에 String을 교체 할 때마다 새로운 String 객체가 생성됩니다. StringBuilder는 변경 가능합니다. 즉, 원하는만큼 변경할 수 있습니다.

Question 6

StringBuilder문자 배열 버퍼를 필요한 길이로 지정할 수 있으므로보다 효율적으로 교체를 수행합니다. StringBuilder추가 이상을 위해 설계되었습니다!

물론 진짜 질문은 이것이 너무 멀리 최적화 된 것인지 여부입니다. JVM은 여러 객체의 생성과 후속 가비지 수집을 매우 잘 처리하며 모든 최적화 질문과 마찬가지로 첫 번째 질문은 이것을 측정하고 문제라고 결정했는지 여부입니다.

Question 7

replaceAll () 메서드를 사용하는 것은 어떻 습니까?

Question 8

이제 자바 템플릿 엔진 인 Rythm 이 다음과 같은 작업을 수행 할 수있는 String interpolation mode 라는 새로운 기능과 함께 출시되었습니다 .

String result = Rythm.render("@name is inviting you", "Diana");

위의 경우는 위치별로 템플릿에 인자를 전달할 수 있음을 보여줍니다. Rythm을 사용하면 이름으로 인수를 전달할 수도 있습니다.

Map<String, Object> args = new HashMap<String, Object>();
args.put("title", "Mr.");
args.put("name", "John");
String result = Rythm.render("Hello @title @name", args);

참고 Rythm은 템플릿을 자바 바이트 코드로 컴파일하기 때문에 String.format 및 속도보다 약 2 ~ 3 배 빠르며 런타임 성능이 StringBuilder와의 연결에 매우 가깝습니다.

연결: