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!

Improve this question
7
  • 2
    what do you want to achieve? what's your expected result? Commented Dec 5, 2016 at 1:04
  • 2
    @AndrewTobilko He wants a faster way to do this for performance. Commented Dec 5, 2016 at 1:05
  • 2
    Have you tried inserting into a StringBuilder? docs.oracle.com/javase/7/docs/api/java/lang/… Or reverse the propositions before iterating, would that allow you to append only? Commented Dec 5, 2016 at 1:05
  • 2
    Can proposition.length() be zero? Looping backwards might make it easier to use a StringBuilder. Commented Dec 5, 2016 at 1: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. Commented Dec 5, 2016 at 1:14

3 Answers 3

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

He doesn't need to reverse the algorithm. StringBuilder.insert() exists.
@EJP: But using insert defeats the point, because you wouldn't have done anything about the quadratic runtime.
@EJP insert would require moving all the previous input, it would probably involve as much shuffling of memory as the original code.
insert may need to move input, but would still be faster than the original which creates all these strings
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.
|
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();
Improve this answer

1 Comment

I'm going to try this method, thanks for responding all.
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);
Improve this answer

1 Comment

I'm going to try this method, thanks for responding all.