反转字符串替换 - 有更快的方法吗？

Question

我有一种方法可以替换除了指定字符以外的所有字符。例如，

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

希望返回：

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

现在，这不是过早的优化实例。我在网络操作期间多次调用此方法。我发现对于较长的字符串，它会导致一些延迟，删除它有所帮助。任何加快速度的帮助都将不胜感激。

    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();
    }

最终结果。我还添加了一个测试用例，针对一个3K字符的字符串，运行100K次而不是1M，以查看每个算法的扩展性如何。唯一的惊喜是正则表达式比其他算法“更好”，但由于它本身非常慢，所以没有帮助：

用户 短 * 1M 长 * 100K 比例 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

更新：我将Peter版本的正则表达式创建为静态变量，并将其设置为RegexOptions.Compiled，以公平起见：

用户 短 * 1M 长 * 100K 比例 Peter 8997 74715 8.30

我的测试代码Pastebin链接，请纠正我如果有错：http://pastebin.com/f64f260ee

- esac

---

@John，我正在重新检查它们，希望我没有搞砸像在运行测试时重新加载网页这样的事情 :) - esac

@Michael：我们公司要求我们在所有比较中都必须明确表达我们的意图，以便未来的开发人员清楚地了解我们的意图。使用“== false”或“== true”并不太糟糕，但为了避免人们试图使用整数返回值进行布尔比较，他们只是说所有比较必须是明确的。 - esac

@john，你是正确的，我重新运行了它们并发布了上面的时间。对于我的错误我很抱歉。 - esac

很好，我用了不同的方法进行测试（在60k字符串上迭代1次），但是在百分比方面几乎得到了完全相同的结果。顺便说一下，您可以在一个函数调用中重置和启动秒表：sw = Stopwatch.StartNew()。 - John Rasch

@esac: 这应该是SO的代表性帖子。我非常喜欢你的回复方式。顺便问一下：当你说“我的版本”时，你选择了哪个？（在评论Peter的帖子中，我还提到了一个不安全的版本。） - dirkgently

Answer 1

你不能像这样使用 Regex.Replace 吗：

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

- heijp06

---

正则表达式比仅遍历字符串更快吗？我一直认为在性能成为问题时，正则表达式并不好！ - dirkgently

使用正则表达式和简单的测试来在循环中执行100万次，我的方法需要4200毫秒，而正则表达式需要34000毫秒。我知道它更干净，但我希望看到速度的提高 :) - esac

@esac: 你可以尝试一下我描述的方法（性能比较）吗？ - dirkgently

@esac：只要要替换的字符集是固定的，这种方法就可以很好地工作，并且可能是最好的方法。尽量不要创建新字符串，而是直接进行修改。如果其他方法都失败了，您还可以使用不安全的选项访问字符串作为C风格数组并进行修改（尽管我怀疑这是否会提高性能）。 - dirkgently

@esac：你还想要一个更好的算法吗？;-) - dirkgently

Answer 2

好的，对于一个约为60KB的字符串，在这种情况下，这将比你的版本快大约40％：

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();
}

技巧在于用所有的替换字符初始化一个新字符串，因为大多数字符都将被替换。

- John Rasch

---

+1 - 很好。然而，在这种情况下，我保证由于未使用++index或index++表达式的结果，增加索引的性能不会有任何差异。我相信JIT将生成完全相同的代码。如果csc.exe生成完全相同的IL，我也不会感到惊讶。 - Michael Burr

@Michael - 看起来你是对的，当我把它改回去时，它似乎表现相似，我不知道上次测试时为什么不同。 - John Rasch

要查看IL代码，可以使用.NET Framework（或者可能是SDK）附带的ildasm工具，或者像所有酷孩子一样使用免费的.NET Reflector：http://www.red-gate.com/products/reflector/ - Michael Burr

Answer 3

我不知道这样做是否更快，但它避免了新建字符串，只是为了将它们附加到字符串构建器中，这可能有所帮助：

    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();
    }

如果pattern的字符数很大（我猜一般不会），那么对其进行排序并执行Array.BinarySearch()可能更好，而不是使用Array.indexOf()。

对于如此简单的转换，我敢打赌它的速度比正则表达式快。

另外，由于pattern中的字符集通常来自一个字符串（至少这是我在使用这种API时的经验），为什么不将方法签名改为：

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

或者更好的是，有一个重载函数，其中pattern可以是char[]或string吗？

- Michael Burr

---

好的 - 在查看您的计时结果之后，我对与您的原始版本相比表现如此糟糕感到有些惊讶...我想使用String.IndexOfAny()远远优于对每个字符重复调用Array.IndexOf。 - Michael Burr

Answer 4

这是另一个版本。我的测试表明其性能相当不错。

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);
}

- LukeH

---

非常好，虽然你的缩放有点偏差，但你离击败最高提交非常接近 :) 我已经更新了主要时间。 - esac

有趣的是，从算法角度来看，这与我的帖子类似。主要区别在于使用显式循环而不是调用Array.IndexOf()，并且使用char[]构建结果而不是StringBuffer()。但是，这个实现速度快了4-5倍... - Michael Burr

@esac，看起来基准测试结果会因为运行的机器/框架而有很大差异：在我的旧电脑上（P4 2.6GHz，1.5GB，XP32），我的版本比John的快两倍；在我的新电脑上（Core2Duo 2.66GHz，4GB，Vista64），John的版本比我的快两倍！ - LukeH

Answer 5

StringBuilder有一个重载方法，它接受一个字符和计数，因此您无需创建中间字符串来添加到StringBuilder中。通过替换以下代码，我可以获得约20％的性能提升：

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

使用：

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

并且这个：

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

使用：

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

(我测试了你说的那个代码，发现它比原来慢了大约15倍...)

- Guffa

---

我认为现在有趣的问题是：这比John Rasch的程序更快吗？他的程序会用替换字符乐观地加载StringBuilder，或者Rasch的程序更快？我可以看到两种可能性（我怀疑它取决于数据）。 - Michael Burr

@esac - 谢谢...我真的很感兴趣，很高兴这里有比我更勤奋的人去找出答案！ - Michael Burr

Answer 6

这将是O(n)的。您似乎正在用*替换所有字母和空格，为什么不只测试当前字符是否为字母/空格并替换它呢？

- dirkgently