[解決済み] 文字列内のすべての文字を反復処理する最速の方法
2022-04-20 21:34:14
質問
Java で、String のすべての文字を反復処理する最も速い方法は何でしょう。
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];
}
EDIT :
私が知りたいのは、繰り返し
charAt
メソッドを1回だけ呼び出す場合のコストよりも小さくなったり大きくなったりします。
toCharArray
を実行し、反復処理中に配列に直接アクセスします。
JITのウォームアップ時間やJVMの起動時間などを考慮した上で、異なる文字列長に対する堅牢なベンチマークを提供できる人がいれば最高なのですが、単に2回の
System.currentTimeMillis()
.
解決方法は？
FIRST UPDATE: これを本番環境で試す前に（お勧めしませんが）、まずこれを読んでください。 http://www.javaspecialists.eu/archive/Issue237.html Java 9以降、Javaはデフォルトで文字列をbyte[]として格納するようになったため、説明したような解決策はもう機能しません。
SECOND UPDATE: 2016-10-25 現在、私の AMDx64 8core とソース 1.8 では、「charAt」を使ってもフィールドアクセスをしても差はありません。jvmは十分に最適化されており、'string.charAt(n)'の呼び出しはインラインで効率化されているようです。
第3の更新：2020-09-07現在、私のRyzen 1950-X 16コアとソース1.14では、「charAt1」はフィールドアクセスより9倍遅く、「charAt2」はフィールドアクセスより4倍遅くなりました。フィールドアクセスが明らかに勝者であることがわかります。なお、Java 9以上のバージョンでは、byte[]アクセスを使用する必要があります。
の長さに依存します。
String
検査中です。もし、質問文にあるように、それが
長い
文字列を検査する最速の方法は、リフレクションを使用して、バッキングの
char[]
文字列の
64 AMD Phenom II 4 core 955 @ 3.2 GHZ (クライアントモードとサーバーモードの両方) で、JDK 8 (win32 と win64) を使って、9種類の手法で完全にランダムなベンチマークを行ったところ (以下を参照!)、以下のようになりました。
String.charAt(n)
が最も速く、小さな文字列では
reflection
を使用して String バックアップ配列にアクセスすると、大きな文字列ではほぼ 2 倍の速度になります。
実験
-
9種類の最適化技術を試行。
-
文字列の内容はすべてランダム化される
-
0,1,2,4,8,16など、2の倍数で始まる文字列サイズに対してテストが行われます。
-
テストは1つの文字列サイズにつき1,000回行われます。
-
テストは毎回ランダムな順番でシャッフルされます。言い換えれば、テストは毎回、1000回以上、ランダムな順番で行われるのです。
-
テストスイート全体は、最適化と時間に対するJVMウォームアップの効果を示すために、前方および後方で実行されます。
-
スイート全体を2回実行し、1回は
-clientモードと、もう1つは-serverモードとなります。
結論
-クライアントモード(32ビット)
文字列の場合
1〜256文字の長さ
を呼び出すと
string.charAt(i)
は、1秒間に1340万文字から5億8800万文字の平均処理能力で勝利します。
また、このように全体的に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のバックアレイにアクセスするのが最も速いです。 このテクニックは、ほぼ2倍の速さです は、String.charAt(i) (178%高速)と同じです。この範囲での平均速度は、11億1100万文字/秒でした。
Fieldは先に取得しておき、ライブラリ内で異なる文字列に対して再利用する必要があります。興味深いことに、上記のコードとは異なり、Fieldアクセスでは、ループチェックで 'chars.length' を使用するよりも、ローカルの最終長変数を持つ方が9%高速になります。以下は、Fieldアクセスを最速に設定する方法である。
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);
}
サーバーモードに関する特別なコメント
私のAMD64マシンの64ビットJavaマシンで、サーバーモードで32文字の長さの文字列の後にフィールドアクセスが始まるのが勝ちです。クライアントモードでは512文字まで見られませんでした。
また、私が思うに、JDK 8 (32 ビットビルド) をサーバーモードで実行していたとき、大きな文字列と小さな文字列の両方で、全体のパフォーマンスが 7% 遅くなったことも特筆すべき点です。これは、JDK 8 early release のビルド 121 Dec 2013 での話です。ということで、今のところ、32ビットサーバーモードは32ビットクライアントモードより遅いようです。
とはいえ......起動する価値のあるサーバーモードは、64ビットマシンだけだと思われます。そうでなければ、かえってパフォーマンスを低下させることになります。
で実行する32ビットビルドの場合
-server mode
AMD64で、これだけは言える。
- String.charAt(i)が全体的に明らかに勝者です。しかし、8文字から512文字までのサイズでは、「新規」「再利用」「フィールド」の間で勝者が存在しました。
- クライアントモードではString.charAt(i)は45%高速化される
- クライアントモードで、大きな文字列のフィールドアクセスが2倍高速になりました。
また、String.chars() (Streamとその並列バージョン)はダメだと言っておく価値があります。他のどの方法よりも遅い。その
Streams
APIは、一般的な文字列操作を行うにはかなり遅い方法です。
ウィッシュリスト
Java Stringは、contains(述語), forEach(consumer), forEachWithIndex(consumer) などの述語を受け入れる最適化されたメソッドを持つことができるかもしれません。したがって、ユーザが長さを知ったり、Stringメソッドを繰り返し呼び出したりする必要なしに、これらは、解析ライブラリを助けることができます。
beep-beep beep
を高速化することができます。
夢を持ち続けてください :)
Happy Strings!
~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;
}
上記と同じですが、長さの最終的なローカル int を作成する代わりに String.length() を使用します。
int charAtMethod2(final String data) {
for (int i = 0; i < data.length(); i++) {
if (data.charAt(i) <= ' ') {
doThrow();
}
}
return data.length();
}
stream" -- 新しいJAVA-8文字列のIntStreamを使用し、それをチェックするためにpredicateを渡す。
int streamMethod(final String data, final IntPredicate predicate) {
if (data.chars().anyMatch(predicate)) {
doThrow();
}
return data.length();
}
streamPara" -- 上と同じですが、OH-LA-LA - GO PARALLEL!!!!
// 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();
}
フィールド1" -- FANCY! 文字列の内部にアクセスするためのフィールドを取得する 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);
}
}
フィールド2: -- 上記と同じですが、quot;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
MODE（前方・後方テストの組み合わせ）
注：私のAMD64マシンでは、Java 32bitの-clientモードとJava 64bitの-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
MODE（前方・後方テストの組み合わせ）
注：これはAMD64上でJava 32bitをサーバーモードで動作させた場合のテストです。Java 64bitのサーバーモードは、32文字サイズ以降に始まるFieldアクセスが勝利することを除いて、クライアントモードのJava 32bitと同じでした。
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 以前のバージョンでテストする場合は、2 つのストリーム・テストを削除してください)
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("");
}
}
関連
-
この行に複数のマーカーがある - HttpServletResponseが型エラーに解決できない
-
[解決済み] C#のStringとstringの違いは何ですか？
-
[解決済み] Java Mapの各エントリを効率的に反復処理するには？
-
[解決済み] なぜパスワードにはStringではなくchar[]が好まれるのですか？
-
[解決済み] 文字列の単語を反復処理するにはどうすればよいですか？
-
[解決済み] Java の配列を表示する最も簡単な方法は何ですか？
-
[解決済み] YAML の文字列を複数行に渡って分割するには？
-
[解決済み] C++でintをstringに変換する最も簡単な方法
-
[解決済み] 複数行の長い文字列を作成するためのPythonicな方法
-
[解決済み】JavaScriptで文字列の出現箇所をすべて置換する方法
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
スタイルシートとして解釈されるリソースが、MIMEタイプtext/htmlで転送される。
-
springboot project MIMEタイプ text/htmlで転送された静的ファイルを読み込む。
-
undefinedeclipse エラー。この行に複数のアノテーションが見つかりました: - 文字列を型解決に解決できない
-
Dateが型に解決できない問題を解決する
-
Enumとの組み合わせでswitchの使い方を一度覚えるために必要な定数式
-
java Mail send email smtp is not authenticated by TLS encryption solution.
-
Spring boot runs with Error creating bean with name 'entityManagerFactory' defined in class path resource
-
linux run jarfile Invalid or corrupt jarfile error.
-
[解決済み] Javaで文字列の文字を反復処理する最も簡単/最も良い/最も正しい方法は何ですか？
-
[解決済み] java -server" と "java -client "の本当の違い？