从字符串中删除特殊字符的最有效方法

Question

我想从一个字符串中删除所有特殊字符，允许的字符是 A-Z（大写或小写）、数字 (0-9)、下划线 (_) 或点号 (.)。

我有以下代码，它可以工作，但我怀疑（我知道！）它不是很有效率：

    public static string RemoveSpecialCharacters(string str)
    {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.Length; i++)
        {
            if ((str[i] >= '0' && str[i] <= '9')
                || (str[i] >= 'A' && str[i] <= 'z'
                    || (str[i] == '.' || str[i] == '_')))
                {
                    sb.Append(str[i]);
                }
        }

        return sb.ToString();
    }

最高效的方式是什么？正则表达式应该怎样写？与普通字符串操作相比有何优劣之处？

需要清理的字符串通常很短，长度一般在10到30个字符之间。

- ObiWanKenobi

---

我不会把这些内容写在答案里，因为这样并没有更高效的作用。但是，你可以使用像char.IsLetterOrDigit()这样的静态字符方法在if语句中，使它更易读。 - Martin Harris

我不确定检查 A 到 Z 是否安全，因为它会包含 6 个非字母的字符，其中只有一个是所需的（下划线）。 - Steven Sudit

专注于使您的代码更易读。除非您要在循环中执行此操作，例如每秒500次，否则效率并不是一个大问题。使用正则表达式，这将使阅读变得更加容易。 - Byron Whitlock

拜伦，你关于强调易读性的想法可能是正确的。然而，我对正则表达式能否易读持怀疑态度。 :-) - Steven Sudit

正则表达式是否易读有点像德语是否易读；这取决于你是否了解它（尽管在两种情况下，你偶尔会遇到毫无意义的语法规则 ;)）。 - Blixt

Answer 1

你认为自己的方法不有效，为什么？实际上，这是你可以做的最有效的方法之一。

当然，你应该将字符读入局部变量或使用枚举器来减少数组访问的次数:

public static string RemoveSpecialCharacters(this string str) {
   StringBuilder sb = new StringBuilder();
   foreach (char c in str) {
      if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || c == '.' || c == '_') {
         sb.Append(c);
      }
   }
   return sb.ToString();
}

这种方法的效率之所以高效，是因为它能够很好地扩展。执行时间将与字符串的长度成比例。如果您将其用于大型字符串，就不会有任何令人讨厌的意外情况。

编辑：
我进行了一项快速性能测试，对使用 24 个字符的字符串运行每个函数一百万次。以下是结果：

原始函数：54.5 毫秒。
我建议的更改：47.1 毫秒。
带 StringBuilder 容量设置的我的函数：43.3 毫秒。
正则表达式：294.4 毫秒。

编辑2：
我在上面的代码中添加了 A-Z 和 a-z 之间的区别。（我重新运行了性能测试，没有任何显着区别。）

编辑3：
我测试了查找+char[] 解决方案，运行时间约为 13 毫秒。

当然，代价就是初始化庞大的查找表并将其保留在内存中。虽然这不是很多数据，但对于如此简单的函数来说还是相当多的...

private static bool[] _lookup;

static Program() {
   _lookup = new bool[65536];
   for (char c = '0'; c <= '9'; c++) _lookup[c] = true;
   for (char c = 'A'; c <= 'Z'; c++) _lookup[c] = true;
   for (char c = 'a'; c <= 'z'; c++) _lookup[c] = true;
   _lookup['.'] = true;
   _lookup['_'] = true;
}

public static string RemoveSpecialCharacters(string str) {
   char[] buffer = new char[str.Length];
   int index = 0;
   foreach (char c in str) {
      if (_lookup[c]) {
         buffer[index] = c;
         index++;
      }
   }
   return new string(buffer, 0, index);
}

- Guffa

---

我同意。我唯一想做的修改是在StringBuilder构造函数中添加初始容量参数，即“= new StringBuilder(str.Length)”。 - David

我的答案使用了 char[] 缓冲区而不是 StringBuilder，根据我的测试结果，比这个快了一点点。(虽然我的代码可读性稍差，所以小的性能提升可能不值得。) - LukeH

为什么要踩我？如果你不解释哪里有问题，那么回答就无法得到改进。 - Guffa

我会让这个数组变得更小。我认为你可以用2^7（127）的空间来表示所有需要的字符，就像ASCII字符集一样。即使你是通过程序填充这个数组，所有的字符在编译时都是已知的，你甚至可以将它变成只读数组。危险在于其他人可能会将这段代码复制/粘贴到子程序中，并分配比所需更多的空间。 - Sprague

@SILENT：不，它并不会，但你应该只执行一次。如果每次调用方法时都分配一个那么大的数组（并且如果你频繁调用该方法），那么该方法将远远成为最慢的，并对垃圾回收器造成大量工作。 - Guffa

Answer 2

除非你真的需要从函数中挤出最大的性能，否则只需选择最易于维护和理解的方法。正则表达式看起来像这样：

如果需要更高的性能，可以预编译它或仅在首次调用时告诉它进行编译（后续调用将更快）。

public static string RemoveSpecialCharacters(string str)
{
    return Regex.Replace(str, "[^a-zA-Z0-9_.]+", "", RegexOptions.Compiled);
}

- Blixt

---

这是一个非常简单的正则表达式（没有回溯或任何复杂的东西），因此它应该非常快。 - user1228

如果不进行编译，它的速度大约比他的方法慢5倍，经过编译后，它的速度比他的方法慢3倍。尽管如此，它仍然比他的方法简单10倍 :-D - user7116

正则表达式并不是神奇的万能工具，也不比手动优化的代码更快。 - Christian Klauser

对于那些铭记 Knuth 关于优化的名言的人来说，这就是开始的地方。然后，如果你发现你需要额外的千分之一毫秒性能，可以使用其他技术之一。 - John

@nerdspal 只需从正则表达式中删除点号，它应该是"[^a-zA-Z0-9_]+"。 - nramirez

Answer 3

正则表达式看起来像：

public string RemoveSpecialChars(string input)
{
    return Regex.Replace(input, @"[^0-9a-zA-Z\._]", string.Empty);
}

但是如果性能非常重要，我建议您在选择“正则表达式路径”之前进行一些基准测试...

- Christian C. Salvadó

Answer 4

public static string RemoveSpecialCharacters(string str)
{
    char[] buffer = new char[str.Length];
    int idx = 0;

    foreach (char c in str)
    {
        if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z')
            || (c >= 'a' && c <= 'z') || (c == '.') || (c == '_'))
        {
            buffer[idx] = c;
            idx++;
        }
    }

    return new string(buffer, 0, idx);
}

- LukeH

---

+1，已测试，比StringBuilder快约40％。每个字符串0.0294毫秒v. 0.0399毫秒。 - user7116

为了确保，您是指带有预分配还是不带预分配的 StringBuilder？ - Steven Sudit

通过预分配，它仍然比char[]分配和新字符串慢40%。 - user7116

我喜欢这个。我调整了这个方法 foreach (char c in input.Where(c => char.IsLetterOrDigit(c) || allowedSpecialCharacters.Any(x => x == c))) buffer[idx++] = c; - Chris Marisic

Answer 5

我建议创建一个简单的查找表，你可以在静态构造函数中初始化以将任何字符组合设置为有效内容。这样可以进行快速的单一检查操作。

编辑

此外，为了提高速度，你需要将StringBuilder的容量初始化为输入字符串的长度。这将避免重新分配空间。这两种方法结合使用将带给你速度和灵活性。

另一个编辑

虽然编译器可能会进行优化，但出于风格和效率的考虑，我推荐使用foreach而不是for循环。

- Steven Sudit

---

对于数组，for 和 foreach 生成的代码相似。但我不确定字符串是否也是如此。我怀疑 JIT 是否知道 String 的类似数组的特性。 - Christian Klauser

我敢打赌JIT对于字符串的类数组特性比你那个 [已移除笑话] 更了解。Anders等人在.NET中对字符串的所有优化工作做得很多。 - user1228

我没有看到使用布尔数组和整数数组之间的任何性能差异。我会使用布尔数组，因为它将查找表从256 kb降低到64 kb，但对于这样一个微不足道的函数来说，仍然是大量的数据...而且只快了约30%。 - Guffa

Guffa，我会分段回答。1）我查了一下我的笔记，似乎我是错误的。Boolean和Integer的速度差不多，所以我使用了它。 - Steven Sudit

@Guffa 2）鉴于我们只保留字母数字和一些基本的拉丁字符，我们只需要一个低位字节的表格，因此大小并不是问题。如果我们想要通用性，那么标准的Unicode技术是双重间接。换句话说，一个由256个表引用组成的表，其中许多指向相同的空表格。 - Steven Sudit

Answer 6

如果你正在使用一个动态字符列表，LINQ 可能会提供一个更快速优雅的解决方案：

public static string RemoveSpecialCharacters(string value, char[] specialCharacters)
{
    return new String(value.Except(specialCharacters).ToArray());
}

我将这种方法与之前的两种“快速”方法（发布编译）进行比较：

• LukeH的字符数组解决方案 - 427毫秒
• StringBuilder解决方案 - 429毫秒
• LINQ（本答案）- 98毫秒

请注意，算法略有修改 - 字符作为数组传递而不是硬编码，这可能会稍微影响一些事情（即/其他解决方案将具有内部循环来检查字符数组）。

如果我切换到使用LINQ where子句的硬编码解决方案，则结果如下：

• 字符数组解决方案 - 7ms
• StringBuilder解决方案 - 22ms
• LINQ - 60毫秒

如果您计划编写更通用的解决方案而不是硬编码字符列表，则可能值得考虑LINQ或修改的方法。 LINQ绝对可以提供简洁，易读的代码 - 即使比正则表达式更好。

- ShadowChaser

---

这种方法看起来不错，但是它不起作用 - Except() 是一个集合操作符，所以你最终只会得到字符串中每个唯一字符的第一次出现。 - McKenzieG1

Answer 7

我并不认为你的算法仅仅是高效的。它是O(n)的，只检查每个字符一次。除非你在检查之前就神奇地知道值，否则你不可能得到更好的结果。

然而，我建议将StringBuilder的容量初始化为字符串的初始大小。我猜测你所感受到的性能问题来自于内存重新分配。

顺便说一下：检查A-z是不安全的。你会包括[、\、]、^、_和`...

顺便说一下2：为了获得更高的效率，可以按照最小化比较次数的顺序进行比较。（最坏情况下，你需要8次比较，所以不要想太多。）这取决于你期望的输入，但以下是一个例子：

if (str[i] >= '0' && str[i] <= 'z' && 
    (str[i] >= 'a' || str[i] <= '9' ||  (str[i] >= 'A' && str[i] <= 'Z') || 
    str[i] == '_') || str[i] == '.')

顺便提一下：如果你真的需要这个过程变得更快，使用switch语句可能会更快。编译器应该为您创建一个跳转表，从而只进行单个比较：

switch (str[i])
{
    case '0':
    case '1':
    .
    .
    .
    case '.':
        sb.Append(str[i]);
        break;
}

- lc.

---

我同意在这个问题上无法超越O(n)。然而，每次比较都有一个成本可以降低。表格查找具有低廉的固定成本，而一系列比较将随着添加更多异常而增加成本。 - Steven Sudit

关于附注3，你真的认为跳转表比查找表更快吗？ - Steven Sudit

我对交换机解决方案进行了快速性能测试，结果表明其性能与比较对象相同。 - Guffa

@Steven Sudit - 我敢说它们实际上是一样的。愿意进行测试吗？ - lc.

O(n)符号有时让我很恼火。人们会根据算法已经是O(n)的事实做出愚蠢的假设。如果我们将此例程更改为使用从世界另一端的服务器构建一次性SSL连接以检索比较值的函数来替换str[i]调用...你肯定会看到巨大的性能差异，而算法仍然是O(n)。每个算法的O(1)成本很重要，但并不相等！ - darron

@Ic: 我不确定直接表会更快，但我怀疑它们不会更慢。这两种方法都涉及查找；跳转表方法还涉及额外的分支，这通常很慢。我也会避免使用跳转表解决方案，因为它缺乏灵活性。 - Steven Sudit

Answer 8

您可以按照以下方式使用正则表达式：

return Regex.Replace(strIn, @"[^\w\.@-]", "", RegexOptions.None, TimeSpan.FromSeconds(1.0));

- Giovanny Farto M.

Answer 9

我认为这很不错。唯一需要改进的是使用字符串的长度来初始化 StringBuilder。

StringBuilder sb = new StringBuilder(str.Length);

- bruno conde

Answer 10

另一种试图通过减少分配来提高性能的方法，特别是如果该函数被多次调用。

它的工作原理是因为您可以保证结果不会比输入更长，因此可以在不创建额外内存副本的情况下传递输入和输出。因此，您不能使用 stackalloc 创建缓冲区数组，因为这将需要从缓冲区中复制出去。

public static string RemoveSpecialCharacters(this string str)
{
    return RemoveSpecialCharacters(str.AsSpan()).ToString();
}

public static ReadOnlySpan<char> RemoveSpecialCharacters(this ReadOnlySpan<char> str)
{
    Span<char> buffer = new char[str.Length];
    int idx = 0;

    foreach (char c in str)
    {
        if (char.IsLetterOrDigit(c))
        {
            buffer[idx] = c;
            idx++;
        }
    }

    return buffer.Slice(0, idx);
}

- James Westgate