C# loop through array of chars not efficient

Question

I have this code below where I loop through string and compare everything char by char and it's very slow process I wonder how I can improve this code.

        //delete anti-xss junk ")]}'\n" (5 chars);
        if (trim)
        {
            googlejson = googlejson.Substring(5);
        }

        //pass through result and turn empty elements into nulls
        //echo strlen( $googlejson ) . '<br>';
        bool instring = false;
        bool inescape = false;
        string lastchar = "";
        string output = "";
        for ( int x=0; x< googlejson.Length; x++ ) {

            string ch = googlejson.Substring(x, 1);

            //toss unnecessary whitespace
            if ( !instring && ( Regex.IsMatch(ch, @"/\s/"))) {
                continue;
            }

            //handle strings
            if ( instring ) {
                if (inescape) {
                    output += ch;
                    inescape = false;
                } else if ( ch == "\\" ) {
                    output += ch;
                    inescape = true;
                } else if ( ch == "\"") {
                    output += ch;
                    instring = false;
                } else {
                    output += ch;
                }
                lastchar = ch;
                continue;
            }


            switch ( ch ) {

                case "\"":
                    output += ch;
                    instring = true;
                    break;

                case ",":
                    if ( lastchar == "," || lastchar == "[" || lastchar == "{" ) { 
                        output += "null";
                    }
                    output += ch;
                    break;
                case "]":
                case "}":
                    if ( lastchar == "," ) { 
                        output += "null";
                    }
                    output += ch;
                    break;

                default:
                    output += ch;
                    break;
            }
            lastchar = ch;
        }
        return output;

This is just amazing.

I have changed 2 following lines and gain phenomenal performance increase like 1000% or something

First change this

string ch = googlejson.Substring(x, 1);

to that

string ch = googlejson[x].ToString();

Second I replaced all += ch with String Builder

output.Append(ch);

So those 2 changes had maximum performance impact.

As the code only has one For loop, I think it is slow not because the code is not efficient but because the code is complicate. Without consider of improving your method (as I don't know your requirement), if you are worried about long non-responding times of the UI, I suggest you to put the function in a backgroundworker and implement a progressbar if you haven't done so already. — Bolu
– Bolu, Commented Feb 3, 2012 at 9:55

MartinStettner · Accepted Answer · 2012-02-03 09:34:19Z

6

First, you shouldn't use Substrings, when only dealing with single characters. Use

char ch = googlejson[x];

instead.

You could also consider using a StringBuilder for your output variable. If you're working with string, you should always have in mind, that strings are immutable in .NET, so for every

output += ch;

there is a new string instance created.

Use

StringBuilder output = new StringBuilder();

and

output.append(ch);

instead.

answered Feb 3, 2012 at 9:34

MartinStettner

29.3k15 gold badges84 silver badges106 bronze badges

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

9 Comments

Tom Squires Over a year ago

The performance gain of StringBuilder is so small on any modern system that there is no point in the increased complexity codinghorror.com/blog/2009/01/…

Jodrell Over a year ago

@Tom Squires, is it really that complex?

Tom Squires Over a year ago

@Jodrell its not a lot more complex but for negligible performance gain even a small amount of extra complexity isnt worth it.

weston Over a year ago

@TomSquires that link deals with the case where it is not in a loop. When it is not a loop, c# replaces + with String.Concat. In a loop StringBuilder use is essential, don't believe all you read - profile!

MartinStettner Over a year ago

That's not entirely true. For small examples (like the one in the post you mentioned) the difference is small, of course. For only 10 appends, the quadratic complexity doesn't really matter (also, if you run the same 10 appends thousands of times on new strings...) But in a loop like the one presented here, it does matter. I did a simple test of appending a single char 10000 times. I got times of 7ms for StringBuilder and 3238ms for += concatenation!! So I think, if you're appending in a loop, you should always use a StringBuilder (if you expect more than a couple of iterations).

|

StephenD · Accepted Answer · 2012-02-03 09:52:38Z

As per the other comments, this code's use of strings as characters and Substring() is pretty dire - in terms of performance. Also, the use of Regex to check for whitespace going to be very inefficient.

If you want to operate on characters, use characters (char) not strings.

The for loop is a bit inefficient, but the JIT compiler probably optimises that away. It would be slightly better to use a local variable instead of accessing Length property.

Doing a switch on strings is pretty inefficient too, when a switch on characters is darn fast.

And as MartinStettner suggested, StringBuilder append will be better for building the result. (@Tom Squires - This question is all about performance, so yes it does matter, and it isn't more complex - it may be a few more characters but that's not complexity.

Finally, I would say that if you have performance problems (apart from this dire code), you should consider measuring it with a profiler before getting carried away with optimisation.

PS This looks like an interview question ... tut tut if this is the case, that's not what SO is for.

Jodrell · Accepted Answer · 2012-02-03 10:04:15Z

0

Why not use the StringReader instead of SubString

var output = new StringBuilder();

using (var reader = new StringReader(googleJson)
{
    var buffer = new char[1]
    while (reader.Read(buffer, 0, 1) == 1)
    {
        var ch = buffer[0];

        //your stuff

        output.Append(ch);
    }
}

return output.ToString();

You could use StringReader.Read() and do all you logic on the integer code value of the charachter which would be fast but a little brittle.

edited Feb 3, 2012 at 10:04

answered Feb 3, 2012 at 9:58

Jodrell

35.9k6 gold badges94 silver badges131 bronze badges

1 Comment

StephenD Over a year ago

I think you'll find that the overhead of the StringReader.Read() call outweighs a simple googleJson[i]. The allocation/initialisation of the StringReader() is also unnecessary and might be measurable for small loops.

gimbar · Accepted Answer · 2012-02-03 14:36:09Z

0

What about:
if ( !instring && ( Regex.IsMatch(ch, @"/\s/")))
to
if ( !instring && ch < 33)
or even better:
if ( !instring && Char.IsWhiteSpace(ch))

edited Feb 3, 2012 at 14:36

answered Feb 3, 2012 at 10:01

gimbar

13510 bronze badges

Collectives™ on Stack Overflow

C# loop through array of chars not efficient

4 Answers 4

9 Comments

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

9 Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related