在Java中提取大写字母的最快方法

Question

我目前正在处理DNA序列字符串，其中小写字母表示内含子（introns），大写字母表示外显子（exons）。该方法的目的是尽可能快地检索出外显子形成的字符串。

以下是序列示例：

ATGGATGACAGgtgagaggacactcgggtcccagccccaggctctgccctcaggaagggggtcagctctcaggggcatctccctctcacagcccagccctggggatgatgtgggagccccatttatacacggtgcctccttctctcctagAGCCTACATAG

我的第一个版本使用了String replaceAll()方法，但速度特别慢：

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

有没有其他方法可以提高性能？

- Thibault Robin

---

你可以使用 new StringBuilder(sequence.length()) 来避免重新调整内部的 char[] 大小。不过在处理如此小的输入时，我想这不会有太大的差别。 - Andy Turner

你可以始终将输入字符串分成多个部分并使用并行处理。 - B.Gen.Jack.O.Neill

如果你真的想在速度方面尽可能做到最好，就不要使用字符串。一个核苷酸对可以用四位编码：两位表示a/g/t/c，一位表示内含子/外显子状态，最后一位是填充位，以便一个字节恰好包含两个核苷酸对。为了处理这么少的值而携带Unicode字符的所有负担是不值得的。 - biziclop

有些偏离主题，但如果您确实需要速度并且使用非常大的字符串，您可以考虑使用GPU。有一些库可以与Java一起使用，例如OpenCL的jocl。您甚至可以使用一些OpenGL包装器并直接使用着色器。 - B.Gen.Jack.O.Neill

如果您有成千上万个不同的字符串需要过滤，那么您真的应该考虑将任务并行化。但是也不要过度。创建10万个单独的任务提交给执行器将会产生巨大的开销。我可能会为每个CPU核心创建一个线程，并让它迭代总输入字符串数量的相应部分。这基本上也是在GPU上执行此操作的方式。 - JimmyB

Answer 1

你需要使用 char 数组和双指针技巧。 我在我的机器上得到了这个结果：

编辑：添加了热身阶段。Java 是来自 Ubuntu 14 LTS 的 OpenJDK 8

编辑2：哈希表是远远最快的。

编辑3：我在我的代码中有一个 bug。双指针技巧是最快的。

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

编辑4：使用JMH对1M DNA字符串进行基准测试。 结果与我以前的基准测试一致，即“x比y更好”，最差的是正则表达式，最好的是双指针，第二好的是naive 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

编辑5：处理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.
    }

}

- vz0

---

不错，虽然这个微基准测试并不完全正确。 - Kayaman

热身活动稍微改变了数字。3B似乎是最好的选择。 - vz0

你的基准测试结果存在误导性，因为它涵盖了许多常见基准测试陷阱：1）将多个基准测试合并在一个方法中；2）测量OSR存根而不是最终编译版本；3）没有消耗结果等。 - apangin

非常感谢您的回答！我尝试了getExons5方法，确实大大提高了程序的执行速度。我认为除非改变数据结构，否则不可能使它更快，正如一些人所建议的那样。 - Thibault Robin

@ThibaultRobin 是的，你应该对数据进行预处理，并将其保存为新文件，改变数据结构。10k x 100k是1GB的DNA。这在现今来说是廉价存储。 - vz0

我已经使用JMH重新运行了基准测试，使用一个1M字符串而不是10M原始字符串。一旦10M的测试完成，我会进行更新。使用1M字符串可以将整个字符串放入缓存中。 - vz0

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

- Mayur Maheshwari

---

不必将变量转换为“int”：c >= 65与此相同。另外，您可以使用c >= 'A'来消除魔法数字。 - Andy Turner

一次比较就足够了。在(char)c中不需要进行类型转换。 - talex

最好将预期的大小传递给StringBuilder构造函数。例如，sequence.length()或其他什么东西。 - user319799

1). 你只需要一个检查：c<=90。 2). 迭代由String（通过toCharArray）创建的字符数组将优于当前方法。 3). 写入巨大的char[]，然后从中创建一个String将优于当前方法。如果你应用我提到的更改，你将获得当前方法的约x2性能。 - user3707125

我会非常谨慎地考虑优化速度增益估计。Java甚至CPU有许多内部机制可以降低复杂性，并且可以通过使用预编译代码、分支预测等轻松忽略一些微调。 - B.Gen.Jack.O.Neill

Answer 3

以下是我认为更加简洁且与其他建议同样快速的替代方法。

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

- Jean-François Savard

---

我认为我们在这里不是在寻求意见，而是在寻找可衡量的事实。 - Kayaman

@Kayaman 显然这会违反 SO 的规定。事实上，这段代码的速度与此处使用的其他循环一样快。我认为这段代码更加简洁，特别是为了让用户不要将其视为现金并使用他们发现更易读的内容。 - Jean-François Savard

Answer 4

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

- Liping Huang

---

这似乎不能满足提问者的要求。 - Kayaman

@Kayaman你的意思是只替换'a'、't'、'g'、'c'吗？那么只需比较整数值，例如str.charAt(i) == 97 || str.charAt(i) == 116 || str.charAt(i) == 103 || str.charAt(i) == 99。 - Liping Huang

不行。你的解决方案不能将大写字符提取为字符串。 - Kayaman