时间复杂度：google.common.base.Joiner vs 字符串连接

Question

我知道在循环中对字符串使用 += 需要 O(n^2) 时间，其中 n 是循环数。但是如果循环会运行最多20次。这会将时间复杂度更改为 O(1) 吗？例如，

List<String> strList = new ArrayList<>();
//some operations to add string to strList
for(String str : strList) appendStr += str + ",";

我知道 strList 的大小永远不会超过 20。而且 strList 中的每个字符串都将少于 20 个字符。如果这种情况下的字符串连接仍然具有 O(n^2) 时间复杂度，如果我希望我的算法具有更好的时间复杂度，那么使用 google.common.base.Joiner 会更好吗？

Answer 1

由于 JVM 运行时优化，不可能说 Guava 的 Joiner 会 100% 更有效地工作，在某些情况下，普通连接会工作得更快。

也就是说，更喜欢 Joiner（或在幕后利用 StringBuilder 的类似构造）来连接集合，因为它的可读性和性能通常更好。

Answer 2

从非常迂腐的意义上讲，是的，如果您的输入被限制在固定大小，那么对该输入执行的任何操作实际上都是恒定时间的，但是这与此类分析的目的背道而驰。如果您对其时间复杂度感兴趣，而不是它对单个特定输入的行为方式，请检查您的代码在 asymptotic 情况下的行为方式。

即使您将列表的大小限制为 20 个元素，您仍然需要 O(n^2) "work" 来连接元素。与使用 StringBuilder 或更高级别的工具（例如 Joiner 相比，这些工具设计比重复连接更有效。 Joiner 只需执行 O(n) "work" 即可构造您需要的字符串。

简而言之，从来没有这样做的理由：

 for(String str : strList) appendStr += str + ",";

而不是：

Joiner.on(',').join(strList);

Answer 3

我已经完全删除了我之前的答案，因为我的测试存在严重缺陷。以下是一些更新的结果和代码：

@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5, time = 2, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 2, timeUnit = TimeUnit.SECONDS)
public class DifferentConcats {

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder().include(DifferentConcats.class.getSimpleName())
                                          .verbosity(VerboseMode.EXTRA)
                                          .build();
        new Runner(opt).run();
    }

    @Param(value = {"1", "10", "100", "1000", "10000"})
    private int howMany;

    private static final Joiner JOINER = Joiner.on(",");

    @Benchmark
    @Fork(3)
    public String guavaJoiner() {

        List<String> list = new ArrayList<>(howMany);

        for (int i = 0; i < howMany; ++i) {
            list.add("" + i);
        }
        return JOINER.join(list);
    }

    @Benchmark
    @Fork(3)
    public String java9Default() {

        List<String> list = new ArrayList<>(howMany);

        for (int i = 0; i < howMany; ++i) {
            list.add("" + i);
        }

        String result = "";

        for (String s : list) {
            result += s;
        }

        return result;
    }
}

结果：

Benchmark                      (howMany)  Mode  Cnt         Score         Error  Units
DifferentConcats.guavaJoiner           1  avgt   15        62.582 ±       0.756  ns/op
DifferentConcats.java9Default          1  avgt   15        47.209 ±       0.708  ns/op

DifferentConcats.guavaJoiner          10  avgt   15       430.310 ±       4.690  ns/op
DifferentConcats.java9Default         10  avgt   15       377.203 ±       4.071  ns/op

DifferentConcats.guavaJoiner         100  avgt   15      4115.152 ±      38.505  ns/op
DifferentConcats.java9Default        100  avgt   15      4659.620 ±     182.488  ns/op

DifferentConcats.guavaJoiner        1000  avgt   15     43917.367 ±     360.601  ns/op
DifferentConcats.java9Default       1000  avgt   15    362959.115 ±    6604.020  ns/op

DifferentConcats.guavaJoiner       10000  avgt   15    435289.491 ±    5391.097  ns/op
DifferentConcats.java9Default      10000  avgt   15  47132980.336 ± 1152934.498  ns/op

TL;DR

另一个被接受的答案是绝对正确的。

Answer 4

我发现了一篇很棒的博客post 详细解释了每种串联技术的性能java-string-concatenation-which-way-is-best

注意：串联性能因编号而异。要连接的字符串。例如 - 要连接 1-10 个字符串，这些技术最有效 - StringBuilder、StringBuffer 和 Plus Operator。连接 100 个字符串 - Guava Joiner，apache 的 stringsUtils 库也很好用。

请浏览以上博客。真的很好的诠释了各种concatenation Techniques的性能。

谢谢。

时间复杂度：google.common.base.Joiner vs 字符串连接

time complexity: google.common.base.Joiner vs String concatenation

java

complexity-theory

time-complexity

guava