9

I'm having performance issues. Does anyone have a faster/better solution for doing the following:

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

I know concat and stringbuilder are faster, but i don't see how i can use these methods. Because of the following line of code:

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

Thanks in advance!

Raedwald
  • 46,613
  • 43
  • 151
  • 237
  • 2
    what do you want to achieve? what's your expected result? – Andrew Tobilko Dec 05 '16 at 01:04
  • 2
    @AndrewTobilko He wants a faster way to do this for performance. – RaminS Dec 05 '16 at 01:05
  • 2
    Have you tried inserting into a StringBuilder? https://docs.oracle.com/javase/7/docs/api/java/lang/StringBuilder.html#insert(int,%20java.lang.String) Or reverse the `propositions` before iterating, would that allow you to append only? – Robert Dec 05 '16 at 01:05
  • In general, when working with strings, it is much better to use a `StringBuilder`, and after getting your desired string use the method `toString()` – lmiguelvargasf Dec 05 '16 at 01:06
  • 2
    Can `proposition.length()` be zero? Looping backwards might make it easier to use a `StringBuilder`. – Bubletan Dec 05 '16 at 01:08
  • 4
    @lmiguelvargasf: The upvoters might have upvoted because converting this code to use more efficient forms of string building isn't actually trivial, due to the mixed prepending and appending. – user2357112 Dec 05 '16 at 01:14
  • Related to, but not a duplicate of, http://stackoverflow.com/questions/1532461/stringbuilder-vs-string-concatenation-in-tostring-in-java – Raedwald Dec 11 '16 at 08:51

3 Answers3

9

So from what I can tell there are 3 problems here:

  1. Values are primarily prepended to the string.
  2. For each value a character is appended.
  3. If only one value is present, nothing should be appended or prepended.
  4. With 2 or more items, the 0th item is handled differently:

0:""

1:"A"

2:"|(B,A)"

3:"|(C,|(B,A))"

It can be made quicker by making a few changes:

  1. Reverse the algorithm, this means the majority of the work involves appending, allowing you to use StringBuilders.
  2. Count the number of closing )'s and append those after the loop is finished.
  3. Special case for 0 or 1 items in the list.

With those changes the algorithm should be able to use a StringBuilder and be a lot quicker.

Attempt at an algorithm:

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();
}

I believe this should produce the correct results, but it should give the right idea.

Community
  • 1
  • 1
Kiskae
  • 24,655
  • 2
  • 77
  • 74
  • 1
    He doesn't need to reverse the algorithm. `StringBuilder.insert()` exists. – user207421 Dec 05 '16 at 01:17
  • 1
    @EJP: But using `insert` defeats the point, because you wouldn't have done anything about the quadratic runtime. – user2357112 Dec 05 '16 at 01:21
  • 3
    @EJP insert would require moving all the previous input, it would probably involve as much shuffling of memory as the original code. – Kiskae Dec 05 '16 at 01:22
  • 1
    insert may need to move input, but would still be faster than the original which creates all these strings – Robert Dec 05 '16 at 01:27
  • @Robert However both moving memory (insert) and allocating memory (naive) are situations you want to avoid within a loop. Hence why I suggested a reverse iteration because that turns it into a problem the stringbuilder is designed for. – Kiskae Dec 05 '16 at 01:29
  • 3
    Another option is to use an `ArrayDeque`, which is a circular structure that inserts at the start just as fast as the end. At the end you could join all the strings. – 4castle Dec 05 '16 at 01:34
  • I'm going to try this method, thanks for responding all. –  Dec 05 '16 at 07:38
7

The problem is that you're prepending and appending to the string as you go. String and StringBuilder dont handle this well (and give quadratic performance). But you can use a dequeue which supports insertion at start and end to store all the pieces. Then finally you can join the bits in the dequeue.

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
  • 70,661
  • 7
  • 134
  • 187
2

Assuming this is an array of propositions, you could first sum the length of the String(s) in the array. Add 4 for your additional characters, and subtract 4 because you don't use those separators on the first element. That should be the perfect size for your output (this is optional, because StringBuilder is dynamically sized). Next, construct a StringBuilder. Add the first element. All subsequent elements follow the same pattern, so the loop is simplified with a traditional for. Something like,

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
  • 198,278
  • 20
  • 158
  • 249