15
\$\begingroup\$

In my C# program I am using Regular expressions to:

  • Loop through a list of possible words in need of replacing.
  • For each word, to find out if a string I am given has any matches.
  • If it does, I perform some (slightly costly) logic to create the replacement.
  • I then perform the actual replacement.

My current code looks roughly as follows:

string toSearchInside; // The actual string I'm going to be replacing within
List<string> searchStrings; // The list of words to look for via regex

string pattern = @"([:@?]{0})";
string replacement;

foreach (string toMatch in searchStrings)
{
    var regex = new Regex(
                            string.Format(pattern, toMatch), 
                            RegexOptions.IgnoreCase
                            );
    var matches = regex.Matches(toSearchInside);

    if (matches.Count == 0)
        continue;

    replacement = CreateReplacement(toMatch);

    toSearchInside = regex.Replace(toSearchInside, replacement);
}

And I can get this working, but it seems somewhat inefficient in that it is using the regex engine twice - Once to find the matches (regex.Matches()) and once for the replacing regex.Replace()). I was wondering if there was a way to simply say replace the matches you already found?

Also, if has been asked what is within the CreateReplacement() method since it could be possibly done via a Match Elevator, but it is actually a separate method that's fairly costly and not really what I'm asking in this case - My bigger question here is how to deal with this situation of having to use Regex twice - Once to find the matches and then a second time to replace them.

I hope that what I'm trying to find out how to do actually makes sense.

\$\endgroup\$
24
\$\begingroup\$

Regex.Matches returns a MatchCollection which contains Matches which captures the index and length of each match. So as such you won't have to fire up the regex engine again because you can do something like this:

string toSearchInside; // The actual string I'm going to be replacing within
List<string> searchStrings; // The list of words to look for via regex

string pattern = @"([:@?]{0})";
string replacement;

foreach (string toMatch in searchStrings)
{
    var regex = new Regex(
                            string.Format(pattern, toMatch), 
                            RegexOptions.IgnoreCase
                            );
    var matches = regex.Matches(toSearchInside);

    if (matches.Count == 0)
        continue;

    replacement = CreateReplacement(toMatch);

    // in case the replacement is of a different length we replace from
    // from back to front to keep the match indices correct
    foreach (var match in matches.Cast<Match>().Reverse())
    {
        toSearchInside = toSearchInside.Replace(match.Index, match.Length, replacement);
    }
}

Unfortunately the .NET framework doesn't come with a positional Replace so we have to create one which I did as an extension method:

public static string Replace(this string s, int index, int length, string replacement)
{
    var builder = new StringBuilder();
    builder.Append(s.Substring(0,index));
    builder.Append(replacement);
    builder.Append(s.Substring(index + length));
    return builder.ToString();
}

If you do this often and the match patterns don't change you could consider two things:

  • Pre-compile the regular expressions
  • Pre-create the replacements
\$\endgroup\$
  • 1
    \$\begingroup\$ Chris, this is EXACTLY what I was looking for! - THANK YOU!!!! \$\endgroup\$ – John Bustos Feb 10 '16 at 20:47
  • \$\begingroup\$ @Heslacher: Thanks, fixed. Actually the code was inline but I felt it would look cleaner with an extension method \$\endgroup\$ – ChrisWue Feb 11 '16 at 8:16
  • \$\begingroup\$ I guess I would have made a extension method which acts on the Match itself. Nevertheless you already got my +1 ;-) \$\endgroup\$ – Heslacher Feb 11 '16 at 8:17
  • 1
    \$\begingroup\$ I know this was a while ago, but if the replacement is a different length than the match, won't the loop "walk" the replacements out of position? e.g., abcdefabcdef if you replace bcd with hello, you get 1,3 and 7,3. The first loop will give you ahelloefabcdef, then the second loop will give you ahellohellobcdef, instead of ahelloefahelloef. After the first loop, the match "moved" to index 9 instead of 7. \$\endgroup\$ – goodeye Aug 16 '17 at 2:40
  • 2
    \$\begingroup\$ ok, my wife the accountant came up with: couldn't you replace them in reverse order? Assuming they're sorted (or sort them to be sure; that was my contribution), then the original positions would still be valid. \$\endgroup\$ – goodeye Aug 16 '17 at 4:11
5
\$\begingroup\$

To improve @ChrisWue's answer I would like to suggest having 2 extension methods, one acting on a MatchCollection and the other acting on a Match like so

public static class RegexExtensions
{
    public static string Replace(this MatchCollection matches, string source, string replacement)
    {
        foreach (var match in matches.Cast<Match>())
        {
            source = match.Replace(source, replacement);
        }
        return source;
    }
    public static string Replace(this Match match, string source, string replacement)
    {
        return source.Substring(0, match.Index) + replacement + source.Substring(match.Index + match.Length);
    }
}  

I have omitted the usually required null checks for these methods because something should be left for you to do.

In addition I have replaced he StringBuilder usage in favour of simple one line string concatenation using + because this is automatically using internaly a StringBuilder

I would like to encourage you to always use braces {} although they might be optional. Using them just helps you to make your code less error prone.

Implementing this changes lead to

string toSearchInside; // The actual string I'm going to be replacing within
List<string> searchStrings; // The list of words to look for via regex

string pattern = @"([:@?]{0})";
string replacement;

foreach (string toMatch in searchStrings)
{
    var regex = new Regex(
                            string.Format(pattern, toMatch), 
                            RegexOptions.IgnoreCase
                            );
    var matches = regex.Matches(toSearchInside);

    if (matches.Count == 0)
    {
        continue;
    }

    replacement = CreateReplacement(toMatch);

    toSearchInside = matches.Replace(toSearchInside, replacement);
}
\$\endgroup\$
  • 2
    \$\begingroup\$ truly, !!!**THANK YOU**!!! - I have to say I love this community for being so intelligent and willing to help! - Thanks!! \$\endgroup\$ – John Bustos Feb 11 '16 at 14:18
  • \$\begingroup\$ I would think there should be a variable introduced into the first extension method so that the source string is not mutated during the method. \$\endgroup\$ – Darren Nov 10 '16 at 9:49
  • \$\begingroup\$ Since your're not reversing the collection it's no longer necessary to cast it. \$\endgroup\$ – Snowbody Dec 11 '17 at 14:02
  • 1
    \$\begingroup\$ This still creates numerous temporary strings and an extra StringBuilder for each replacement. \$\endgroup\$ – Snowbody Dec 11 '17 at 14:03
5
\$\begingroup\$

You don't have to run the same regex twice by first checking if it matches and then replacing parts. You can do everything in a single call to Regex.Replace. If it won't match then the string remains unchanged.

foreach (var toMatch in searchStrings)
{
    toSearchInside = Regex.Replace(
        toSearchInside, 
        string.Format(pattern, toMatch), 
        CreateReplacement(toMatch), 
        RegexOptions.IgnoreCase);
}

If you need more control over the replacement process you can use the MatchEvaluator. This will allow you to evaluate each single replacement.

This is not exactly what you are doing in your code but in case you should need it here's an example:

foreach (var toMatch in searchStrings)
{
    var regex = new Regex(string.Format(pattern, toMatch), RegexOptions.IgnoreCase);

    // Evaluate each match and create a replacement for it.
    toSearchInside = regex.Replace(toSearchInside, m 
        => CreateReplacement(m.Groups[1].Value));
}

where the m is a Match object for the current match.

\$\endgroup\$
  • \$\begingroup\$ A slight improvement would be for CreateReplacement() to use a Dictionary<string,string> for memoization so it only need calculate each replacement maximum once. \$\endgroup\$ – Snowbody Dec 11 '17 at 13:39
  • \$\begingroup\$ @Snowbody I think you're right but the question is so old, I no longer know what it actually was about ;-) \$\endgroup\$ – t3chb0t Dec 11 '17 at 16:00
3
\$\begingroup\$

Improvement to @ChrisWue and @Heslacher's solution

I really like @ChrisWue and @Heslacher's solution but it's inefficient in that a ton of temporary Strings get created with all the calls to Substring, and the same string gets rebuilt over and over and over again (as many StringBuilder objects as there are matches).

It ought to be possible with just one StringBuilder, like so:

var builder = new StringBuilder();
int prevIndex = 0
foreach (var match in matches)
{
    builder.Append(toSearchInside, prevIndex, match.Index);
    builder.Append(replacement);
    prevIndex = match.Length;
}
builder.Append(toSearchInside, prevIndex, toSearchInside.Length - prevIndex);

Benefits: only one StringBuilder, no temporary strings.

Improvement to @t3chb0t's solution

I also was glad that @t3chb0t pointed to the MatchEvaluator solution as I thought it has a lot of promise. I was hoping to replace one of the deficiencies I've seen so far with all proposed solutions to date: the haystack string is scanned multiple times, once for each target word. Regular expressions have the | operator to scan for multiple things at once! After a bit of thought I came up with this:

var MemoizedCreateReplacement = Memoize<string, string>(CreateReplacement);

// note, no start paren, and ending with '|' instead of close paren
string pattern = @"[:@?]{0}|"; 

StringBuilder sb;
sb.Append"(";
foreach(var toMatch in searchStrings)
{
    sb.AppendFormat(pattern,toMatch);
}
sb.chars[sb.Length-1]=")"; // replace last | with )
var regex = new Regex(sb.ToString());
regex.Replace(toSearchInside, m => MemoizedCreateReplacement(m.Groups[1].Value));

Benefits: Only one pass over the toSearchInside string. Only one StringBuilder; no temporary strings used in calls to it. Only one temporary string (for the Regex) and each replacement gets computed once, only if it's needed.

Memoize() code, based on what I found http://explodingcoder.com/blog/content/painless-caching-memoization-net

public static Func<TArg, TResult> Memoize<TArg, TResult>(Func<TArg, TResult> function) {
   return Memoize(function, new Dictionary<TArg, TResult>());
}

public static Func<TArg, TResult> Memoize<TArg, TResult>(Func<TArg, TResult> function, IDictionary<TArg, TResult> cache) {
   return delegate(TArg key) {TResult replacement; return cache.TryGetValue(key, out replacement) ? replacement : (cache[key] = function(key));};
}
\$\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.