1

I have a program that builds a string in a loop, and my program is too slow. It takes now about 600 milliseconds to run Oblig1Test.oppgave7. What could be done to speed it up?

Oblig1.toString:

public static String toString(int[] a, char v, char h, String mellomrom)
{
    String s ="";

    s += v;

    if(a.length != 0)
    {
        for(int i = 0; i < a.length-1; i++)
        {
                s += a[i] + mellomrom; 
        }

        s += a[a.length-1];
    }

    s += h;

    return s;
}

Oblig1Test:

public static int oppgave7()
{
   int[] b = new int[20000];
   long tid = System.currentTimeMillis();
   Oblig1.toString(b,' ',' '," ");
   tid = System.currentTimeMillis() - tid;

  if (tid > 40)
  {
    System.out.println("Oppgave 7: Metoden "
      + "er for ineffektiv. Må forbedres!");
  }
}

public static void main(String[] args) throws IOException
{
   oppgave7();
}
Gilles 'SO- stop being evil'
  • 104,111
  • 38
  • 209
  • 254
mv700
  • 35
  • 1
  • 8

4 Answers4

8

When the slow operation in your code is the concatenation of many strings, chances are you'll gain a lot by using a StringBuilder.

By changing your toString method to

public static String toString(int[] a, char v, char h, String mellomrom){
    StringBuilder sb = new StringBuilder();
    sb.append(v);
    if(a.length != 0){
        for(int i = 0; i < a.length-1; i++){
                sb.append(a[i]).append(mellomrom); 
        }
        sb.append(a[a.length-1]);
    }
    sb.append(h);
    return sb.toString();
}

I was able to pass from 493 ms to 22 ms on my computer.

Denys Séguret
  • 372,613
  • 87
  • 782
  • 758
3

Use a StringBuilder:

public static String toString(int[] a, char v, char h, String mellomrom) {
    StringBuilder sb = new StringBuilder();
    sb.append(v);
    for(int i = 0 ; i < a.length - 1 ; ++i) {
        sb.append(a[i]).append(mellomrom);
    }
    if(a.length != 0) {
        sb.append(a[a.length-1]);
    }
    sb.append(h);
    return sb.toString();
}
Jean Logeart
  • 52,687
  • 11
  • 83
  • 118
2

First of all, single character names for variables? Bad boy! :) Give things meaningful names, it doesn't cost anything.

Secondly, strings in Java are immutable. The statment 

String concatedString = concatedString + secondString

doesn't mean "Append the value of secondString to concatedString", it means "Make a new String that's the value of concatedString and secondString, throw away concatedString and make the concatedString reference refer to the new string". In other words, every time you use + to concatenate strings, you're implicitly creating a new String object.

Creating objects in a loop is very expensive.

Java provides a set of mutable strings such as StringBuilder and StringBuffer (the latter being thread-safe but less performant). Use one of them instead.

Petr Janeček
  • 37,768
  • 12
  • 121
  • 145
GordonM
  • 31,179
  • 15
  • 87
  • 129
  • Note that this isn't necessarily true (at least as of today). Your example, in its currents state and with Java 1.6+, will be automatically rewritten using a StringBuilder for you and you don't need to do anything. In the OP's case, however, only parts of his function will be optimized by `javac` and he should rather be explicit with its own use of a single StringBuilder instance. – haylem Sep 04 '13 at 13:41
  • I wasn't aware of the automatic stringbuffer creation, I'll have to remember that. But given the caveats you mentioned it's probably not wise to depend on it. – GordonM Sep 04 '13 at 13:42
  • No, but in general I tend to not fuss about using StringBuilders that much anymore, except for specially intensive string building cases. Since I now only target Java 6+ platforms most of the time, I don't worry so much about it, or I rewrite my `toString()` to create cases where `javac` is able to do most of the work by itself and get the best of both worlds: decent readability and decent speed, albeit not the best one. I'd recommend you play around with `javap` to look at some simple examples' bytecode. It's fun. – haylem Sep 04 '13 at 13:46
  • see this [conversation with Heinz Kabutz](http://www.oracle.com/technetwork/articles/javase/kabutz-qa-136652.html). Beware, some of that may already be outdated, but that will tell you what to look for. – haylem Sep 04 '13 at 13:47
  • See also: http://stackoverflow.com/questions/14927630/java-string-concat-vs-stringbuilder-optimised-so-what-should-i-do – haylem Sep 04 '13 at 13:49
1

Yes, this is a common problem.

Strings in Java are immutable which means that once a String object is constructed, it can't be modified in any way and all manipulations with it are done via copying the contents.

In your particular case, when you do s += v or s += a[i] + mellomrom, it actually copies the contents of the s string to a new StringBuilder, concatenates the parts and then makes a String out of that StringBuilder. So,

s += v

becomes

s = new StringBuilder(s).append(v).toString();

And

s += a[i] + mellomrom

becomes 

s = new StringBuilder(s).append(a[i]).append(mellomrom).toString();

This, when done in a loop, is a major performance disaster (construction of two new objects, copying the contents twice). To construct a string in a loop, use your own StringBuilder instance, so you only have one and you don't have to convert it to a String on every iteration:

public static String toString(int[] a, char v, char h, String mellomrom)
{
    StringBuilder sb = new StringBuilder();
    sb.append(v);

    if(a.length != 0)
    {
        for(int i = 0; i < a.length-1; i++)
        {
            sb.append(a[i]).append(mellomrom);
        }
        sb.append(a[a.length-1]);
    }
    sb.append(h);
    return sb.toString();
}
Petr Janeček
  • 37,768
  • 12
  • 121
  • 145
  • In his case, he can even set the exact capacity of the StringBuilder right from the start, as we now the size and separators to use. – haylem Sep 04 '13 at 13:44