迭代字符串中所有字符的最快方法

Question

在Java中，迭代字符串中所有字符的最快方法是什么，这个：

 String str = "a really, really long string";
for (int i = 0, n = str.length(); i < n; i++) {
    char c = str.charAt(i);
}

或这个：

 char[] chars = str.toCharArray();
for (int i = 0, n = chars.length; i < n; i++) {
    char c = chars[i];
}

编辑 ：

我想知道的是，在长时间迭代期间重复调用 charAt 方法的成本最终是否小于或大于对 toCharArray 执行单次调用的成本—— --- 在开始时，然后在迭代期间直接访问数组。

如果有人可以为不同的字符串长度提供一个可靠的基准，考虑到 JIT 预热时间、JVM 启动时间等，而不仅仅是两次调用 System.currentTimeMillis() 之间的差异，那就太好了.

原文由 Óscar López 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

第一次更新：在生产环境中尝试之前（不建议），请先阅读： http ://www.javaspecialists.eu/archive/Issue237.html 从 Java 9 开始，所描述的解决方案将不再有效, 因为现在 Java 默认会将字符串存储为 byte[]。

第二次更新：截至 2016 年 10 月 25 日，在我的 AMDx64 8core 和源代码 1.8 上，使用 ‘charAt’ 和字段访问没有区别。看来 jvm 已充分优化以内联和简化任何 ‘string.charAt(n)’ 调用。

第三次更新：截至 2020 年 9 月 7 日，在我的 Ryzen 1950-X 16 内核和源代码 1.14 上，“charAt1”比字段访问慢 9 倍，“charAt2”比字段访问慢 4 倍。现场访问权重新成为明显的赢家。请注意，该程序需要对 Java 9+ 版本的 jvms 使用 byte[] 访问。

这完全取决于被检查的 String 的长度。如果，正如问题所说，它是针对 长 字符串，检查字符串的最快方法是使用反射来访问字符串的支持 char[] 。

使用 JDK 8（win32 和 win64）在 64 AMD Phenom II 4 核 955 @ 3.2 GHZ（客户端模式和服务器模式）上使用 9 种不同技术（见下文！）进行的完全随机基准测试表明，使用 String.charAt(n) 对于小字符串来说是最快的，使用 reflection 访问字符串后备数组几乎是大字符串的两倍。

本实验

• 尝试了 9 种不同的优化技术。

• 所有字符串内容都是随机的

• 测试是针对从 0、1、2、4、8、16 等开始的 2 倍数的字符串大小进行的。

• 每个字符串大小进行 1,000 次测试

• 每次测试都会随机排列。换句话说，每次测试都是以随机顺序完成的，超过 1000 次。

• 整个测试套件向前和向后完成，以显示 JVM 预热对优化和时间的影响。

• 整个套件执行两次，一次在 -client 模式下，另一个在 -server 模式下。

结论

-客户端模式（32位）

对于 长度为 1 到 256 个字符的 字符串，调用 string.charAt(i) 平均每秒处理 1340 万到 5.88 亿个字符。

此外，它总体上快 5.5%（客户端）和 13.9%（服务器），如下所示：

     for (int i = 0; i < data.length(); i++) {
        if (data.charAt(i) <= ' ') {
            doThrow();
        }
    }

而不是像这样使用本地最终长度变量：

     final int len = data.length();
    for (int i = 0; i < len; i++) {
        if (data.charAt(i) <= ' ') {
            doThrow();
        }
    }

对于长度为 512 到 256K 个字符 的长字符串，使用反射访问 String 的后备数组是最快的。 这种技术几乎是 String.charAt(i) 的两倍（快 178%）。此范围内的平均速度为每秒 11.11 亿个字符。

该字段必须提前获得，然后可以在库中的不同字符串上重复使用。有趣的是，与上面的代码不同，使用字段访问，使用本地最终长度变量比在循环检查中使用“chars.length”快 9%。以下是最快设置字段访问的方法：

    final Field field = String.class.getDeclaredField("value");
   field.setAccessible(true);

   try {
       final char[] chars = (char[]) field.get(data);
       final int len = chars.length;
       for (int i = 0; i < len; i++) {
           if (chars[i] <= ' ') {
               doThrow();
           }
       }
       return len;
   } catch (Exception ex) {
       throw new RuntimeException(ex);
   }

-server 模式特别说明

在我的 AMD 64 机器上的 64 位 Java 机器上，在服务器模式下的 32 个字符长度的字符串后，字段访问开始获胜。直到客户端模式下的 512 个字符长度才出现这种情况。

另外值得注意的是，我认为，当我在服务器模式下运行 JDK 8（32 位构建）时，大字符串和小字符串的整体性能都慢了 7%。这是 JDK 8 早期版本的 build 121 Dec 2013。所以，就目前而言，32 位服务器模式似乎比 32 位客户端模式慢。

话虽如此……似乎唯一值得调用的服务器模式是在 64 位机器上。否则它实际上会影响性能。

对于在 AMD64 上运行 -server mode 的 32 位构建，我可以这样说：

1. String.charAt(i) 总体上是明显的赢家。虽然大小在 8 到 512 个字符之间，但在“新”、“重用”和“字段”之间还是有赢家的。
2. String.charAt(i) 在客户端模式下快 45%
3. 在客户端模式下，大型字符串的字段访问速度是其两倍。

还值得一提的是，String.chars()（Stream 和并行版本）是个败笔。比任何其他方式都慢。 Streams API 是一种执行一般字符串操作的相当慢的方法。

愿望清单

Java String 可以具有接受优化方法的谓词，例如 contains(predicate)、forEach(consumer)、forEachWithIndex(consumer)。因此，无需用户知道长度或重复调用 String 方法，这些可以帮助解析库 beep-beep beep 加速。

继续做梦：）

快乐的弦乐！

~SH

该测试使用以下 9 种方法来测试字符串是否存在空格：

“charAt1”——以通常的方式检查字符串内容：

 int charAtMethod1(final String data) {
    final int len = data.length();
    for (int i = 0; i < len; i++) {
        if (data.charAt(i) <= ' ') {
            doThrow();
        }
    }
    return len;
}

“charAt2” – 与上面相同，但使用 String.length() 而不是为 LENGTh 制作最终的本地 int

 int charAtMethod2(final String data) {
    for (int i = 0; i < data.length(); i++) {
        if (data.charAt(i) <= ' ') {
            doThrow();
        }
    }
    return data.length();
}

“stream” – 使用新的 JAVA-8 String 的 IntStream 并传递一个谓词来进行检查

int streamMethod(final String data, final IntPredicate predicate) {
    if (data.chars().anyMatch(predicate)) {
        doThrow();
    }
    return data.length();
}

“streamPara”——和上面一样，但是 OH-LA-LA——并行！！！

 // avoid this at all costs
int streamParallelMethod(final String data, IntPredicate predicate) {
    if (data.chars().parallel().anyMatch(predicate)) {
        doThrow();
    }
    return data.length();
}

“reuse” – 用字符串内容重新填充一个可重复使用的 char[]

 int reuseBuffMethod(final char[] reusable, final String data) {
    final int len = data.length();
    data.getChars(0, len, reusable, 0);
    for (int i = 0; i < len; i++) {
        if (reusable[i] <= ' ') {
            doThrow();
        }
    }
    return len;
}

“new1” – 从字符串中获取 char[] 的新副本

int newMethod1(final String data) {
    final int len = data.length();
    final char[] copy = data.toCharArray();
    for (int i = 0; i < len; i++) {
        if (copy[i] <= ' ') {
            doThrow();
        }
    }
    return len;
}

“new2” – 同上，但使用 “FOR-EACH”

 int newMethod2(final String data) {
    for (final char c : data.toCharArray()) {
        if (c <= ' ') {
            doThrow();
        }
    }
    return data.length();
}

“field1”——花式！！获得访问字符串内部 char[] 的字段

int fieldMethod1(final Field field, final String data) {
    try {
        final char[] chars = (char[]) field.get(data);
        final int len = chars.length;
        for (int i = 0; i < len; i++) {
            if (chars[i] <= ' ') {
                doThrow();
            }
        }
        return len;
    } catch (Exception ex) {
        throw new RuntimeException(ex);
    }
}

“field2” – 同上，但使用 “FOR-EACH”

 int fieldMethod2(final Field field, final String data) {
    final char[] chars;
    try {
        chars = (char[]) field.get(data);
    } catch (Exception ex) {
        throw new RuntimeException(ex);
    }
    for (final char c : chars) {
        if (c <= ' ') {
            doThrow();
        }
    }
    return chars.length;
}

客户的复合结果 -client 模式（前向和后向测试相结合）

注意：在我的 AMD64 机器上，Java 32 位的 -client 模式和 Java 64 位的 -server 模式与下面的相同。

 Size     WINNER  charAt1 charAt2  stream streamPar   reuse    new1    new2  field1  field2
1        charAt    77.0     72.0   462.0     584.0   127.5    89.5    86.0   159.5   165.0
2        charAt    38.0     36.5   284.0   32712.5    57.5    48.3    50.3    89.0    91.5
4        charAt    19.5     18.5   458.6    3169.0    33.0    26.8    27.5    54.1    52.6
8        charAt     9.8      9.9   100.5    1370.9    17.3    14.4    15.0    26.9    26.4
16       charAt     6.1      6.5    73.4     857.0     8.4     8.2     8.3    13.6    13.5
32       charAt     3.9      3.7    54.8     428.9     5.0     4.9     4.7     7.0     7.2
64       charAt     2.7      2.6    48.2     232.9     3.0     3.2     3.3     3.9     4.0
128      charAt     2.1      1.9    43.7     138.8     2.1     2.6     2.6     2.4     2.6
256      charAt     1.9      1.6    42.4      90.6     1.7     2.1     2.1     1.7     1.8
512      field1     1.7      1.4    40.6      60.5     1.4     1.9     1.9     1.3     1.4
1,024    field1     1.6      1.4    40.0      45.6     1.2     1.9     2.1     1.0     1.2
2,048    field1     1.6      1.3    40.0      36.2     1.2     1.8     1.7     0.9     1.1
4,096    field1     1.6      1.3    39.7      32.6     1.2     1.8     1.7     0.9     1.0
8,192    field1     1.6      1.3    39.6      30.5     1.2     1.8     1.7     0.9     1.0
16,384   field1     1.6      1.3    39.8      28.4     1.2     1.8     1.7     0.8     1.0
32,768   field1     1.6      1.3    40.0      26.7     1.3     1.8     1.7     0.8     1.0
65,536   field1     1.6      1.3    39.8      26.3     1.3     1.8     1.7     0.8     1.0
131,072  field1     1.6      1.3    40.1      25.4     1.4     1.9     1.8     0.8     1.0
262,144  field1     1.6      1.3    39.6      25.2     1.5     1.9     1.9     0.8     1.0

服务器的复合结果 -server 模式（前向和后向测试相结合）

注意：这是在 AMD64 上以服务器模式运行的 Java 32 位测试。 Java 64 位的服务器模式与客户端模式中的 Java 32 位相同，只是字段访问在 32 个字符大小后开始获胜。

 Size     WINNER  charAt1 charAt2  stream streamPar   reuse    new1    new2  field1  field2
1        charAt     74.5    95.5   524.5     783.0    90.5   102.5    90.5   135.0   151.5
2        charAt     48.5    53.0   305.0   30851.3    59.3    57.5    52.0    88.5    91.8
4        charAt     28.8    32.1   132.8    2465.1    37.6    33.9    32.3    49.0    47.0
8          new2     18.0    18.6    63.4    1541.3    18.5    17.9    17.6    25.4    25.8
16         new2     14.0    14.7   129.4    1034.7    12.5    16.2    12.0    16.0    16.6
32         new2      7.8     9.1    19.3     431.5     8.1     7.0     6.7     7.9     8.7
64        reuse      6.1     7.5    11.7     204.7     3.5     3.9     4.3     4.2     4.1
128       reuse      6.8     6.8     9.0     101.0     2.6     3.0     3.0     2.6     2.7
256      field2      6.2     6.5     6.9      57.2     2.4     2.7     2.9     2.3     2.3
512       reuse      4.3     4.9     5.8      28.2     2.0     2.6     2.6     2.1     2.1
1,024    charAt      2.0     1.8     5.3      17.6     2.1     2.5     3.5     2.0     2.0
2,048    charAt      1.9     1.7     5.2      11.9     2.2     3.0     2.6     2.0     2.0
4,096    charAt      1.9     1.7     5.1       8.7     2.1     2.6     2.6     1.9     1.9
8,192    charAt      1.9     1.7     5.1       7.6     2.2     2.5     2.6     1.9     1.9
16,384   charAt      1.9     1.7     5.1       6.9     2.2     2.5     2.5     1.9     1.9
32,768   charAt      1.9     1.7     5.1       6.1     2.2     2.5     2.5     1.9     1.9
65,536   charAt      1.9     1.7     5.1       5.5     2.2     2.4     2.4     1.9     1.9
131,072  charAt      1.9     1.7     5.1       5.4     2.3     2.5     2.5     1.9     1.9
262,144  charAt      1.9     1.7     5.1       5.1     2.3     2.5     2.5     1.9     1.9

完整的可运行程序代码

（要在 Java 7 及更早版本上进行测试，请删除两个流测试）

 import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.function.IntPredicate;

/**
 * @author Saint Hill <http://stackoverflow.com/users/1584255/saint-hill>
 */
public final class TestStrings {

    // we will not test strings longer than 512KM
    final int MAX_STRING_SIZE = 1024 * 256;

    // for each string size, we will do all the tests
    // this many times
    final int TRIES_PER_STRING_SIZE = 1000;

    public static void main(String[] args) throws Exception {
        new TestStrings().run();
    }

    void run() throws Exception {

        // double the length of the data until it reaches MAX chars long
        // 0,1,2,4,8,16,32,64,128,256 ...
        final List<Integer> sizes = new ArrayList<>();
        for (int n = 0; n <= MAX_STRING_SIZE; n = (n == 0 ? 1 : n * 2)) {
            sizes.add(n);
        }

        // CREATE RANDOM (FOR SHUFFLING ORDER OF TESTS)
        final Random random = new Random();

        System.out.println("Rate in nanoseconds per character inspected.");
        System.out.printf("==== FORWARDS (tries per size: %s) ==== \n", TRIES_PER_STRING_SIZE);

        printHeadings(TRIES_PER_STRING_SIZE, random);

        for (int size : sizes) {
            reportResults(size, test(size, TRIES_PER_STRING_SIZE, random));
        }

        // reverse order or string sizes
        Collections.reverse(sizes);

        System.out.println("");
        System.out.println("Rate in nanoseconds per character inspected.");
        System.out.printf("==== BACKWARDS (tries per size: %s) ==== \n", TRIES_PER_STRING_SIZE);

        printHeadings(TRIES_PER_STRING_SIZE, random);

        for (int size : sizes) {
            reportResults(size, test(size, TRIES_PER_STRING_SIZE, random));

        }
    }

    ///
    ///
    ///  METHODS OF CHECKING THE CONTENTS
    ///  OF A STRING. ALWAYS CHECKING FOR
    ///  WHITESPACE (CHAR <=' ')
    ///
    ///
    // CHECK THE STRING CONTENTS
    int charAtMethod1(final String data) {
        final int len = data.length();
        for (int i = 0; i < len; i++) {
            if (data.charAt(i) <= ' ') {
                doThrow();
            }
        }
        return len;
    }

    // SAME AS ABOVE BUT USE String.length()
    // instead of making a new final local int
    int charAtMethod2(final String data) {
        for (int i = 0; i < data.length(); i++) {
            if (data.charAt(i) <= ' ') {
                doThrow();
            }
        }
        return data.length();
    }

    // USE new Java-8 String's IntStream
    // pass it a PREDICATE to do the checking
    int streamMethod(final String data, final IntPredicate predicate) {
        if (data.chars().anyMatch(predicate)) {
            doThrow();
        }
        return data.length();
    }

    // OH LA LA - GO PARALLEL!!!
    int streamParallelMethod(final String data, IntPredicate predicate) {
        if (data.chars().parallel().anyMatch(predicate)) {
            doThrow();
        }
        return data.length();
    }

    // Re-fill a resuable char[] with the contents
    // of the String's char[]
    int reuseBuffMethod(final char[] reusable, final String data) {
        final int len = data.length();
        data.getChars(0, len, reusable, 0);
        for (int i = 0; i < len; i++) {
            if (reusable[i] <= ' ') {
                doThrow();
            }
        }
        return len;
    }

    // Obtain a new copy of char[] from String
    int newMethod1(final String data) {
        final int len = data.length();
        final char[] copy = data.toCharArray();
        for (int i = 0; i < len; i++) {
            if (copy[i] <= ' ') {
                doThrow();
            }
        }
        return len;
    }

    // Obtain a new copy of char[] from String
    // but use FOR-EACH
    int newMethod2(final String data) {
        for (final char c : data.toCharArray()) {
            if (c <= ' ') {
                doThrow();
            }
        }
        return data.length();
    }

    // FANCY!
    // OBTAIN FIELD FOR ACCESS TO THE STRING'S
    // INTERNAL CHAR[]
    int fieldMethod1(final Field field, final String data) {
        try {
            final char[] chars = (char[]) field.get(data);
            final int len = chars.length;
            for (int i = 0; i < len; i++) {
                if (chars[i] <= ' ') {
                    doThrow();
                }
            }
            return len;
        } catch (Exception ex) {
            throw new RuntimeException(ex);
        }
    }

    // same as above but use FOR-EACH
    int fieldMethod2(final Field field, final String data) {
        final char[] chars;
        try {
            chars = (char[]) field.get(data);
        } catch (Exception ex) {
            throw new RuntimeException(ex);
        }
        for (final char c : chars) {
            if (c <= ' ') {
                doThrow();
            }
        }
        return chars.length;
    }

    /**
     *
     * Make a list of tests. We will shuffle a copy of this list repeatedly
     * while we repeat this test.
     *
     * @param data
     * @return
     */
    List<Jobber> makeTests(String data) throws Exception {
        // make a list of tests
        final List<Jobber> tests = new ArrayList<Jobber>();

        tests.add(new Jobber("charAt1") {
            int check() {
                return charAtMethod1(data);
            }
        });

        tests.add(new Jobber("charAt2") {
            int check() {
                return charAtMethod2(data);
            }
        });

        tests.add(new Jobber("stream") {
            final IntPredicate predicate = new IntPredicate() {
                public boolean test(int value) {
                    return value <= ' ';
                }
            };

            int check() {
                return streamMethod(data, predicate);
            }
        });

        tests.add(new Jobber("streamPar") {
            final IntPredicate predicate = new IntPredicate() {
                public boolean test(int value) {
                    return value <= ' ';
                }
            };

            int check() {
                return streamParallelMethod(data, predicate);
            }
        });

        // Reusable char[] method
        tests.add(new Jobber("reuse") {
            final char[] cbuff = new char[MAX_STRING_SIZE];

            int check() {
                return reuseBuffMethod(cbuff, data);
            }
        });

        // New char[] from String
        tests.add(new Jobber("new1") {
            int check() {
                return newMethod1(data);
            }
        });

        // New char[] from String
        tests.add(new Jobber("new2") {
            int check() {
                return newMethod2(data);
            }
        });

        // Use reflection for field access
        tests.add(new Jobber("field1") {
            final Field field;

            {
                field = String.class.getDeclaredField("value");
                field.setAccessible(true);
            }

            int check() {
                return fieldMethod1(field, data);
            }
        });

        // Use reflection for field access
        tests.add(new Jobber("field2") {
            final Field field;

            {
                field = String.class.getDeclaredField("value");
                field.setAccessible(true);
            }

            int check() {
                return fieldMethod2(field, data);
            }
        });

        return tests;
    }

    /**
     * We use this class to keep track of test results
     */
    abstract class Jobber {

        final String name;
        long nanos;
        long chars;
        long runs;

        Jobber(String name) {
            this.name = name;
        }

        abstract int check();

        final double nanosPerChar() {
            double charsPerRun = chars / runs;
            long nanosPerRun = nanos / runs;
            return charsPerRun == 0 ? nanosPerRun : nanosPerRun / charsPerRun;
        }

        final void run() {
            runs++;
            long time = System.nanoTime();
            chars += check();
            nanos += System.nanoTime() - time;
        }
    }

    // MAKE A TEST STRING OF RANDOM CHARACTERS A-Z
    private String makeTestString(int testSize, char start, char end) {
        Random r = new Random();
        char[] data = new char[testSize];
        for (int i = 0; i < data.length; i++) {
            data[i] = (char) (start + r.nextInt(end));
        }
        return new String(data);
    }

    // WE DO THIS IF WE FIND AN ILLEGAL CHARACTER IN THE STRING
    public void doThrow() {
        throw new RuntimeException("Bzzzt -- Illegal Character!!");
    }

    /**
     * 1. get random string of correct length 2. get tests (List<Jobber>) 3.
     * perform tests repeatedly, shuffling each time
     */
    List<Jobber> test(int size, int tries, Random random) throws Exception {
        String data = makeTestString(size, 'A', 'Z');
        List<Jobber> tests = makeTests(data);
        List<Jobber> copy = new ArrayList<>(tests);
        while (tries-- > 0) {
            Collections.shuffle(copy, random);
            for (Jobber ti : copy) {
                ti.run();
            }
        }
        // check to make sure all char counts the same
        long runs = tests.get(0).runs;
        long count = tests.get(0).chars;
        for (Jobber ti : tests) {
            if (ti.runs != runs && ti.chars != count) {
                throw new Exception("Char counts should match if all correct algorithms");
            }
        }
        return tests;
    }

    private void printHeadings(final int TRIES_PER_STRING_SIZE, final Random random) throws Exception {
        System.out.print("  Size");
        for (Jobber ti : test(0, TRIES_PER_STRING_SIZE, random)) {
            System.out.printf("%9s", ti.name);
        }
        System.out.println("");
    }

    private void reportResults(int size, List<Jobber> tests) {
        System.out.printf("%6d", size);
        for (Jobber ti : tests) {
            System.out.printf("%,9.2f", ti.nanosPerChar());
        }
        System.out.println("");
    }
}

原文由 The Coordinator 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

这只是微优化，您不必担心。

 char[] chars = str.toCharArray();

返回 str 字符数组的副本（在 JDK 中，它通过调用 System.arrayCopy 返回字符的副本）。

除此之外， str.charAt() 仅检查索引是否确实在边界内并返回数组索引内的字符。

第一个不会在 JVM 中创建额外的内存。

原文由 Buhake Sindi 发布，翻译遵循 CC BY-SA 3.0 许可协议