3
\$\begingroup\$

The challenge:

From: URI Online Judge

Implement a program Combiner that takes two Strings as parameters and combines them, alternating letters, starting with the first letter of the first String, followed by the first letter of the second String, then second letter of first String, etc. The remaining letters of the longer String are then appended to the end of the combination String and this combination String is returned.

Input

The input contains several test cases. The first line of input contain an integer N that indicates the number of test cases. Each test case is composed of a line containing two strings and each string contains between 1 and 50 characters, inclusive.

Output

Combine the two input strings, as shown in the example below and print the resulting string.

Sample input and output

Code

static void Main(string[] args)
{
    int n = int.Parse(Console.ReadLine());

    while(n-- > 0)
    {
        args = Console.ReadLine().Split(' ');

        for (int j = 0; j < args[0].Length || j < args[1].Length; j++)
        {
            if (j < args[0].Length)
            {
                Console.Write(args[0][j]);
            }
            if (j < args[1].Length)
            {
                Console.Write(args[1][j]);
            }
        }

        Console.WriteLine();
    }
}

Question is

How can this code be faster?

Apparently, my code took 0.384 second to run with URI's test cases.

The faster sample that solved the problem using C# took 0.072 second, which is a significant difference.

An image with all the execution times from this problem in C# can be found here.

\$\endgroup\$
  • 6
    \$\begingroup\$ Well, since you don't have bad complexity in your algorithm I guess what takes time are the many Console.Write calls. So even when it is unintuitive it might be better to prepare the output line in a buffer before writing it (and no that is not a good situation for an algorithmic competition framework). The boundary check in the for loop might confuse the optimizer, but it is not clear if a single max() before the loop increases the speed). \$\endgroup\$ – eckes Aug 30 '17 at 18:37
4
\$\begingroup\$

Write to StringBuilder and then Console.WriteLine once.

When you run out of one then use Substring.

\$\endgroup\$
  • \$\begingroup\$ All the answers were helpful. I'm accepting this one because the Console.WriteLine calls were what was taking the most time. Only by using StringBuilder, the execution time dropped to 0.044 second. Thank you all :) \$\endgroup\$ – appa yip yip Aug 31 '17 at 13:38
4
\$\begingroup\$

An if in a tight loop is usually a performance killer. At least worth trying is something along the lines of

    len = min(args[0].Length, args[1].Length);
    for (j = 0; j < len; ++j) {
        Console.Write(args[0][j]);
        Console.Write(args[1][j]);
    }
    WriteRemainingsOfLongerString();

As mentioned in the comments, it could also be more performant to build a string and Console.Write it at once.

\$\endgroup\$
2
\$\begingroup\$

If performance really wins over clarity and readability, you can even omit the Split().

string Interleave(string line) {
  var space = line.IndexOf(' ');
  var start1 = 0;
  var end1 = space;
  var start2 = space + 1;
  var end2 = line.Length;
  var interleaved = new StringBuilder(line.Length - 1);
  ...
}

var line = Console.ReadLine();
Console.WriteLine(Interleave(line));
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.