性能（JAVA）- 在循环中使用字符串连接并在前后添加内容

Question

我遇到了性能问题。有没有更快/更好的解决方案来完成以下操作：

    String main = "";
    for (String proposition : propositions) {
        if (main.length() == 0) {
            main = proposition;
        } else {
            main = "|(" + proposition + "," + main + ")";
        }
    }

我知道concat和stringbuilder更快，但我不知道如何使用这些方法。因为下面这行代码：

我知道concat和stringbuilder更快，但我不知道如何使用这些方法。因为下面这行代码：

main = "|(" + proposition + "," + main + ")";

提前感谢您！

- user7138304

---

你想要实现什么？你期望的结果是什么？ - Andrew Tobilko

@AndrewTobilko 他希望有更快的方法来提高性能。 - RaminS

你尝试过使用 StringBuilder 插入吗？https://docs.oracle.com/javase/7/docs/api/java/lang/StringBuilder.html#insert(int,%20java.lang.String) 或者在迭代之前反转 propositions，这样能让你只进行附加操作吗？ - Robert

proposition.length() 可以为零吗？倒序循环可能会更容易使用 StringBuilder。 - Bubletan

点赞者可能会点赞是因为将此代码转换为使用更有效的字符串构建形式并不容易，由于包含了混合的前置和后置操作。 - user2357112

Answer 1

据我所知，这里有三个问题：

1. 值主要是在字符串前面添加的。
2. 对于每个值，都会附加一个字符。
3. 如果只有一个值存在，则不应附加或前置任何内容。
4. 对于两个或更多项，第0项的处理方式不同：

0：“”

1：“A”

2：“|(B,A)”

3：“|(C,|(B,A))”

通过进行以下几个更改可以使其更快：

1. 反转算法，这意味着大部分工作涉及附加，因此您可以使用StringBuilder。
2. 计算关闭的括号数量，并在循环完成后附加这些括号。
3. 特殊情况下列表中只有0或1项。

通过这些更改，该算法应该能够使用StringBuilder并且速度更快。

以下是尝试的算法：

int length = propositions.size();
if (length == 0) {
    main = "";
} else {
    StringBuilder sb = new StringBuilder();
    int nestingDepth = 0;
    // Reverse loop, ignoring 0th element due to special case
    for (int i = length - 1; i > 0; i--) {
        sb.append("|(").append(propositions.get(i)).append(',');
        nestingDepth++;
    }
    // Append last element due to special casing
    sb.append(propositions.get(0));
    for (int i = 0; i < nestingDepth; i++) {
        sb.append(')');
    }

    main = sb.toString();
}

我认为这应该能够产生正确的结果，但它应该能够给出正确的想法。

- Kiskae

---

他不需要反转算法。StringBuilder.insert()已经存在。 - user207421

@EJP：但使用insert是没有意义的，因为您没有解决二次运行时间的问题。 - user2357112

@EJP插入需要移动所有先前的输入，这可能涉及与原始代码一样多的内存重排。 - Kiskae

插入操作可能需要移动输入，但仍然比创建所有这些字符串的原始操作更快。 - Robert

另一个选择是使用ArrayDeque，它是一种环形结构，在开头插入字符串的速度与在末尾相同。最后，您可以将所有字符串连接起来。 - 4castle

Answer 2

问题在于您在进行操作时不断地向字符串前后添加内容。这种方式会导致String和StringBuilder的表现不佳（并且会导致二次时间复杂度）。但是，您可以使用双端队列来存储所有的片段，因为它支持在开头和结尾插入。最后，您可以将队列中的所有元素连接起来。

ArrayDeque bits = new ArrayDeque();
for (String proposition : propositions) {
    if (bits.size() == 0) {
        bits.push(proposition);
    } else {
        // Add prefix
        main.offerFirst("|(" + proposition + "," );
        // Add suffix
        main.push(")");
    }
}
StringBuilder sb = new StringBuilder();
for( String s : bits) {
   sb.append(s);
}
main = sb.toString();

- Michael Anderson

---

我将尝试这种方法，感谢您的回复。 - user7138304

Answer 3

假设这是一个propositions数组，您可以首先将数组中String的长度相加。加上4个附加字符，减去4个分隔符，因为第一个元素不使用这些分隔符。这应该是输出的完美大小（这是可选项，因为StringBuilder是动态大小的）。接下来，构造一个StringBuilder。添加第一个元素。所有后续元素都遵循相同的模式，因此循环使用传统的for更简化。类似如下：

int len = Stream.of(propositions).mapToInt(s -> s.length() + 4).sum() - 4;
StringBuilder sb = new StringBuilder(len); // <-- len is optional
sb.append(propositions[0]);
for (int i = 1; i < propositions.length; i++) {
    sb.insert(0, ",").insert(0, propositions[i]).insert(0, "|(").append(")");
}
System.out.println(sb);

- Elliott Frisch

---

我将尝试这种方法，感谢您的回复。 - user7138304