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

Question

I know that using += on strings in loops takes O(n^2) time where n is the number of loops. But if the loop will run at most 20 times. Will that change the time complexity to O(1) ? For example,

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

I know that the size of strList will never exceed 20. Also each string in strList will have less than 20 characters. If the string concatenation in this case still has O(n^2) time complexity, would it better be to use google.common.base.Joiner if I want my algorithm to have a better time complexity?

Answer 1

In a very pedantic sense yes, if your input is capped at a fixed size than any operations performed on that input are effectively constant-time, however that misses the purpose of such analysis. Examine how your code behaves in the asymptotic case if you are interested in its time complexity, not how it behaves for a single specific input.

Even if you cap the size of the list to 20 elements, you're still doing O(n^2) "work" in order to concatenate the elements. Contrast that with using a StringBuilder or higher-level tool such as Joiner which are designed to be more efficient than repeated concatenations. Joiner only has to do O(n) "work" in order to construct the string you need.

Put simply, there's never a reason to do:

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

instead of:

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

Answer 2

I found a great blog post explaining the performance of each Concatenation technique in details java-string-concatenation-which-way-is-best

Note : Concatenation performance varies with no. of strings to concatenate. For example - to concatenate 1-10 strings, these techniques works best - StringBuilder, StringBuffer and Plus Operator. And to concatenate 100s of strings - Guava Joiner, apache's stringsUtils library also works great.

Please go through the above blog. It really explains performance of various concatenation Techniques very well.

Thanks.

Answer 3

I have completely erased my previous answer, because the tests that I had were seriously flawed. Here are some updated results and code:

@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;
    }
}

And the results:

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

The other, accepted answer, is absolutely correct.

Answer 4

It is impossible to state that the Guava's Joiner would work more effectively with 100% assurance due to JVM runtime optimizations, under certain circumstances a plain concatenation would work faster.

That's said, prefer Joiner (or similar constructs that utilizes a StringBuilder under the hood) for concatenating collections since it's readability and performance, in general, are better.