Java - Most Efficent way to traverse a String

Question

Possible Duplicate:
What is the easiest/best/most correct way to iterate through the characters of a string in Java?

What I'm considering is time and efficiency. With those in mind, which method (among the ones below or others not mentioned) is the most efficient way to go through each character of a string?

String str = "Foo Bar";
for(int i=0;i<str.length();i++)
   System.out.println(str.charAt(i)); // access the character using .charAt()

for(char letter: str.toCharArray)
   System.out.println(letter);       // use for-each loop with the char array.

Again, there might be a better way to do this, but I also am curious if there is are major time/resources differences between the two above.

strictly speaking, the String method `.charAt()` is O(1) and will presumably be faster than redundantly converting the string to a character array (as strings are already backed by char arrays) — Alex Lynch, Nov 09 '12 at 00:59

Óscar López · Accepted Answer · 2019-02-20T18:38:52.813

11

The first version is more efficient. The second version of the code will end up being slower and use more memory because of the cost of creating and filling the new char[] with toCharArray().

For long strings (more than 512 chars, approximately), the fastest way to inspect the string is to use reflection to access the backing char[] of the String (but only works up to Java 8, because of Compact Strings):

String data = "a really long string";
Field field = String.class.getDeclaredField("value");
field.setAccessible(true);
char[] chars = (char[]) field.get(data);

for (int i = 0, n = chars.length; i < n; i++)
    System.out.println(chars[i]);

By using the above approach, we were able to avoid entirely the need to create a new char[] and also to pay the cost of an extra method call to charAt() in each iteration.

Take a look at this post, the answer contains detailed benchmarks. The best of both worlds, but anyway it was a hack and it no longer works.

edited Feb 20 '19 at 18:38

answered Nov 09 '12 at 01:03

Óscar López

232,561
37
312
386

Note the missing `field.setAccessible(true);` – Viliam Dec 01 '15 at 23:50
@Viliam it's fixed now, thanks! – Óscar López Dec 02 '15 at 01:30
1

This code is broke when running on OpenJDK, since at least Java 9, when [Compact Strings](https://openjdk.java.net/jeps/254) was implemented. The `value` field in `String` is now a byte array. – Lii Feb 20 '19 at 18:29

arshajii · Answer 2 · 2012-11-09T01:07:12.697

The first method is faster since toCharArray has to copy over the internal character array of the string before it returns anything, whereas charAt accesses the elements from this internal array directly, making it more efficient.

In other words, charAt is O(1) and toCharArray is O(n). Now, both of those methods of traversing the string will be O(n), but the second will have a higher 'leading coefficient' than the first.

You can see all this if you look at the source code for the String class.

Java - Most Efficent way to traverse a String

2 Answers2