logo标签列表

Java charAt() 还是 substring()？哪个更快？

javastringperformancecharactersubstring
13
我想遍历字符串中的每个字符，并将字符串的每个字符作为字符串传递给另一个函数。
String s = "abcdefg";
for(int i = 0; i < s.length(); i++){
    newFunction(s.substring(i, i+1));}

或者

String s = "abcdefg";
for(int i = 0; i < s.length(); i++){
    newFunction(Character.toString(s.charAt(i)));}

最终结果需要是一个字符串。
那么有什么想法可以使其更快或更有效率吗？
6个回答
16

像往常一样：这并不重要，但如果你坚持花时间进行微调优，或者真的喜欢为你非常特殊的使用情况进行优化，请尝试这个：

import org.junit.Assert;
import org.junit.Test;

public class StringCharTest {

    // Times:
    // 1. Initialization of "s" outside the loop
    // 2. Init of "s" inside the loop
    // 3. newFunction() actually checks the string length,
    // so the function will not be optimized away by the hotstop compiler

    @Test
    // Fastest: 237ms / 562ms / 2434ms
    public void testCacheStrings() throws Exception {
        // Cache all possible Char strings
        String[] char2string = new String[Character.MAX_VALUE];
        for (char i = Character.MIN_VALUE; i < Character.MAX_VALUE; i++) {
            char2string[i] = Character.toString(i);
        }

        for (int x = 0; x < 10000000; x++) {
            char[] s = "abcdefg".toCharArray();
            for (int i = 0; i < s.length; i++) {
                newFunction(char2string[s[i]]);
            }
        }
    }

    @Test
    // Fast: 1687ms / 1725ms / 3382ms
    public void testCharToString() throws Exception {
        for (int x = 0; x < 10000000; x++) {
            String s = "abcdefg";
            for (int i = 0; i < s.length(); i++) {
                // Fast: Creates new String objects, but does not copy an array
                newFunction(Character.toString(s.charAt(i)));
            }
        }
    }

    @Test
    // Very fast: 1331 ms/ 1414ms / 3190ms
    public void testSubstring() throws Exception {
        for (int x = 0; x < 10000000; x++) {
            String s = "abcdefg";
            for (int i = 0; i < s.length(); i++) {
                // The fastest! Reuses the internal char array
                newFunction(s.substring(i, i + 1));
            }
        }
    }

    @Test
    // Slowest: 2525ms / 2961ms / 4703ms
    public void testNewString() throws Exception {
        char[] value = new char[1];
        for (int x = 0; x < 10000000; x++) {
            char[] s = "abcdefg".toCharArray();
            for (int i = 0; i < s.length; i++) {
                value[0] = s[i];
                // Slow! Copies the array
                newFunction(new String(value));
            }
        }
    }

    private void newFunction(String string) {
        // Do something with the one-character string
        Assert.assertEquals(1, string.length());
    }

}
由于这将传递一个字符串，因此您需要在第一个测试中稍微更改一下测试。{char[] s = "abcdefg".toCharArray();} 应该放在循环内部，或者更好的做法是（为了防止JVM进行聪明的优化，将整个循环和.toCharArray()放在单独的函数中）。重要的是要测量所有初始开销以及循环成本。特别是由于性能实际上可能根据字符串长度从一个状态转变为另一个状态。因此，测试不同长度的字符串也很重要。 - MatBailie
将“s”移至循环内，并添加assert()以防止JVM优化newFunction()。当然，现在速度较慢，但相对测量仍然相同。我的观点仅仅是如果问题确切知道，就有优化的可能性。重点不是更改用于某个操作的函数，而是从更高层次上看待操作以获得改进，例如通过缓存。 - mhaller
1
请注意，自Java 7u6以来，substring方法变成了复制。请参阅https://dev59.com/SGYq5IYBdhLWcg3w0j8T。 - Vadzim
14
答案是：那并不重要。
对你的代码进行分析。这是否是瓶颈所在？
以什么方式进行配置文件？是为了内存使用情况吗？ - Peter Mortensen
4

新的函数newFunction是否真的需要使用String类型？如果您可以让newFunction接受一个char类型的参数并像这样调用它，那会更好：

newFunction(s.charAt(i));

那样，您可以避免创建临时的String对象。
回答您的问题：很难说哪个更有效率。在这两个例子中，都需要创建一个只包含一个字符的String对象。哪个更有效取决于您特定的Java实现如何实现String.substring(...)和Character.toString(...)。唯一找出答案的方法是通过性能分析器运行程序，并查看哪个版本使用了更多的CPU和/或内存。通常情况下，您不应该担心这样的微小优化 - 只有在发现这是性能和/或内存问题的原因时，才花时间处理它。
newFunction 真的需要接收一个字符串。除了单个字符，newFunction 也可以处理更长的字符串，并且以相同的方式处理它们。我不想重载 newFunction 来接收一个字符，因为在这两种情况下它都执行相同的操作。 - estacado
1
我完全同意在开发过程中应避免微观优化，除非有必要。我也认为，作为一种学习练习，了解内存分配和其他“隐藏行为”非常重要。个人厌倦了天真的程序员们相信短代码=性能好，而不经意地使用高度低效的算法。不学习这些的人是懒惰的，沉迷于这些的人则会变得很慢。需要适当平衡，在我看来 :) - MatBailie
@estacado：如果性能是你的驱动力（正如你的帖子所暗示的），那么就要在正确的地方进行优化。重载new函数以避免字符串开销可能是一个明智的选择，这取决于基于[char]的版本看起来像什么。将代码弯曲到函数周围可能更耗时、效果更差、难以维护。 - MatBailie
2
你发布的两个片段，我不想说哪个更好。我同意Will的看法，这几乎肯定与你代码的整体性能无关，如果不是这样，你可以进行更改，并确定哪种方法在你的数据上、在你的JVM和硬件上运行最快。
话虽如此，如果你先将String转换为char数组，然后对数组进行迭代，第二个片段可能会更好。这样做只需要一次执行String开销（转换为数组），而不是每次调用都需要。此外，你可以直接将数组传递给带有一些索引的String构造函数，这比单独取出一个字符（然后将其转换为一个字符数组）更有效率。
String s = "abcdefg";
char[] chars = s.toCharArray();
for(int i = 0; i < chars.length; i++) {
    newFunction(String.valueOf(chars, i, 1));
}

然而，为了加强我的第一点，当你查看每次调用String.charAt()时实际上避免的内容时，它包括两个边界检查、一个（惰性）布尔值OR和一个加法。这不会有任何明显的差别。在String构造函数中的区别也是如此。

本质上，从性能角度来看，这两种习惯用法都很好（都不会立即表现出低效），因此除非分析工具显示这占用了应用程序运行时间的大部分，否则不应再花费更多时间在它们上面。即使在那种情况下，通过重构此区域的支持代码（例如，让newFunction接受整个字符串本身）几乎肯定可以获得更多的性能提升；java.lang.String 在这一点上已经被优化得非常好了。

当前的JVM中，substring实际上使用原始字符数组作为后备存储器，而您正在初始化一个副本。因此，我的直觉认为substring实际上会更快，因为memcpy可能会更昂贵（取决于字符串的大小，越大越好）。 - wds
0
我会先使用 String.toCharArray() 获取源字符串的底层 char[]，然后继续调用 newFunction。
但我同意 Jesper 的观点，最好只处理字符并避免使用所有的字符串函数...
据我所知，String.charAt(i)执行该查找。将字符串复制到新数组中(这是我理解的String.toCharArray()所做的)，会引入一个新的不同开销。重复传递字符串引用到charAt()比先转换为本机数组慢吗?我怀疑这取决于字符串的长度... - MatBailie
总是有取舍的 :) 只有原帖作者才能真正判断哪种方法更有效。 - Cadet Pirx
0

Leetcode似乎更喜欢使用子字符串选项这里。

这是我解决该问题的方法：

class Solution {
public int strStr(String haystack, String needle) {
    if(needle.length() == 0) {
        return 0;
    }

    if(haystack.length() == 0) {
        return -1;
    }

    for(int i=0; i<=haystack.length()-needle.length(); i++) {
        int count = 0;
        for(int j=0; j<needle.length(); j++) {
            if(haystack.charAt(i+j) == needle.charAt(j)) {
                count++;
            }
        }
        if(count == needle.length()) {
            return i;
        }
    }
    return -1;
}

}

这是他们提供的最佳解决方案：

class Solution {
public int strStr(String haystack, String needle) {
    int length;
    int n=needle.length();
    int h=haystack.length();
    if(n==0)
        return 0;
    // if(n==h)
    //     length = h;
    // else
        length = h-n;
    if(h==n && haystack.charAt(0)!=needle.charAt(0))
            return -1;
    for(int i=0; i<=length; i++){
        if(haystack.substring(i, i+needle.length()).equals(needle))
            return i;
    }
    return -1;
}

}

老实说，我想不出为什么这很重要。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接