Java에서 대문자를 추출하는 가장 빠른 방법

Question

현재 인트론이 소문자이고 엑손이 대문자 인 문자열 형식의 DNA 시퀀스로 작업하고 있습니다. 이 메소드의 목적은 가능한 빨리 String 형태로 엑슨을 검색하는 것입니다. 시퀀스의

예 :

ATGGATGACAGgtgagaggacactcgggtcccagccccaggctctgccctcaggaagggggtcagctctcaggggcatctccctctcacagcccagccctggggatgatgtgggagccccatttatacacggtgcctccttctctcctagAGCCTACATAG는

내 첫 번째 버전은 문자열 완전히 대체하기() 메소드를 사용했지만 그것은 특히 느렸다 :

public String getExons(String sequence) { 
    return sequence.replaceAll("[atgc]", ""); 
} 

그래서 나는 시도 어느 새 버전 성능은 개선되었지만 상당히 느립니다.

public String getExons(String sequence) { 
    StringBuilder exonBuilder = new StringBuilder(); 

    for (int i = 0; i < sequence.length(); i++) { 
     char c = sequence.charAt(i); 
     if (c == 'A' || c == 'T' || c == 'G' || c == 'C') exonBuilder.append(c); 
    } 
    return exonBuilder.toString(); 

성능을 향상시키는 또 다른 방법이 있습니까? 아래

Answer 1

당신은 이중 포인터 트릭 char 배열을 사용해야합니다. 내 컴퓨터에서이 결과가 나타납니다.

편집 : 워밍업 단계로 업데이트되었습니다. 자바는 우분투 14 LTS

Edit2가에서 오픈 JDK 8 : 해시 테이블까지 차이로 가장 빠른 것입니다.

편집 3 : 코드에 버그가 있습니다. 더블 포인터 트릭이 가장 빠릅니다.

GTCtgACgGT 
getExons1: 1068 
getExons2: 377 
getExons3: 313 
getExons3b: 251 
getExons4: 586 
getExons5: 189 
getExons6: 671 

편집 4 : 1M DNA 문자열로 JMH로 벤치 마크 실행. 결과는 "Y보다 X"내 이전 벤치 마크에 대한과 일치하고는 최악의 정규 표현식되는 최고의되는 더블 포인터, 두 번째 가장 순진 3B 인 :

Benchmark     Mode Cnt Score Error Units 
MyBenchmark.benchExons1 thrpt 200 33.659 ± 1.036 ops/s 
MyBenchmark.benchExons2 thrpt 200 107.095 ± 4.074 ops/s 
MyBenchmark.benchExons3a thrpt 200 118.543 ± 3.779 ops/s 
MyBenchmark.benchExons3b thrpt 200 163.717 ± 4.602 ops/s 
MyBenchmark.benchExons4 thrpt 200 69.942 ± 2.019 ops/s 
MyBenchmark.benchExons5 thrpt 200 191.142 ± 5.307 ops/s 
MyBenchmark.benchExons6 thrpt 200 57.654 ± 1.963 ops/s 

Edit5 : 10 MB의 문자열 :

Benchmark     Mode Cnt Score Error Units 
MyBenchmark.benchExons1 thrpt 200 4.640 ± 0.068 ops/s 
MyBenchmark.benchExons2 thrpt 200 13.451 ± 0.161 ops/s 
MyBenchmark.benchExons3a thrpt 200 15.379 ± 0.232 ops/s 
MyBenchmark.benchExons3b thrpt 200 19.550 ± 0.181 ops/s 
MyBenchmark.benchExons4 thrpt 200 8.510 ± 0.147 ops/s 
MyBenchmark.benchExons5 thrpt 200 24.343 ± 0.331 ops/s 
MyBenchmark.benchExons6 thrpt 200 7.339 ± 0.074 ops/s 

코드 :

package org.sample; 

import org.openjdk.jmh.annotations.Benchmark; 
import org.openjdk.jmh.annotations.Scope; 
import org.openjdk.jmh.annotations.State; 

import java.util.HashMap; 
import java.util.Random; 

@State(Scope.Thread) 
public class MyBenchmark { 

    String DNA; 

    public MyBenchmark() { 
     DNA = buildRandomDNA(1000000); 
    } 

    static String letters = "ATGCatgc"; 

    public static String buildRandomDNA(int size) { 
     StringBuilder builder = new StringBuilder(size); 
     Random r = new Random(); 

     for (int i = 0; i < size; ++i) { 
      builder.append(letters.charAt(r.nextInt(letters.length()))); 
     } 

     return builder.toString(); 
    } 

    @Benchmark 
    public void benchExons1() { 
     getExons1(DNA); 
    } 

    @Benchmark 
    public void benchExons2() { 
     getExons2(DNA); 
    } 

    @Benchmark 
    public void benchExons3a() { 
     getExons3a(DNA); 
    } 

    @Benchmark 
    public void benchExons3b() { 
     getExons3b(DNA); 
    } 

    @Benchmark 
    public void benchExons4() { 
     getExons4(DNA); 
    } 

    @Benchmark 
    public void benchExons5() { 
     getExons5(DNA); 
    } 

    @Benchmark 
    public void benchExons6() { 
     getExons6(DNA); 
    } 

    public static String getExons1(String sequence) { 
     return sequence.replaceAll("[atgc]", ""); 
    } 

    public static String getExons2(String sequence) { 
     StringBuilder exonBuilder = new StringBuilder(); 

     for (int i = 0; i < sequence.length(); i++) { 
      char c = sequence.charAt(i); 
      if (c == 'A' || c == 'T' || c == 'G' || c == 'C') 
       exonBuilder.append(c); 
     } 
     return exonBuilder.toString(); 
    } 

    public static String getExons3a(String sequence) { 
     StringBuilder exonBuilder = new StringBuilder(); 

     for (int i = 0; i < sequence.length(); i++) { 
      char c = sequence.charAt(i); 
      if (c <= 'Z') { 
       exonBuilder.append((char) c); 
      } 
     } 

     return exonBuilder.toString(); 
    } 

    public static String getExons3b(String sequence1) { 
     char[] sequence = sequence1.toCharArray(); 
     StringBuilder exonBuilder = new StringBuilder(); 

     for (int i = 0; i < sequence.length; i++) { 
      if (sequence[i] <= 'Z') { 
       exonBuilder.append(sequence[i]); 
      } 
     } 

     return exonBuilder.toString(); 
    } 

    public static HashMap<String, String> M = new HashMap<String, String>(); 

    public static void buildTable() { 
     for (int a = 0; a < letters.length(); ++a) { 
      for (int b = 0; b < letters.length(); ++b) { 
       for (int c = 0; c < letters.length(); ++c) { 
        for (int d = 0; d < letters.length(); ++d) { 
         String key = "" + letters.charAt(a) + letters.charAt(b) + letters.charAt(c) + letters.charAt(d); 
         M.put(key, getExons1(key)); 
        } 
       } 
      } 
     } 
    } 

    public static String getExons4(String sequence1) { 
     char[] sequence = sequence1.toCharArray(); 
     StringBuilder exonBuilder = new StringBuilder(); 

     for (int i = 0; i < sequence.length; i += 4) { 
      exonBuilder.append(M.get(new String(sequence, i, 4))); 
     } 

     return exonBuilder.toString(); 
    } 

    public static String getExons5(String sequence1) { 
     char[] sequence = sequence1.toCharArray(); 
     int p = 0; 

     for (int i = 0; i < sequence.length; i++) { 
      if (sequence[i] <= 'Z') { 
       sequence[p] = sequence[i]; 
       ++p; 
      } 
     } 

     return new String(sequence, 0, p); 
    } 

    public static int dnatoint(char[] s, int start, int len) { 
     int key = 0; 
     for (; len > 0; len--, start++) { 
      switch (s[start]) { 
      case 'A': key = (key << 3) | 0; break; 
      case 'C': key = (key << 3) | 1; break; 
      case 'G': key = (key << 3) | 2; break; 
      case 'T': key = (key << 3) | 3; break; 
      case 'a': key = (key << 3) | 4; break; 
      case 'c': key = (key << 3) | 5; break; 
      case 'g': key = (key << 3) | 6; break; 
      case 't': key = (key << 3) | 7; break; 
      } 
     } 
     return key; 
    } 

    public static String[] M2 = new String[8*8*8*8]; 

    public static void buildTable2() { 
     for (int a = 0; a < letters.length(); ++a) { 
      for (int b = 0; b < letters.length(); ++b) { 
       for (int c = 0; c < letters.length(); ++c) { 
        for (int d = 0; d < letters.length(); ++d) { 
         String key = "" + letters.charAt(a) + letters.charAt(b) + letters.charAt(c) + letters.charAt(d); 
         M2[dnatoint(key.toCharArray(), 0, 4)] = getExons1(key); 
        } 
       } 
      } 
     } 
    } 

    public static String getExons6(String sequence1) { 
     char[] sequence = sequence1.toCharArray(); 
     StringBuilder exonBuilder = new StringBuilder(); 

     assert (sequence.length % 4) == 0; 

     for (int i = 0; i < sequence.length; i += 4) { 
      exonBuilder.append(M2[dnatoint(sequence, i, 4)]); 
     } 

     return exonBuilder.toString(); 
    } 

    static { 
     buildTable(); 
     buildTable2(); 
    } 

    //@Benchmark 
    public void testMethod() { 
     // This is a demo/sample template for building your JMH benchmarks. Edit as needed. 
     // Put your benchmark code here. 
    } 

} 

여기

Answer 2

사용 :

public String getExons(String sequence) { 
    StringBuilder exonBuilder = new StringBuilder(); 

    for (int i = 0; i < sequence.length(); i++) { 
     char c = sequence.charAt(i); 
     if((int)c>=65 && (int)c <=90){ 
      exonBuilder.append((char)c); 
     } 
    } 

    return exonBuilder.toString(); 

Answer 3

public static void main(String[] args) { 
    String str = "ATGGATGACAGgtgagaggacactcgggtcccagccccaggctctgccctcaggaagggggtcagctctcaggggcatctccctctcacagcccagccctggggatgatgtgggagccccatttatacacggtgcctccttctctcctagAGCCTACATAG"; 
    byte[] bytes = str.getBytes(); 

    for(int i=0; i<str.length(); i++) { 
     if (str.charAt(i) >= 90) { 
      bytes[i] = (byte) (str.charAt(i) - 32); 
     } 
    } 

    System.out.println(new String(bytes)); 
} 

Answer 4

내 의견 m에서, 대안 간결하고 간결하고 다른 사람들처럼 빨리 제안했다.

sequence.chars() 
    .filter(c -> c >= 65 && c <= 90) 
    .collect(StringBuilder::new, 
     (StringBuilder sb, int c) -> sb.append((char) c), 
     StringBuilder::append);