Inverse String.Replace - Faster way of doing it?

Question

I have a method to replace every character except those I specify. For example,

ReplaceNot("test. stop; or, not", ".;/\\".ToCharArray(), '*');

would return

"****.*****;***,****".

Now, this is not an instance of premature optimization. I call this method quite a few times during a network operation. I found that on longer strings, it is causing some latency, and removing it helped a bit. Any help to speed this up would be appreciated.

    public static string ReplaceNot(this string original, char[] pattern, char replacement)
    {           
        int index = 0;
        int old = -1;

        StringBuilder sb = new StringBuilder(original.Length);

        while ((index = original.IndexOfAny(pattern, index)) > -1)
        {
            sb.Append(new string(replacement, index - old - 1));
            sb.Append(original[index]);
            old = index++;
        }

        if (original.Length - old > 1)
        {
            sb.Append(new string(replacement, original.Length - (old + 1)));
        }

        return sb.ToString();
    }

Final #'s. I also added a test case for a 3K character string, ran at 100K times instead of 1M to see how well each of these scales. The only surprise was that the regular expression 'scaled better' than the others, but it is no help since it is very slow to begin with:

User            Short * 1M  Long * 100K     Scale
John            319             2125            6.66
Luke            360             2659            7.39
Guffa           409             2827            6.91
Mine            447             3372            7.54
DirkGently      1094            9134            8.35
Michael         1591            12785           8.04
Peter           21106           94386           4.47

Update: I made the creation of the regular expression for Peter's version a static variable, and set it to RegexOptions.Compiled to be fair:

User            Short * 1M      Long * 100K     Scale
Peter           8997            74715           8.30

Pastebin link to my testing code, please correct me if it is wrong: http://pastebin.com/f64f260ee

One nit: please change pattern.Contains(original[i]) == false ? replacement : original[i] to pattern.Contains(original[i]) ? original[i] : replacement. Comparing a bool expression to true/false isn't necessary and is usually considered bad form. — Michael Burr
– Michael Burr, Commented May 5, 2009 at 19:37
I have run speed tests for all of these versions, and your newest edit is actually the slowest of all of them, how are you getting results 4x faster? — John Rasch
– John Rasch, Commented May 5, 2009 at 19:39
@john, I am rechecking them, hoping I didn't mess something up like reloading a webpage while running the test :) — esac
– esac, Commented May 5, 2009 at 19:46
@Michael: our company requires us to be explicit in all of our comparisons so that any future developers know exactly what we intend. It's not so bad with == false or == true, but to avoid people trying to use boolean comparisons with integer return values, they just said all comparisons must be explicit. — esac
– esac, Commented May 5, 2009 at 19:55
@esac: This ought to be the pin-up post for SO. I just love the way you have responded. BTW: When you say my version, which one did you go for? (I had mentioned an unsafe version as well in my comments to Peter's post.) — dirkgently
– dirkgently, Commented May 6, 2009 at 6:54

heijp06 · Accepted Answer · 2009-05-05 18:55:23Z

8

Can't you use Regex.Replace like so:

Regex regex = new Regex(@"[^.;/\\]");
string s = regex.Replace("test. stop; or, not", "*");

answered May 5, 2009 at 18:55

heijp06

11.8k1 gold badge43 silver badges63 bronze badges

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

9 Comments

gregmac Over a year ago

This screams regex to me as well. As soon as you have more than a couple calls to .IndexOf* or .Substring methods (or the possibly less efficient (?) "new string(replacement, index - old - 1)"), you can probably accomplish whatever you're trying to do with a relatively simple regex, in a couple lines of code.

dirkgently Over a year ago

And regex will be faster than running over the string once? I always though regex-es were no good when performance was an issue!

esac Over a year ago

Using a Regex and a simple test to execute it in a loop 1million times, my method above takes 4200 milliseconds, whereas the Regex takes 34000 milliseconds. I know it is cleaner, but I would love to see a speed improvement :)

dirkgently Over a year ago

@esac: Can you try the method I described (performance comparison)?

esac Over a year ago

dirkgently: if you mean iterating through the string as a char array and assigning that into a new char array and returning a string, that was my first pass through. it isnt always just 'alphabet and whitespace', so it has to be generic. i'll revert my code back to that version and post the same number for comparison.

|

John Rasch · Accepted Answer · 2009-05-05 19:46:23Z

6

Alright, on a ~60KB string, this will perform about 40% faster than your version:

public static string ReplaceNot(this string original, char[] pattern, char replacement)
{
    int index = 0;

    StringBuilder sb = new StringBuilder(new string(replacement, original.Length));

    while ((index = original.IndexOfAny(pattern, index)) > -1)
    {
        sb[index] = original[index++];
    }

    return sb.ToString();
}

The trick is to initialize a new string with all replacement characters, since most of them will be replaced.

edited May 5, 2009 at 19:46

answered May 5, 2009 at 18:55

John Rasch

63.6k19 gold badges109 silver badges141 bronze badges

3 Comments

Michael Burr Over a year ago

+1 - Nice. However, I guarantee in this case that since the result of the ++index or index++ expression isn't being used, there would be absolutely zero difference in performance (as far as how you increment index). I'm sure the JIT would generate the exact same code. I wouldn't be surprised if csc.exe generated the exact same IL.

John Rasch Over a year ago

@Michael - it appears you are right, when I changed it back it seems to perform similarly, I don't know why it was different last time I tested it

Michael Burr Over a year ago

To view IL there's ildasm which comes with the .NET Framework (or maybe the SDK), or you can do what all the cool kids do and use the free .NET Reflector: red-gate.com/products/reflector

Michael Burr · Accepted Answer · 2009-05-05 19:28:19Z

4

I don't know if this will be any faster, but it avoids newing up strings just so they can be appended to the string builder, which may help:

    public static string ReplaceNot(this string original, char[] pattern, char replacement)
    {
        StringBuilder sb = new StringBuilder(original.Length);

        foreach (char ch in original) {
            if (Array.IndexOf( pattern, ch) >= 0) {
                sb.Append( ch);
            }
            else {
                sb.Append( replacement);
            }
        }

        return sb.ToString();
    }

If the number of chars in pattern will be of any size (which I'm guessing it generally won't), it might pay to sort it and perform an Array.BinarySearch() instead of the Array.indexOf().

For such a simple transformation, I'd bet that it'll have no problem being faster than a regex, too.

Also, since your set of characters in pattern are likely to usually come from a string anyway (at least that's been my general experience with this type of API), why don't you have the method signature be:

public static string ReplaceNot(this string original, string pattern, char replacement)

or better yet, have an overload where pattern can be a char[] or string?

edited May 5, 2009 at 19:28

answered May 5, 2009 at 19:11

Michael Burr

342k52 gold badges553 silver badges774 bronze badges

1 Comment

Michael Burr Over a year ago

Well - after looking at your timing results I'm a little surprised at how poorly this fares compared to your original... I guess that using String.IndexOfAny() is far, far better than calling Array.IndexOf repeatedly on each character.

LukeH · Accepted Answer · 2009-05-05 23:24:14Z

4

Here's another version for you. My tests suggest that its performance is pretty good.

public static string ReplaceNot(
    this string original, char[] pattern, char replacement)
{
    char[] buffer = new char[original.Length];

    for (int i = 0; i < buffer.Length; i++)
    {
        bool replace = true;

        for (int j = 0; j < pattern.Length; j++)
        {
            if (original[i] == pattern[j])
            {
                replace = false;
                break;
            }
        }

        buffer[i] = replace ? replacement : original[i];
    }

    return new string(buffer);
}

answered May 5, 2009 at 23:24

LukeH

271k59 gold badges373 silver badges411 bronze badges

3 Comments

esac Over a year ago

very nice, although your scaling is off a little bit, you are very close to beating the top submission :) i've updated the main times.

Michael Burr Over a year ago

Interesting - algorithm-wise this is similar to my post. The main differences are an explicit loop instead of calling Array.IndexOf() and using a char[] to build the result instead of a StringBuffer(). But this implementation is 4-5x faster...

LukeH Over a year ago

@esac, It seems that the benchmarks vary significantly depending on the machine/framework they're running on: On my old PC (P4 2.6GHz, 1.5GB, XP32) my version is twice as fast as John's; On my newer PC (Core2Duo 2.66GHz, 4GB, Vista64) John's version is twice as fast as mine!

Guffa · Accepted Answer · 2009-05-05 19:56:23Z

2

The StringBuilder has an overload that takes a character and a count, so you don't have to create intermediate strings to add to the StringBuilder. I get about 20% improvement by replacing this:

sb.Append(new string(replacement, index - old - 1));

with:

sb.Append(replacement, index - old - 1);

and this:

sb.Append(new string(replacement, original.Length - (old + 1)));

with:

sb.Append(replacement, original.Length - (old + 1));

(I tested the code that you said was about four times faster, and I find it about 15 times slower...)

answered May 5, 2009 at 19:56

Guffa

703k111 gold badges760 silver badges1k bronze badges

2 Comments

Michael Burr Over a year ago

So what I think is the interesting question now is: is this faster than John Rasch's routine which optimistically loads the StringBuilder with the replacement char or Rasch's faster? I could see it going either way (and I suspect it's data dependant).

Michael Burr Over a year ago

@esac - thanks... I'm genuinely interested, and I'm glad there's someone less lazy than me around here to find out!

dirkgently · Accepted Answer · 2009-05-05 18:53:32Z

0

It's going to be O(n). You seem to be replacing all alphabets and whitespaces by *, why not just test if the current character is an alphabet/whitespace and replace it?

answered May 5, 2009 at 18:53

dirkgently

112k16 gold badges135 silver badges190 bronze badges

Collectives™ on Stack Overflow

Inverse String.Replace - Faster way of doing it?

6 Answers 6

9 Comments

3 Comments

1 Comment

3 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

9 Comments

3 Comments

1 Comment

3 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related