Java : 문자열 간의 일치 검색

Question

2 개의 문자열이 주어지면 적어도 4 자의 첫 번째 일치 항목을 찾고 싶습니다.

이것은 현재 수행해야하는 코드입니다. 제대로 작동하지만 더 나은 방법이있을 수 있다고 생각합니다. 내가하는 일에 비명을 지르는 비효율적이거나 나쁜 관행이 있습니까? Apache Commons와 같은 일반적인 라이브러리가 있습니까?

Gene 클래스에 대해 걱정할 필요가 없습니다. 문제의 문자열 만 포함됩니다. 또한 GeneMatch()은 일치하는 항목이없는 반면, 인수가있는 GeneMatch 생성자는 일치하는 항목이 있음을 나타냅니다.

Constants.MIN_MATCH == 4,이 경우.

public static GeneMatch findMatch(Gene g0, Gene g1) { 

    String g0DNA = g0.getDNA(); 
    String g1DNA = g1.getDNA(); 

    if (g0DNA.equals("") || g1DNA.equals("")) { //there won't be a match if one is empty 
     return new GeneMatch(); 
    } 

    int g0Left = -1; 
    int g0Right = -1; 
    int g1Left = -1; 
    int g1Right = -1; 

    String window; 

    for (int inx = 0; inx <= g0DNA.length() - Constants.MIN_MATCH; inx++) { 
     window = g0DNA.substring(inx, inx + Constants.MIN_MATCH); 

     if (g1DNA.indexOf(window) != -1) { 

      g0Left = inx; 
      g0Right = inx + Constants.MIN_MATCH; 

      g1Left = g1DNA.indexOf(window); 
      g1Right = g1Left + Constants.MIN_MATCH; 

      /* grow the match to the right 
      * while the two right indices are less than the lengths of their respective strings, and the 
      * characters at the indices match, increment each index 
      */ 
      while (g0Right < g0DNA.length() && g1Right < g1DNA.length() && g0DNA.charAt(g0Right) == g1DNA.charAt(g1Right)) { 
       g0Right++; 
       g1Right++; 
      } 
      break; //we've already found a match, no need to continue sliding the window 
     } 
    } 

    //now that the indices are found, convert to Genes 
    if (g0Left == -1 || g0Right == -1 || g1Left == -1 || g1Right == -1) { //no match found 
     return new GeneMatch(); 
    } 

    Gene gL0 = new Gene(g0DNA.substring(0, g0Left)); 
    Gene gL1 = new Gene(g1DNA.substring(0, g1Left)); 

    Gene g0match = new Gene(g0DNA.substring(g0Left, g0Right)); 
    Gene g1match = new Gene(g1DNA.substring(g1Left, g1Right)); 

    Gene gR0 = new Gene(g0DNA.substring(g0Right)); 
    Gene gR1 = new Gene(g1DNA.substring(g1Right)); 

    //sanity check 
    assert g0DNA.equals(gL0.getDNA() + g0match.getDNA() + gR0.getDNA()) : "g0 didn't add up"; 
    assert g1DNA.equals(gL1.getDNA() + g1match.getDNA() + gR1.getDNA()) : "g1 didn't add up"; 

    return new GeneMatch(gL0, gR0, g0match, g1match, gL1, gR1); 

} 

Answer 1

현재 접근

1. 더블 g1DNA.indexOf (창) 전화 - 첫 번째 호출 결과를 저장하고 나중에 다시 사용할 수 있습니다;
2. 불필요한 문자열 창 = g0DNA.substring (INX, INX + Constants.MIN_MATCH)를 동안 건설 개체;
3. 어설 션이 인 경우 불필요한 gL0, gL1, gR0, gR1 구성;
4. 경우 (g0DNA.equals ("") || g1DNA.equals (""))를 확인하기 위해 검사 을 향상시킬 수있는 문자열이 는 적어도 4 개 개의 심볼마다 ;
5. 그것은 항상 더 나은 전화 등호() 일정에 , 즉 "".equals (ARG)를 사용합니다. 이 null 인 경우 가능한 NPE를 피할 수 있습니다. 여기서 은 큰 영향을 미치지 않으며, 적용 할 좋은 코딩 정책은 입니다.
6. 는 ""대체 할 수 String.isEmpty() 방법 있습니다.equals (arg);
7. DNA 문자열에 대해 Null 검사를 수행하지 않습니다.

개선

1. 그것은 짧은 문자열 루프 더 나은, 즉 당신은 dna1 및 dna2 길이를 확인하고 짧은 길이 하나에 대해 외부 루프를 수행해야합니다. 그것은 반복 수를 최소화 할 수 있습니다.
2. 새 문자열 개체 을 생성하지 않고 문자로 조작 할 수 있습니다. 또한 java.lang.CharSequence 구현을 위해 알고리즘을 수정할 수 있습니다.
3. 당신은 문자로 확인하고 는 외부 루프 반복의 시간을 최소화 하기 위해 타의 추종을 불허하는 것으로 판명되었다 시퀀스를 설정 계속 즉, 타의 추종을 불허하는 순서를 기억 할 수 있습니다. 예를 들어 'b' 문자가 많이 포함 된 문자열에 대해 을 반복합니다. 첫 번째 'b' 처리 중에 두 번째 문자열에 char가 포함되지 않았는지 확인합니다. 그걸 기억하고 후속 'b' 처리 열심히;
4. String.indexOf()을 사용하는 경우 문자열 시작 부분에서 검색이 수행됩니다. 검색 할 문자열이 오히려 이면 문제가 될 수 있습니다. 색인 문자 을 작성하는 것이 좋습니다. 나는. 당신이 모든 대상 문자열의 문자와 '문자'와 같은 빌드 매핑을 반복 할 수있는 경기를 찾는 전에 -> 을 '문자열 내에서 발생 의 인덱스 세트'. 따라서 루프 바디 검사를 많이 수행 할 수 있습니다. 긴 문자열의 경우 더 빨리 ;

일반 고려 '최선의'선택 입력 데이터 프로파일 및 알고리즘 사용 정책에 의존하기 때문에 더 '한 최고의 알고리즘' 없습니다 . 나는. 알고리즘이 거의 실행되지 않고 성능에 미치는 영향이 미미한 경우에는 최적화에 많은 시간을 할애 할 필요가 없으며 유지하기 쉬운 간단한 코드를 작성하는 것이 훨씬 좋습니다. 입력 문자열이 짧다면 건물 문자 인덱스 등에서 아무런 의미가 없습니다. 일반적으로 가능한 경우 사전 최적화를 피하고 거기에 병목 현상이있는 경우 결과 알고리즘을 선택할 때 신중하게 모든 입력 데이터를 고려하십시오.

Answer 2

나에게 상당히 좋아 보인다. 그냥 두 개의 작은 것들 :

1. 재사용 -1 == 존재에 대한 모든 사 바르를 확인하지 않는 대신에 두 번 (g1Left = g1DNA.indexOf(window);)

2. 그것을 호출 g1DNA.indexOf(window)의 결과 모두 세트로 어쨌든 그들을 즉시.

Answer 3

나에게 잘 어울립니다. 하나는 앞으로 나아갈 것이고 마이크로는 할당 측면에서 최적화 될 수 있지만 이것은 JIT 컴파일러의 일입니다. 알고리즘 속도가 너무 느리다면 프로파일 링을 시도하십시오.