Click here to Skip to main content
15,860,972 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

 
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 
GeneralRe: this one is even faster and more flexible Pin
Michael Epner8-Apr-09 23:54
Michael Epner8-Apr-09 23:54 
GeneralRe: Modify to Replace Only at End of String Pin
kevinswarner9-Apr-09 10:35
kevinswarner9-Apr-09 10:35 
I know I should spend the time to do this on my own, but thought I would ask for suggestions on how to modify to only replace match at end of original string. I use a regex right now, but would rather use this faster approach.
GeneralRe: Modify to Replace Only at End of String Pin
Michael Epner14-Apr-09 5:57
Michael Epner14-Apr-09 5:57 
GeneralRe: this one is even faster and more flexible Pin
db conner27-Feb-10 6:46
db conner27-Feb-10 6:46 
GeneralThere is no clear winner Pin
IK1322-Feb-12 10:46
IK1322-Feb-12 10:46 
GeneralRe: this one is even faster and more flexible [modified] Pin
Abi Bradbury16-Dec-14 3:57
Abi Bradbury16-Dec-14 3:57 
GeneralRe: this one is even faster and more flexible [modified] Pin
Michael Epner16-Dec-14 4:10
Michael Epner16-Dec-14 4:10 
Generalizpit Pin
Ballitano28-Nov-06 4:35
Ballitano28-Nov-06 4:35 
QuestionWhats wrong with this? Pin
RK KL20-Sep-05 10:41
RK KL20-Sep-05 10:41 
QuestionWhy you does not use RegexOptions.Compile flag? Pin
Oleksandr Kucherenko12-Jul-05 3:04
Oleksandr Kucherenko12-Jul-05 3:04 
GeneralTip Pin
leppie4-Jul-05 4:56
leppie4-Jul-05 4:56 
GeneralRe: Tip Pin
Huisheng Chen4-Jul-05 15:49
Huisheng Chen4-Jul-05 15:49 
GeneralRe: Tip Pin
Rei Miyasaka4-Jul-05 16:17
Rei Miyasaka4-Jul-05 16:17 
GeneralRe: Tip Pin
Huisheng Chen4-Jul-05 16:45
Huisheng Chen4-Jul-05 16:45 
GeneralTweak Pin
Anonymous4-Jul-05 3:36
Anonymous4-Jul-05 3:36 
GeneralRe: Tweak Pin
Huisheng Chen4-Jul-05 3:44
Huisheng Chen4-Jul-05 3:44 
GeneralRe: Tweak Pin
Lieven G.8-Jul-05 20:30
Lieven G.8-Jul-05 20:30 
QuestionCould you expand on your conclusion? Pin
Anonymous4-Jul-05 3:24
Anonymous4-Jul-05 3:24 
AnswerRe: Could you expand on your conclusion? Pin
Huisheng Chen4-Jul-05 3:35
Huisheng Chen4-Jul-05 3:35 

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.