Java中提高字符串拼接性能的方法

8

可能是重复问题:
Java字符串连接

如何提高这段代码的性能:

public static String concatStrings(Vector strings) {
    String returnValue = "";

    Iterator iter = strings.iterator();
    while( iter.hasNext() ) {
        returnValue += (String)iter.next();
    }

    return returnValue;
}

2
这是作业吗?从本质上讲,这没有什么问题,只需要标记一下即可。 - Dean Harding
https://dev59.com/JnVD5IYBdhLWcg3wOo9h - Ray Tayek
这似乎不是一个典型的作业问题,特别是涉及到性能方面。学生们通常对此并不意识到或者没有比较材料 ;) - BalusC
不要使用原始类型,而且你可能不需要Vector的同步。 - polygenelubricants
与未来的维护性能相关 - 您的方法可以接受一个 Iterable<String> - Carl
8个回答

15

您可以考虑使用StringBuilder,而不是对个别字符串使用 +=。在Java中,字符串是不可变的,这意味着一旦您创建了一个字符串对象,就无法修改它。在循环中对字符串使用 += 将导致创建许多不同的字符串实例,可能会导致性能问题。 StringBuilder可以连接字符串而无需创建新实例,这取决于具体情况,可能会节省一些时间。


1
+= 隐含地每次创建一个新的字符串。 - BalusC
你能把你的解释用代码表达出来吗? - Rachel
在循环之前创建 StringBuilder,在循环内调用 append() 方法,在循环结束后使用 toString() 获取结果。 - BalusC
我无法将其放入代码中,但这很容易。只需创建一个新的 StringBuilder,并在循环中使用 "append" 方法将新字符串添加到缓冲区中。完成后,只需调用 stringBuilder.toString() 来获取最终结果。 - Andy White

8
public static String concatStrings(List<String> strings) {
    StringBuilder sb = new StringBuilder();
    for (String s : strings) {
       sb.append(s);
    }    
    return sb.toString();
}

一些注意事项:

  • 在循环中构建字符串时,请使用StringBuilder
    • +用于简单的连接,但在增量构建时非常糟糕
  • 尽可能使用for-each以提高可读性
  • java.util.Vector是同步的;如果您不需要这个(昂贵的)功能,请使用ArrayList

不要使用原始类型

  • JLS 4.8 Raw Types

    只有为了兼容旧代码而允许使用原始类型。在引入泛型后编写的代码中强烈不建议使用原始类型。将来的Java编程语言版本可能禁止使用原始类型。

  • Effective Java第二版:第23条:不要在新代码中使用原始类型

    如果您使用原始类型,则会失去泛型带来的所有安全性和表现力优势。

另请参阅


1
请参见https://dev59.com/m3E85IYBdhLWcg3wdDIM - polygenelubricants

6

正如其他答案所建议的那样,使用StringBuilder可能是更好的选择。

问题中给出的代码实际上将被编译(使用Sun的javac)成以下内容:

public static String concatStrings(Vector strings) {
    String returnValue = "";

    Iterator iter = strings.iterator();
    while( iter.hasNext() ) {
        String str = (String)iter.next();

        StringBuilder sb = new StringBuilder(returnValue);
        sb.append(str);

        returnValue = sb.toString();
    }

    return returnValue;
}

编译器将使用StringBuilder来替换+=字符串拼接。然而,编译器可能会重写循环内的代码,因此在每次迭代中都会创建一个新的StringBuilder实例,这不太友好于性能。
因此,在这种情况下,最好自己在循环外部创建StringBuilder,并执行手动字符串拼接。
public static String concatStrings(Vector strings) {
    StringBuidler returnValueBuilder;

    Iterator iter = strings.iterator();
    while( iter.hasNext() ) {
        returnValueBuilder.append((String)iter.next());
    }

    return returnValueBuilder.toString();
}

在某些情况下,编译器会优化连接操作,即'+'并不总是那么糟糕,这是一个好处。然而,在像问题中提出的情况下,开销不在于创建新的StringBuilder实例(对象分配通常非常快),而在于在返回新的String之前将StringBuilder缓冲区复制到String中(String保证不可变性,因此它们无法重用相同的缓冲区)。 - CurtainDog
@CurtainDog - 如果我没记错的话,StringBuilder.toString() 在创建结果 String 时巧妙地避免了复制字符数组。看一下代码吧。 - Stephen C
@Stephen C:这绝对不是最新版本的情况。通常,Java标准库非常小心地避免任何可能导致String意外变异的情况。请参见http://google.com/codesearch/p?hl=en#gbgUBv1WUj4/src/share/classes/java/lang/StringBuilder.java&q=package:jdk%20file:StringBuilder.java%20toString&sa=N&cd=1&ct=rc。 - David
@David - 我今天学到了新东西!显然这个更改发生在1.4.x和1.5之间...http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6219959 - Stephen C
@Stephen C - 谢谢,你让我感觉很年轻... 我所有严肃的Java编码都必须在1.5之后进行。当然,我发现我的最初评论是不准确的,应该是“不能重用”改为“发现重用有问题”。 - CurtainDog

4
private static final int AVERAGE_STRING_LENGTH = 10;  // Using 10 is arbitrary

public static final String concatStrings(final Collection<String> strings) {
    if (strings == null)   return null;

    final int size = strings.size();
    if (size == 0)         return "";
    if (size == 1)         return strings.get(0);

    final StringBuilder returnValue =
        new StringBuilder(AVERAGE_STRING_LENGTH * size);

    for (String s : strings) {
        returnValue.append(s);
    }

    return returnValue.toString();
}

也许有点过度,这里是我能想到的concatStrings()的每个优化 - 如上所示 - 其中一些可能不适用于您的环境:
  • 使用StringBuilder - 对于这些连续的连接,它的效率要高得多
  • 使用StringBuilder(int capacity)来指定可能需要的容量,如果有任何预测方式(使用上面的平均大小,但其他方法可能更方便)
  • 使用Collection参数类型,以允许使用比Vector更高效的数据结构,后者是同步的 - 加上调用者具有更大的灵活性(例如,无需将Set<String>复制到Vector<String>中才能调用此方法)
  • 硬编码简单情况,如果它们很可能出现(例如,上面的null,大小为0和大小为1的情况)
  • 使用final来促进JIT内联和优化
  • 缓存strings的大小,如果它被多次使用。 (例如,在上面的代码中使用了3次。)

最后,如果这个操作在大量字符串上经常执行,请查看Java绳索


1

除了使用ArrayList和StringBuilder,让我们考虑一下这个。

在现代计算机科学范式中,空间几乎总是可以用时间来换取(也许这是一个主观的陈述)。对于给定的情况,使用以下代码会额外使用O(N)的空间,其中N =字符串数量(用于保存list.toArray()的新缓冲区)。这比至少使用Iterator要好(打开AbstractList.iterator())。重要的是,时间复杂度显着提高,通过在一次迭代中同时计算两个字符串的连接,从而将迭代次数减半!这有点像使用动态规划方法(记住,使用动态规划计算斐波那契数列)!!

    StringBuilder sb = new StringBuilder();
    Object[] o = list.toArray();
    //For even no of Strings
    if(o.length % 2 == 0){
        concatFaster(sb, o);
    } else {
        //For odd no of Strings
        concatFaster(sb, o);
        sb.append(o[o.length-1]); // For the odd index
    }

    public static void concatFaster(StringBuilder sb, Object[] o) {
    for (int i = 0; i < o.length - 1; i+=2) {
        sb.append(o[i]).append(o[i+1]);
    }
}

1
每次调用 += 时,你都会创建一个新的字符串。例如:
String theString = "1"; //Makes an immutable String object "1"
theString +="2"; //Makes a new immutable String object "12"
theString +="3"; //makes a new immutable String object "123"

使用字符串构建器可以避免这个问题。
StringBuilder sb = new StringBuilder("1"); //Makes a StringBuilder object holding 1
sb.append("2"); //The same StringBuilder object now has "12" in it.
sb.append("3"); //The same StringBuidler object now has "123" in it. 
String theString = sb.toString(); //Creates a new String object with "123" in it 

请注意第一个示例中我们创建了所有这些中间字符串,而在第二个示例中我们只创建了StringBuilder和最终的String(在两个示例中,当我们将它们用作参数时,我们都创建了“1”“2”和“3”)。您可以看到第一个示例中创建的对象较少,如果您需要大量追加字符串,那么您可以想象它会如何累积!

1

如果你想让这个过程更快,你可以重构代码,使用ArrayList代替Vector。ArrayList不是线程安全的,所以它比Vector稍微快一些(取决于情况,可能没有差别,也可能有5%的差别)。


1
除了使用 StringBuilder 之外,您还可以预先遍历字符串列表并计算 StringBuilder 所需的确切大小。然后将此值传递到 StringBuilder 构造函数中。请注意,这将属于过早优化的范畴,但您确实要求性能...(您应该查看增长 StringBuilder/StringBuffer 缓冲区的代码,这很有教育意义)

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接