在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在开始时执行单个调用然后在迭代期间直接访问数组的成本。
charAt
toCharArray
如果有人可以为不同的字符串长度提供可靠的基准测试,考虑到 JIT 预热时间、JVM 启动时间等,而不仅仅是两次调用System.currentTimeMillis().
System.currentTimeMillis()
第一次更新:在生产环境中尝试之前(不建议),请先阅读: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[]字符串的支持。
String
char[]
使用 JDK 8(win32 和 win64)在 64 AMD Phenom II 4 核 955 @ 3.2 GHZ(客户端模式和服务器模式)上使用 9 种不同技术(见下文!)进行的完全随机基准测试表明,String.charAt(n)对于小型计算机来说,使用是最快的字符串,而reflection用于访问字符串后备数组的速度几乎是大字符串的两倍。
String.charAt(n)
reflection
尝试了 9 种不同的优化技术。
所有字符串内容都是随机的
测试是针对从 0、1、2、4、8、16 等开始的 2 倍数的字符串大小进行的。
每个字符串大小进行 1,000 次测试
每次测试都会随机排列。换句话说,每次测试都是以随机顺序完成的,超过 1000 次。
整个测试套件向前和向后完成,以显示 JVM 预热对优化和时间的影响。
整个套件完成两次,一次在-client模式下,另一次在模式-server下。
-client
-server
对于 长度为 1 到 256 个字符的 字符串,调用string.charAt(i)胜出,平均每秒处理 1340 万到 5.88 亿个字符。
string.charAt(i)
此外,它总体上快 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); }
在我的 AMD 64 机器上的 64 位 Java 机器上,在服务器模式下的 32 个字符长度的字符串后,字段访问开始获胜。直到客户端模式下的 512 个字符长度才出现这种情况。
另外值得注意的是,我认为,当我在服务器模式下运行 JDK 8(32 位构建)时,大字符串和小字符串的整体性能都慢了 7%。这是 JDK 8 早期版本的 build 121 Dec 2013。所以,就目前而言,32 位服务器模式似乎比 32 位客户端模式慢。
话虽如此……似乎唯一值得调用的服务器模式是在 64 位机器上。否则它实际上会影响性能。
对于在-server modeAMD64 上运行的 32 位构建,我可以这样说:
-server mode
还值得一提的是,String.chars()(Stream 和并行版本)是个败笔。比任何其他方式都慢。StreamsAPI 是一种执行一般字符串操作的相当慢的方法。
Streams
Java String 可以具有接受优化方法的谓词,例如 contains(predicate)、forEach(consumer)、forEachWithIndex(consumer)。因此,无需用户知道长度或重复调用 String 方法,这些可以帮助beep-beep beep加速解析库。
beep-beep beep
继续做梦:)
快乐的弦乐!
~SH
“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; }
注意:在我的 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
注意:这是在 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(""); } }