Click here to Skip to main content
15,860,943 members
Articles / Programming Languages / C#
Article

Fastest C# Case Insenstive String Replace

Rate me:
Please Sign up or sign in to vote.
4.72/5 (30 votes)
4 Jul 20052 min read 352K   1.6K   59   44
Find a fast way to replace case insenstive string.

Introduction

Dealing with data, for many cases, we need to manipulate strings (strings could be the final form of any data, even binary), and among them, replacement is frequently used. We could find string replacement in .NET is easy, since there are different means to accomplish it, such as String.Replace, System.Text.Regex, iteration of String.SubString, or even using Microsoft Visual Basic RunTime's (Microsoft.VisualBasic.DLL) Strings.Replace function. However, each of them has drawbacks. Hence a new method is discovered to perform fast case insensitive string replacement.

Background

I am developing a web resource mining system, I need to deal with heavy and large amount of string replacement of site pages. Since characters may differ from lower/upper case, case insensitivity is the core requirement, and speed is also very important. But I could not find a satisfactory method as a standalone (pure C#), fast and case insensitive string replacement function.

Using the code

In .NET, without using C++/CLI, there are a few ways to perform string replacement:

  1. The most commonly used method is the String.Replace, but case insensitivity is not supported.
  2. System.Text.Regex (Regular Expression) could be case insensitive through defining the RegExpOption to be IgnoreCase, but it is not so efficient.
  3. Iteration of String.SubString with normal string concatenation (+) seems to be faster than Regex in small amounts of replacements.
  4. The only difference against method 3 is to use StringBuilder instead of "+". Why is it faster? There are a few articles talking about it on CodeProject.
  5. Import Microsoft Visual Basic RunTime (Microsoft.VisualBasic.DLL) namespace and using Strings.Replace function, is fast! But, some C# users don't like that.
  6. Hey, why not reflecting method 5? I used Reflector with the help of Denis Bauer's Reflector.FileDisassembler, disassembled the source code of Strings.Replace (it has some related functions such as Strings.Split and Strings.Join etc.). It is just as fast as method 5, but without using Microsoft Visual Basic RunTime.

Well, is there any method that could achieve better and even much better performance? Here goes the super fast string replacement method:

C#
private static string ReplaceEx(string original, 
                    string pattern, string replacement)
{
    int count, position0, position1;
    count = position0 = position1 = 0;
    string upperString = original.ToUpper();
    string upperPattern = pattern.ToUpper();
    int inc = (original.Length/pattern.Length) * 
              (replacement.Length-pattern.Length);
    char [] chars = new char[original.Length + Math.Max(0, inc)];
    while( (position1 = upperString.IndexOf(upperPattern, 
                                      position0)) != -1 )
    {
        for ( int i=position0 ; i < position1 ; ++i )
            chars[count++] = original[i];
        for ( int i=0 ; i < replacement.Length ; ++i )
            chars[count++] = replacement[i];
        position0 = position1+pattern.Length;
    }
    if ( position0 == 0 ) return original;
    for ( int i=position0 ; i < original.Length ; ++i )
        chars[count++] = original[i];
    return new string(chars, 0, count);
}

Now let's do some comparisons: the test case is to first generate a long string, then iterate the replacement 1000 times. We include String.Replace to let us know the difference between case sensitive and insensitive options. Please do remember: String.Replace does not support case insensitivity!

C#
static void Main(string[] args)
{
    string segment = "AaBbCc";
    string source;
    string pattern = "AbC";
    string destination = "Some";
    string result = "";
    
    const long count = 1000;
    StringBuilder pressure = new StringBuilder();
    HiPerfTimer time;

    for (int i = 0; i < count; i++)
    {
        pressure.Append(segment);
    }
    source = pressure.ToString();
    GC.Collect();

    //regexp
    time = new HiPerfTimer();
    time.Start();
    for (int i = 0; i < count; i++)
    {
        result = Regex.Replace(source, pattern, 
                  destination, RegexOptions.IgnoreCase);
    }
    time.Stop();

    Console.WriteLine("regexp    = " + time.Duration + "s");
    GC.Collect();

    //vb
    time = new HiPerfTimer();
    time.Start();
    for (int i = 0; i < count; i++)
    {
        result = Strings.Replace(source, pattern, 
                   destination, 1, -1, CompareMethod.Text);
    }
    time.Stop();

    Console.WriteLine("vb        = " + time.Duration + "s");
    GC.Collect();


    //vbReplace
    time = new HiPerfTimer();
    time.Start();
    for (int i = 0; i < count; i++)
    {
        result = VBString.Replace(source, pattern, 
                   destination, 1, -1, StringCompareMethod.Text);
    }
    time.Stop();

    Console.WriteLine("vbReplace = " + time.Duration + "s");// + result);
    GC.Collect();


    // ReplaceEx
    time = new HiPerfTimer();
    time.Start();
    for (int i = 0; i < count; i++)
    {
        result = Test.ReplaceEx(source, pattern, destination);
    }
    time.Stop();

    Console.WriteLine("ReplaceEx = " + time.Duration + "s");
    GC.Collect();


    // Replace
    time = new HiPerfTimer();
    time.Start();
    for (int i = 0; i < count; i++)
    {
        result = source.Replace(pattern.ToLower(), destination);
    }
    time.Stop();

    Console.WriteLine("Replace   = " + time.Duration + "s");
    GC.Collect();


    //sorry, two slow :(
    /*//substring
    time = new HiPerfTimer();
    time.Start();
    for (int i = 0; i < count; i++)
    {
        result = StringHelper.ReplaceText(source, pattern, 
                   destination, StringHelper.CompareMethods.Text);
    }
    time.Stop();

    Console.WriteLine("substring =" + time.Duration + ":");
    GC.Collect();


    //substring with stringbuilder
    time = new HiPerfTimer();
    time.Start();
    for (int i = 0; i < count; i++)
    {
        result = StringHelper.ReplaceTextB(source, pattern, 
                    destination, StringHelper.CompareMethods.Text);
    }
    time.Stop();

    Console.WriteLine("substringB=" + time.Duration + ":");
    GC.Collect();
    */

    Console.ReadLine();
}

The results:

1¡¢string segment = "abcaBc";
regexp = 3.75481827997692s
vb = 1.52745502570857s
vbReplace = 1.46234256029747s
ReplaceEx = 0.797071415501132s !!!<FONT color=gray>Replace = 0.178327413120941s </FONT>
// ReplaceEx > vbReplace > vb > regexp

2¡¢string segment = "abcaBcabC";
regexp = 5.30117431126023s
vb = 2.46258449048692s
vbReplace = 2.5018721653171s
ReplaceEx = 1.00662179131705s !!!
<FONT color=gray>Replace = 0.233760994763301s </FONT>
// ReplaceEx > vb > vbReplace > regexp

3¡¢string segment = "abcaBcabCAbc";
regexp = 7.00987862982586s
vb = 3.61050301085753s
vbReplace = 3.42324876485699s
ReplaceEx = 1.14969947297771s !!!
<FONT color=gray>Replace = 0.277254511397398s </FONT>
// ReplaceEx > vbReplace > vb > regexp

4¡¢string segment = "ABCabcAbCaBcAbcabCABCAbcaBC";
regexp = 13.5940090151123s
vb = 11.6806222578568s
vbReplace = 11.1757614445411s
ReplaceEx = 1.70264153684337s !!!(my god!)
<FONT color=gray>Replace = 0.42236820601501s</FONT>
// ReplaceEx > vbReplace > vb > regexp

OK, is the ReplaceEx function really the fastest in all conditions?

5¡¢string segment = "AaBbCc";
regexp = 0.671307945562914s
vb = 0.32356849823092s
vbReplace = 0.316965703741677s !!!
ReplaceEx = 0.418256510254795s
Replace = 0.0453026851178013s 
// vbReplace > vb > ReplaceEx > regexp

Why? The bottle neck is:

C#
string upperString = original.ToUpper();
string upperPattern = pattern.ToUpper();

When there is no string to be replaced, time is wasted in string.ToUpper().

Points of Interest

I love resources mining and clustering. I have developed a GUI system with support for windows, mouse, multimedia, true color screen using Quick BASIC 7.1!

History

  • 2005.7.2 - First release.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Product Manager www.xnlab.com
Australia Australia
I was born in the south of China, started to write GWBASIC code since 1993 when I was 13 years old, with professional .net(c#) and vb, founder of www.xnlab.com

Now I am living in Sydney, Australia.

Comments and Discussions

 
QuestionMaybe some easier? Pin
Froschkoenig8411-May-18 8:14
Froschkoenig8411-May-18 8:14 
AnswerMy code is the fastest =) Pin
G3n1us7620-Oct-12 13:34
G3n1us7620-Oct-12 13:34 
GeneralRe: My code is the fastest =) Pin
harald.schmitt7-May-13 0:16
harald.schmitt7-May-13 0:16 
GeneralRe: My code is the fastest =) Pin
G3n1us767-May-13 2:11
G3n1us767-May-13 2:11 
GeneralRe: My code is the fastest =) Pin
harald.schmitt4-Nov-14 3:25
harald.schmitt4-Nov-14 3:25 
GeneralMy vote of 5 Pin
Eddy Vluggen19-Dec-11 23:42
professionalEddy Vluggen19-Dec-11 23:42 
GeneralMy vote of 5 Pin
Jeffrey Schaefer17-Dec-11 10:45
Jeffrey Schaefer17-Dec-11 10:45 
GeneralMy vote of 1 Pin
Priyank Bolia3-Dec-09 2:47
Priyank Bolia3-Dec-09 2:47 
GeneralRe: My vote of 1 Pin
Eddy Vluggen19-Dec-11 23:41
professionalEddy Vluggen19-Dec-11 23:41 
Are you sure it's caused by this code? Smile | :)
Bastard Programmer from Hell Suspicious | :suss:

GeneralRe: My vote of 1 Pin
Huisheng Chen20-Dec-11 9:50
Huisheng Chen20-Dec-11 9:50 
GeneralMy vote of 1 Pin
abcd1234f10-Aug-09 8:39
abcd1234f10-Aug-09 8:39 
GeneralOne more way to do this Pin
sohail.2329-May-08 20:13
sohail.2329-May-08 20:13 
GeneralRe: One more way to do this Pin
Michael Epner8-Apr-09 23:41
Michael Epner8-Apr-09 23:41 
Generalfurther optimizations Pin
clerigo1-Aug-07 7:32
clerigo1-Aug-07 7:32 
Generalthis one is even faster and more flexible [modified] PinPopular
Michael Epner9-Jan-07 7:08
Michael Epner9-Jan-07 7:08 
GeneralRe: this one is even faster and more flexible Pin
dCyphr15-Feb-08 3:59
dCyphr15-Feb-08 3:59 
GeneralRe: this one is even faster and more flexible Pin
Biff_MaGriff11-Apr-08 11:32
Biff_MaGriff11-Apr-08 11:32 
GeneralRe: this one is even faster and more flexible Pin
dCyphr18-Apr-08 18:30
dCyphr18-Apr-08 18:30 
GeneralRe: this one is even faster and more flexible Pin
Michael Epner8-Apr-09 23:53
Michael Epner8-Apr-09 23:53 
GeneralRe: this one is even faster and more flexible Pin
tmbrye22-Sep-08 14:16
tmbrye22-Sep-08 14:16 
GeneralRe: this one is even faster and more flexible Pin
Michael Epner6-Nov-08 4:35
Michael Epner6-Nov-08 4:35 
GeneralRe: this one is even faster and more flexible Pin
K.v.S.30-Oct-08 3:14
K.v.S.30-Oct-08 3:14 
GeneralRe: this one is even faster and more flexible Pin
Member 5515089-Dec-08 6:55
Member 5515089-Dec-08 6:55 
GeneralRe: this one is even faster and more flexible Pin
Michael Epner8-Apr-09 23:26
Michael Epner8-Apr-09 23:26 
GeneralRe: this one is even faster and more flexible Pin
jamie jones8-Apr-09 8:11
jamie jones8-Apr-09 8:11 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.