JVM 문자열 메소드 구현

Question

String 클래스에는 다음과 같이 구현 된 이유를 이해할 수없는 몇 가지 메소드가 있습니다. 은 중 하나입니다.

public String replace(CharSequence target, CharSequence replacement) { 
    return Pattern.compile(target.toString(), Pattern.LITERAL).matcher(
      this).replaceAll(Matcher.quoteReplacement(replacement.toString())); 
} 

더 간단하고 효율적인 (빨리!) 방법에 비해 몇 가지 중요한 이점이 있습니까? "AXC"

시간 :
하려면 string.replace :
1,000,000 반복
는 "ABC"에서 "X"
결과 "B"를 대체 : 자바 7

public static String replace(String string, String searchFor, String replaceWith) { 

    StringBuilder result=new StringBuilder(); 

    int index=0; 
    int beginIndex=0; 
    while((index=string.indexOf(searchFor, index))!=-1){ 
     result.append(string.substring(beginIndex, index)+replaceWith); 
     index+=searchFor.length(); 
     beginIndex=index; 
    } 
    result.append(string.substring(beginIndex, string.length())); 

    return result.toString(); 

} 

통계 485ms
string.replaceAll : 490ms
는 일처럼 = 180ms

코드를 대체 최적화

public String replaceAll(String regex, String replacement) { 
    return Pattern.compile(regex).matcher(this).replaceAll(replacement); 
} 

플리트 구현되어야한다 :

public String[] split(String regex, int limit) { 
    return Pattern.compile(regex).split(this, limit); 
} 

바꾸기 방법의 논리에 따라

public String[] split(String regex, int limit) { 
    /* fastpath if the regex is a 
    (1)one-char String and this character is not one of the 
     RegEx's meta characters ".$|()[{^?*+\\", or 
    (2)two-char String and the first char is the backslash and 
     the second is not the ascii digit or ascii letter. 
    */ 
    char ch = 0; 
    if (((regex.value.length == 1 && 
     ".$|()[{^?*+\\".indexOf(ch = regex.charAt(0)) == -1) || 
     (regex.length() == 2 && 
      regex.charAt(0) == '\\' && 
      (((ch = regex.charAt(1))-'0')|('9'-ch)) < 0 && 
      ((ch-'a')|('z'-ch)) < 0 && 
      ((ch-'A')|('Z'-ch)) < 0)) && 
     (ch < Character.MIN_HIGH_SURROGATE || 
     ch > Character.MAX_LOW_SURROGATE)) 
    { 
     int off = 0; 
     int next = 0; 
     boolean limited = limit > 0; 
     ArrayList<String> list = new ArrayList<>(); 
     while ((next = indexOf(ch, off)) != -1) { 
      if (!limited || list.size() < limit - 1) { 
       list.add(substring(off, next)); 
       off = next + 1; 
      } else { // last one 
       //assert (list.size() == limit - 1); 
       list.add(substring(off, value.length)); 
       off = value.length; 
       break; 
      } 
     } 
     // If no match was found, return this 
     if (off == 0) 
      return new String[]{this}; 

     // Add remaining segment 
     if (!limited || list.size() < limit) 
      list.add(substring(off, value.length)); 

     // Construct result 
     int resultSize = list.size(); 
     if (limit == 0) 
      while (resultSize > 0 && list.get(resultSize - 1).length() == 0) 
       resultSize--; 
     String[] result = new String[resultSize]; 
     return list.subList(0, resultSize).toArray(result); 
    } 
    return Pattern.compile(regex).split(this, limit); 
} 

: E 자바 7 분할 방법은 크게 가능하면 패턴 컴파일/정규식 처리를 방지하도록 최적화

성능 손실은 replace 메서드에서 발견 된 성능 손실과 그리 멀지 않습니다. 어떤 이유로 오라클은 패스트 경로을 다른 방법이 아닌 일부 방법으로 제공합니다.

Answer 1

당신의 제안 된 방법이 실제로는 자신의 테스트 입력뿐만 아니라 프로그램이 던질 가능성이있는 모든 입력에 대해 String 클래스가 사용하는 정규식 기반 방법보다 실제로 빠릅니까? 서브 스트링 매칭을 수행하는 것은 String.indexOf에 의존하며, 그 자체가 나쁜 최악의 경우 성능에 영향을받는 순진 구현입니다. Pattern은 중복 비교를 피하기 위해 KMP과 같은보다 정교한 일치 알고리즘을 구현할 수 있습니다.

일반적으로 Java 팀은 ​​핵심 라이브러리의 성능을 매우 중요하게 생각하며 다양한 실제 데이터를 사용하여 많은 내부 벤치 마크를 유지합니다. 정규 표현식 처리가 병목 현상을 겪은 적이 한번도 없었습니다. 필자가 직면 한 충고는 올바르게 작동하는 가능한 가장 단순한 코드를 작성하는 것부터 시작하여, 프로파일 링이 병목 현상을 입증하고 다른 모든 방법을 사용하지 않을 때까지 자바 내장 함수를 다시 작성하는 것에 대해 생각하기조차하지 않습니다.

가장 최근 편집에 대해서는 먼저 split 방법을 많이 최적화 한 것으로 설명하지 않습니다. 그것은 매우 일반적인 일이 일어나는 특별한 경우를 처리하며, 순진한 문자열 매칭 알고리즘에 대해 위에서 설명한 단일 문자 리터럴 토큰으로 분리하는 최악의 경우의 복잡성을 겪지 않도록 보장됩니다.

replace에 대해 동일한 특수한 경우를 최적화 할 수 있으며 측정 가능한 개선 효과가있을 수 있습니다. 그러나 약 50 줄의 코드 -이 간단한 최적화를 달성하기 위해 무엇이 필요한지 살펴보십시오. 이러한 코드 라인은 비용이 많이 들며 특히 Java 라이브러리에서 가장 널리 사용되는 클래스의 일부일 때 유용합니다.비용은 여러 형태로 제공 :

• 자원을 - 즉 일부 개발자가 시간 쓰기, 테스트, 문서화를 지출해야하는 코드의 50 개 라인을, 그리고 자바 언어의 수명 동안 유지.
• 위험도 - 초기 테스트를 통과하지 못한 미묘한 버그에 대해서는 50 가지 기회가 있습니다.
• 복잡성 - 코드가 50 줄 추가되었으므로 메서드 작동 방식을 이해하려는 개발자는 이제 읽고 이해하는 데 시간이 걸립니다.

"이 특수 효과 방법은 특수 케이스를 처리하기 위해 최적화 된 이유는 무엇입니까?" 또는 더 일반적으로 "왜이 특정 기능이 구현되지 않았습니까?" 원저자는 물론 그 누구도 그 대답에 대해 명확하게 대답 할 수는 없지만, 그 기능에 대한 충분한 수요가 없거나 기능을 통해 얻는 이점이 그 기능을 추가 할만한 가치가없는 것으로 여겨지는 경우가 대부분입니다.